Can This Be The Answer??!!

[nightlyraver]

This is my answer - maybe it's right, maybe it's wrong...

You take yourself out of the group and agree to be the coinflipper. Next, divide the remaining 8 into two groups of 4. Flip coin, and heads eliminate the group on the right, tails, the left. Divide the remaining 4 into 2 groups and do the same thing, and then do the same thing to eliminate the final group so there is only one left. Now, it is between the guy that's left and you. Next, flip the coin 3 times and if the sequence matches the previous 3 flips, you flip with the remaining guy to see who gets thrown off. If the 3 flip sequence is different in any way, you don't flip with the last guy and he is simply thrown off.

Thoughts???

[MasterLJ]

[ QUOTE ]
Here's my first cut:
<font color="white"> Assign everyone a number between zero and 8. Flip the coin 4 times, heads is zero, tails is one. First flip is the least significant (rightmost) digit of a binary number, second the next least significant, etc. Convert the number. If it is between zero and 8 inclusive, that person goes. If it is &gt;8, start over. All 9 numbers (0-8) have equal likelihood of coming up and eventually you will have a number that is not 9-15 inclusive. </font>

[/ QUOTE ]

I like this.

I think a slightly more elegant way would to assign people a number from 0 to 8 and then flip the coins 3 times to generate a 0-7 number then flip the coin once more and add the result (1 being heads, 0 being tails or vice versa). This would generate exactly 9 numbers with an even distribution.

EDIT: This doesn't work at all.

[BruceZ]

[ QUOTE ]
A friend of mine was recently on an interview for an engineer position at Google. He said that the interviewer asked him the following question, which if he answered correctly, would result in an imediate job offer. The interviewer himself did not even know the answer.

Here is the question:

You and 8 other people are on a boat, stranded in the middle of the ocean. You know that help will not arrive for 10 days, and that you have exactly enough water for 8 of you to survive for the 10 days. Therefore, you all have agreed to set one of the people off in a life boat in a long shot attempt to find land.

All you have is a fair coin with which to make the decision of who will be thrown off.

Problem: Find a way to FAIRLY decide who is thrown off using the coin. You may flip the coin as many times as you like, BUT you must come up with a DETERMINATIVE answer.


Does anyone know the answer to this problem? Is there an answer?

I have an answer that I believe is correct, and I will post it later for everyone's review.

[/ QUOTE ]

The key to this type of problem is to find the binary representation of the probability involved, in this case 1/9. The binary representation of 1/9 is 0.000111000111000111..., which you can get by binary long division of 1001 into 1, and verify by

(2^-4 + 2^-5 + 2^-6) +
(2^-10 + 2^-11 + 2^-12) +
(2^-16 + 2^-17 + 2^-18) +
...
= 1/9.

Then if we flip the coin until it comes up heads, and note the number of flips that this requires, the probability is 1/9 that the first head will occur on a flip number corresponding to a 1 in the binary representation of 1/9, namely flip 4,5,6,10,11,12,16,17,18,..., since the probability that this occurs is given by the above sum. If this occurs, then throw a particular man overboard. If the first head occurs on a different numbered flip, as it will 8/9 of the time, then flip the coin 3 more times, and use the 8 equally likely outcomes of these 3 flips to choose one of the other 8 men, who will then each have a probability of (8/9)*(1/8) = 1/9 of being selected.

Note that since the binary representation of 1/9 does not terminate, there is no way to guarantee that an algorithm will terminate after any particular number of flips, but as a practical matter, it will terminate once we have flipped the first head and then flipped 3 more times when necessary.

[nightlyraver]

This is not correct, as you can theoretically keep flipping tails.

[jogsxyz]

Infinite flips means infinite possible solutions. Are you should the question doesn't state in the minimum number of flips needed for a solution?

One simple solution. All nine flip the coin. The majority matches are safe. 5 heads and 4 tails means the 5 heads are safe. The remaining players flip til only one is different. He goes. If there were only two remaining after the first round of flips, the two flip off. One flips first and the other attempts to match it.

[jason1990]

The probability that you are thrown overboard is 1/16, not 1/9, so this method is not fair.

[BruceZ]

[ QUOTE ]
This is not correct, as you can theoretically keep flipping tails.

[/ QUOTE ]

This is the best possible solution to this problem, and this type of problem has been discussed here before. As I said, NO algorithm can be guaranteed to terminate in a finite number of flips since the binary representation of 1/9 does not terminate. As a practical matter, it will always terminate eventually with probability 1, since the probability of an infinite number of tails is 0.

[jason1990]

[ QUOTE ]
This is not correct, as you can theoretically keep flipping tails.

[/ QUOTE ]
As long as I am already here, I suppose I can repeat myself one more time. Theoretically, you cannot keep flipping tails. The probability that you flip an infinite sequence of tails is 0. The probability that you eventually flip a head is 1.

[nightlyraver]

I know - but isn't everyone else's 1/16, too?

[jason1990]

[ QUOTE ]
I know - but isn't everyone else's 1/16, too?

[/ QUOTE ]
Well, someone must be thrown overboard, and there are only 9 of you. Since 9*(1/16) is not 1, no, everyone else's is not 1/16.