Saturday, September 25, 2004

The Three-Sided Coin: Answers

The three-sided coin problem generated numerous responses. Virtually all the proposed solutions were correct, with most reporting “thinking time” of under 10 minutes. Some said it took them less than a minute, while others admitted longer times, but 5 minutes was about in the center. A couple of respondents thought the problem was so easy that maybe it was a joke, but most seemed to think it was a nice challenge. Of course, I have a biased sample here, since I don’t know how many people read the problem but couldn’t figure out the answer, or figured it out but didn’t email me.

The most common wrong answer was this:
Flip the coin twice. If you get two heads, go to the beach. If you get two tails, go to the mountains. If you get one heads and one tails, in whatever order, go to the desert.
This approach doesn’t work, because you can get one heads and one tails in two different ways (HT and TH), each one having 1/4 probability. So with this approach, you’d go to the desert 1/2 the time.

As I indicated in the first post, there are many acceptable answers. Here’s the simplest solution, first submitted by Mike Glover. This was also the most common solution, with about 15 people suggesting it (or something very similar):
Label the options A, B, and C. Flip two coins. If you get HH, choose option A. If you get HT, choose option B. If you get TH, choose option C. If you get TT, start over.
Here’s the answer I had in mind, some variant of which was submitted by 7 respondents:
Flip a coin for each pair (A vs. B., B vs. C, and A vs. C). If any option wins both of its head-to-head matches, choose that option. If no option wins both its matches, then start over.
The principle behind these two solutions is the same: attach A, B, and C to equally probable outcomes, and repeat the procedure if any other outcome comes up. Mike’s solution uses two coin flips to generate four outcomes, and then repeats on one of those outcomes. My solution uses three coin flips to produce eight outcomes, and then repeats on two of them.

But I was mistaken to think every solution would have to rely on this principle. Lauren Fisher submitted a very clever solution:
Flip a coin until heads comes up. There is a one-third chance that the first head will come up on an even-numbered flip.
Doubt it? The math works. The probability of the first head occurring on an even-numbered flip is:
(1/2)^2 + (1/2)^4 + (1/2)^6 + (1/2)^8 + …
= (1/4) + (1/4)^2 + (1/4)^3 + (1/4)^4 + …
= (1/4)/(1 - 1/4) = 1/3
This solution does not, like the prior solutions, rely on repeating the procedure for certain outcomes. If you’re concerned that this procedure only generates the 1/3 probability, without choosing among the three options, that’s easily remedied: if the first heads comes up on an even-numbered flip, choose A; if the first heads comes up on an odd-numbered flip, then flip the coin one more time to decide between B and C.

Lauren’s answer does share one thing with Mike’s and my answers: it could in principle require you to flip the coin an infinite number of times. Some respondents suggested procedures that would avoid that problem. For instance, two respondents suggested using the positioning of the coin when it falls – e.g., treating the word “LIBERTY” as one-third of the quarter’s circumference, and choosing option A when LIBERTY is closest to your body. Another couple of respondents suggested something like dividing a piece of paper into three sections, then setting it on the floor and flipping the coin onto it. Although these approaches could work as a practical matter, I think they run counter to the spirit of the puzzle. Glen Raphael defends these approaches, saying:
You might criticize my proposals to make use of rotational or positional info on the grounds that they don't produce exactly a 1/3rd probability. However, any proposal involving merely flipping the coin fails the same test - coins aren't perfect. Flip a quarter and you don't get an exactly 50% chance of heads; it'll be off by a few hundredths of a percent.
Agreed. But in keeping with the conventions of puzzles like these, I wish to assume that we have a “perfect” quarter. Given a perfect quarter, the algorithms discussed earlier will generate a probability of exactly 1/3. (BTW, Glen R. came up with Mike’s algorithm in addition to his position/rotational proposals.)

So, of the three mathematical solutions – mine, Mike’s, and Lauren’s – which is best? All three produce the correct outcome, so the question is which one will get you to a decision fastest. Mike’s clearly dominates mine, because the probability of getting a decision on any given round is 3/4 for both, but his involves only two flips per round while mine requires three. So it’s down to Mike’s and Lauren’s solutions. For Mike’s solution, the average number of rounds it takes to reach a decision is 4/3 (which results from a guaranteed first round, a 1/4 chance of a second round, a 1/16 chance of a third round, etc.). Since each round requires two coin flips, the average number of coin flips is 8/3. For Lauren’s solution, the average number of rounds it takes to for the first head to come up is 2 (which results from a guaranteed first flip, a 1/2 chance of a second flip, a 1/4 chance of a third flip, etc.). But 2/3 of the time, it will be necessary to flip one more coin to decide between options B and C. This adds another 2/3 of a round to her average, for a total of 8/3, which exactly ties Mike’s algorithm. I’m sure this is no coincidence, but I’m not going to try explaining why.

Thank you all for playing!


Anonymous said...

Just because you can find a solution to a problem quickly doesn't mean the problem isn't worth posing. The fact that there are different solutions is insightful in itself. I think Lauren's answer is the most elegant and I would like to know how it occurred to him/her. To "see" something that requires an infinite series to prove is rather remarkable to me. Next, I liked Glen's "knockout" solution which although a tad longer seems very practical requiring almost no understanding of probability. Sorry, Mike, if I got the same solution as you did in about a minute, it means we both think rather linearly (here we go from one toss to two.) I'm not sure what to make of those that gave "weird" non-mathematical answers. Maybe they are voting for Bush!


Anonymous said...

To help remedy the selection bias, I thought about it for around 15 minutes and did not come up with a solution (although what I did come up with was closest to Glen's -- I just didn't quite get to the repeatability part).

Anonymous said...

I believe my answer took me longer than most (about 30/40 mins). That might just break the tie in Mike's favor. Not to mention I came up with a very wrong answer before this one.

I thought through the problem in the same way that it is illustrated in the original post. However, there are other ways to "see" it.

The binary expansion of 1/3 is .010101010.....
If you treat a head as zero and a tail as one it becomes easier to see. Thus, if what you have flipped, when the first head appears, is less than than 1/3 then you "win" (with a 1/3 probability). You could end up in the situation where you flip forever. . .but as Professor Whitman points out, 2 flips are expected.

I like the problem! Thanks.

hc said...

Seems like there are no powers of 2 divisible by three. This just occured to me: every power of 2 is divisible by 2.

Let us assume 2^n is divisible by 3. Then it is also divisible by 6. 6 is 2*3, so we can deduce 2^n/2 = 2^(n-1) is also divisible by 3, and consequently it is divisible by 6, so 2^(n-1) is divisible by 3 too, and so on...

This might be trivial to you, but I'm not a mathematician and it was a great fun to come out with this while reading your posting.

hc said...

Correction to the end of second paragraph: then 2^(n-2) is divisible by 3 and so on...

Anonymous said...

I wolk up thinking about Glen's solution and I think he was too hard on himself. His solution can be improved on! Suppose A flips with B and wins. Next A flips with C and wins. Game over! No need for the third flip unless you want to know where to go to after going to A. So I suspect that all three methods are as efficient as each other. A true elimination process!


Anonymous said...

To see that Mike's and Lauren's approaches are equivalent, modify Mike's approach to answer "Yes" in case TH and "No" in cases HH,HT. Then what Mike is doing is just flipping coins two at a time until a head comes up, and answering "Yes" if and only if that first head comes up on an even-numbered flip.

This problem could be a starting point for a nice philosophy-of-math discussion about measure theory, probability, and certainty. The Mike-Lauren approach will give an answer in finite time with probability 1. However, this does not quite mean it will *always* give an answer-- the sequence of flips that results in all tails forever is one possible sequence of flips; it just has zero probability since there are infinitely many (indeed uncountably many) sequences.

It is not hard to prove, using the fact (noted by a previous commenter) that 2^n is not divisible by 3, that this is the best you can do, in the sense that no event in a probability space generated by a bounded sequence of coin flips-- a sequence with a finite maximum time to give an answer-- can have probability exactly 1/3.

Nick Weininger

Anonymous said...

another take that is not mentioned: label head and tail 0 and 1; list your options as 1 2 3; now throw the coin 3 times; add up the result; if its 0 start over; is this correct?

Anonymous said...

No. There is only one way to get three heads (a sum of three), but there are three ways each to get one head or one tail.