Thursday, May 05, 2005
Your next coin-flipping puzzle.
Yes, this one's actually pretty easy. Or is it? Imagine you have a fair coin, and need to choose randomly between two people. Well, duh, that's not hard and, no, it's not the puzzle. Imagine, then, that you had four people and again had to choose one of them equally at random. Once again, not too difficult and it's easy to see how this generalizes to any power-of-two number of people.
But what if you had some other number of people, like three, and you still had to choose one of them at random with equal probability across all participants. What do you do? There are a couple reasonably obvious strategies.
First, each person can choose a different length-two sequence from the possibilities of {H,T}, you flip the coin twice and whoever selected that sequence wins. If it's the one sequence no one chose, you just start over and keep flipping twice until you have a winner. This is, of course, guaranteed to be fair but, on the downside, if luck is working against you, you could be flipping for some time before someone wins. Theoretically, if your luck is unspeakably bad, there is no limit to the number of flips you might have to make.
Another algorithm is to have each person flip the coin exactly once. When one person is the odd man out in terms of what shows, that person is the winner and, once again, it's clear that this is fair, just as it's clear that really bad luck means you might be flipping forever if everyone's flips keep matching.
So, the obvious question is, is there a way, with three people and a single honest coin, to fairly select one of those people at random, and be able to put an upper bound on the number of flips you have to make?
Note well that, when I'm asking for an upper bound, this doesn't mean that you must flip that many times before you can declare a winner; perhaps it will take less flips than that maximum depending on your strategy. But, in any case, you need to be able to guarantee that you'll have a winner after at most a finite number of coin flips.
Thoughts?
Open for solutions, Friday, noon, Eastern time.
Subscribe to:
Post Comments (Atom)
4 comments:
OK - I'm going to go on record here and say that there is no conventional solution.
Proof: Let the upper bound be N. Generate all 2^N sequences of possible coin flips running to the limit; put each one on a separate piece of paper. Now go through the proposed procedure with each sequence, with the paper serving in place of coin flips; each one must produce a single winner. (Sequences which establish a winner before reaching the end are OK; that'll just mean that several slips follow the same pattern to this point and all stop in the same place.) Write that name on the slip. In order to have equal odds of each one winning, you'd have to have equal numbers of pieces of paper with each name on them. But with 2^N permutations not divisible by three, it can't be done. So no, I do not think that you can advance a technique which will have a (fixed) upper bound of this sort.
However...
(A) Weigh the coin on an agreed-fair nanogram scale. Convert the answer to base-three. Take the last digit.
(B) Mark a point on the coin's rim, either with a pen or (if you want to forbid marking up the coin) by precise description based on the features on the coin. Spin the coin on a tabletop. When it stops, the number of degrees clockwise between the direction this mark points (from coin center) and true north will be a random value from 0 to 359. Divide by 120 and round decimals down.
- Eric
First, no tricks like weighing the coin or marking it, etc. The puzzle involved simple coin flipping, so we'll deal with the first part of what you wrote.
The proof you give that it can't be done is the obvious one, except for one small glitch. Note that I made it clear that you didn't have to use all N flips before you had the chance to declare a winner. You could, depending on your strategy, declare a winner before then, so insisting on counting all 2^N equally-likely binary sequences isn't completely relevant.
Think a little bit harder.
Hmm. I don't think that invalidates my proof. As I said, the probability of a sequence of results which produces a winner early is equivalent to the sum of the probabilities that you declare the winner early and then proceed to generate the remaining strings as well.
So if a starting string of HH was enough, but the limit was N=4, you could simply put HH-guy's name on all of HHHH, HHHT, HHTH, HHTT. Four of the sixteen overall options. Thus it still comes down to counting permutations; by being declared the winner early he just owns more of them.
But OK. I'll be interested to see my proof disproven. Nice puzzle.
No, no, that's it -- it was simply necessary to make that final observation to be a complete proof. I'll have to come up with something much nastier next time.
Post a Comment