Can This Be The Answer??!!

[nightlyraver]

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.

[fnord_too]

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>

[nightlyraver]

Two comments:

1) How do you assign the numbers
2) This process is not determinitive as you can theoretically "start over" an infinite number of times.

[jason1990]

[ QUOTE ]
This process is not determinitive as you can theoretically "start over" an infinite number of times.

[/ QUOTE ]
"Theoretically," you cannot start over an infinite number of times. The probability that you start over infinitely many times is 0. The probability that you reach a definite answer in a finite number of flips is 1.

[fnord_too]

[ QUOTE ]
Two comments:

1) How do you assign the numbers
2) This process is not determinitive as you can theoretically "start over" an infinite number of times.

[/ QUOTE ]

1. Arbitrarily
2. maybe.

[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.

[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.

[bigpooch]

This can be done in several ways. If you denote a[j] to be
1 if the jth flip of the coin is heads and 0 if the jth flip
is tails, you can generate (to any arbitrary degree of
accuracy) a uniform random variable on [0,1). Essentially,
you simply need to divide the unit interval into 9 disjoint
measurable sets, each of the same measure (1/9) and that you
can with ease determine after a reasonable number of flips
which one of these sets the uniform random variable is in.

Here's one way for the division of the unit interval into
[k/9,(k+1)/9) where k=0,...,8:

Let u[n] = summation (j=1 to n) a[j]/(2^j) be the nth
partial sum. Then, if the half-open interval
[9*u[n], 9*(u[n]+1/(2^(n+1)) ) is entirely in one of the
intervals [0,1), [1,2), ...[8,9), you pick the corresponding
person. Here, you are essentially generating enough "bits"
of the uniform random variable to see if it is less than or
greater than a close "boundary point" k/9 (for k=1,...,8).

[nightlyraver]

I do not think that this is determinitive.

[Orlando Salazar]

I haven't scrolled to replies yet. Have everyone do an individual flip and record it. Do a group flip and whoever's individual flip matches the group flip proceeds to the next stage. Repeat process until one person is left. Send this person out. Example shipmates 1, 2, 3, 4 each make an individual flip and get tails. A single flip for the whole group fall tails. Then only 1,2,3, and 4 are eligible to be exiled. Repeat...then make independant flips, with 1 and 2 getting heads and tails, respectively. A final flip results in heads, send shipmate 1.