Puzzle from last week

3 cities

For triangles with an angle greater than 120 degrees, the path along the two shortest sides is minimal. For all other triangles, the paths to the point that forms three 120 degree angles to the vertices is minimal.

We can start by over constraining the problem to an equilateral triangle. The path connecting the centroid is minimal. In the case of an isosceles triangle, with a height of h and base of 2, the route is defined by h–tan+2sec. The angle from the base for which this is minimum can be found by looking at the derivative, –sec²+2sectan, which is zero for π/6. So the angle between the roads is 2π/3 or 120 degrees. Note that if the base angle of the triangles are less than or equal to π/6, then h is less than or equal to tan and the shortest route is just 2sec.

In the general case, h₁–b₁tan=h₂–b₂tan, ergo, (h₁–b₁tan)/2+(h₂–b₂tan)/2=h₁–b₁tan=h₂–b₂tan, so we need the minimum of (h₁–b₁tan)/2+(h₂–b₂tan)/2+b₁sec+b₂sec. The derivative,–b₁sec²/2–b₂sec²/2+b₁sectan+b₂sectan again is zero at π/6.

Michalewicz and Fogel (pp 187–188) discuss the four-city version of the problem, but constrained by placing the cities at the vertices of a unit square. Following the exterior path (red) the length is 3. The diagonal paths (green) have a length of 2root2 (~2.828). The circular path (blue) has a length of pi (~3.142). The path that utilized pi/3 connections (pink) is optimal (with a length of 2.732).

The generalization of this problem is known as Steiner's problem and it has no known general (efficient) solution.

Class discussion

Let's Make a Deal

Monty Hall, the host of the television game show Let's Make a Deal knows behind which of three doors the grand prize is hidden. He offers you a choice of one of the doors. After you select, he opens one of the two remaining doors to reveal that the grand prize is not behind that door. He then offers you the choice of staying with the door you originally chose or switching to the third door. Do you switch or stay with the door you first selected? Which strategy optimizes your chances of winning? Or does it matter at all?

The odds increase to 2:1 in your favor if you switch. In the original configuration, the odds were uniformly distributed across the three doors: 1:3, 1:3, 1:3. Therefore, the odd that the prize is behind one of the two doors you did not select is 2:1. These odds don't change by Monty Hall opening a door and revealing hidden information. For example, if you choose door A, then the odds that the grand prize is behind one of doors B and C is 2:3. These odds don't change when it is revealed that there is a rubber chicken behind door B. The odds are still 2:3 that the grand prize is behind doors B and C, therefore the odds are 2:1 in favor of switching from door A to door C.

If you had chosen either door without the prize (2:3) and then changed, you’d win.
If you had chosen either door without the prize (2:3) and stayed, you’d lose.
If you had chosen the door with the prize (1:3) and then changed, you’d lose.
If you had chosen the door with the prize (1:3) and stayed, you’d win.
Ergo, changing wins 67% of the time. Staying wins only 33% of the time.

Or, more formally:
3 doors: (X, Y, Z)
Chance of $ behind door: (Cx, Cy, Cz )
Chance of door being opened by Monty Hall: (Hx, Hy, Hz )
If you choose X and switch: P(Hz^Cy)+P(Hy^Cz)=P(Cy)×P(Hz|Cy)+ P(Cz)×P(Hy|Cz)=(⅓×1)+(⅓×1)=⅔.

While the Monty Hall puzzle has been around for years, the above solutions are taken from The Curious Incident of the Dog in the Night-Time by Mark Haddon.

Spin

According to Martin Gardner, this puzzle was developed by Colin R. Blyth after reading a 1951 paper by E.H. Simpson.

You have three spinners, A, B, and C.
A always returns 3.
B returns 2 on 56% of the spins, 4 on 22% of the spins, and 6 on 22% of the spins.
C returns 1 on 51% of the spins, and 5 on 49% of the spins.

In head-to-head competition, which spinner wins the most? Which spinner wins the least?

A will beat B 56% of the time. A will beat C 51% of the time. B will beat C nearly 62% of the time.

When all three are spun together, which spinner wins the most? Which spinner wins the least?

A will beat B & C 29% of the time (56% x 51%). B will beat A & C 33% of the time (22% + (22% x 51%)). C will beat A & B 38% of the time (49% x 78%).

Lotteries

From How to Win More: Strategies for Increasing a Lottery Win by Henze and Riedwyl

Lotteries date back at least to the early 17th century in Genoa. Today it's a worldwode phenomenon. Most lotteries are of the form r/s where you need to match r numbers out s choices. For example, Massachusetts Megabucks is a 6/42 lottery. You need to choose 6 numbers out of 42 in order to win. (See Megabucks.)

Lotto's a taxation
On all fools in the nation
But heaven be praised
It's so easily raised
from Lotto, Then and Now by Morton

Prize structures can be somewhat complex, but the basic thing to keep in mind is that the top prize money is distributed across all of the winning tickets. Since winning is random, the only point of leverage is to maximize the payout when you win, which means minimize the number of winning tickets. You could do this through techniques such as denial of service attacks, which is illegal, or by choosing number combinations that others are unlikely to pick.

The odd of winning a lottery are based on r and s and the number of tickets you buy. For each ticket, the odds of winning are (s*(s-1)*(s-2)*...*(s-r))/(1*2*3*...*r) to 1. Restated, that is (s!)/(r!*(s-r)!). For Massachusetts Megabucks, that is (42*41*40*39*38*37)/(1*2*3*4*5*6)=5245786 to 1, or slightly less likely than tossing 22 "heads" in a row. If you play once per week, chances are you'll win in 100398 years.

You cannot beat the odds. You can examine the past history of winning numbers to find any number of patterns, including that seem to repeat often or numbers that are "due", but you would be wasting your time, because in a lottery, future events are completely independent of the past.

What not to do: Never choose numbers according to a rule or pattern that someone else might use! Common patterns include arithmetic progressions, combinations of numbers that have won in the past, "hot" or "cold" numbers, etc., because these patterns are more likely to result in combinations that other people also choose.

The sensible thing to do is use "Quick Pick," i.e., have the computer chose a random number for you. You could do additional analysis to determine likely combinations and then avoid them for a slight edge.

For an r/s lottery, the odds of any particular number coming up is c, the combination of all possible number sequences. To repeat a number, you need at least two drawings and you will definitely repeat after c+1 drawings. Given k=2 to c+1, the probability of a repeat is 1 minus the product of 1-(j/c) for j=1 to k-1.
For MegaBucks:
6/42 lottery: c=5245786
# of drawings: odds of a repeat
1000: 0.090
1500: 0.193
2000: 0.317
2500: 0.448
3000: 0.576
3500: 0.689
4000: 0.782
4500: 0.855
5000: 0.908
5500: 0.944
6000: 0.968
6500: 0.982
After 3000 drawing, the odds are there will have been a repeat!! (See How To Win More, pp. 116-8)

Puzzle for next week

The monkey and the chimpanzee

chimpanzee is in, but monkey is out
pistachio is in, but peanut is out
turkey is in, but chicken is out
pumpkin is in, but the pie is out
cacophony is in, but harmony is out
stress is in, this being MIT, and, alas, relaxation is out
variety is in, and thank goodness, tedium is out
operetta is in, but symphony is out
hospital is in, but the doctor, nurse, and patient are out
roommate and companion are both in, but friends and family are out
insecticide is in, but all manner of creepy things, including ants, spiders, etc., even centipedes are out
What is the rule determining what is in and what is out?
(See http://epigram.media.mit.edu/walter/chimp.html)