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>

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

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

[nightlyraver]

This cannot be the answer, because the process fails in two regards. First, you experince difficulties when an odd number of shipmates flip the same as the group flip. More importantly, this is not determinitive, since all flips of a set or sub set may tie the group flip.

In fact, you could have a 9-way tie over and over again. The odds of this will APPROACH 0 over time, but they will never be 0, so you're answer is not correct.

[nightlyraver]

I do not think that this is determinitive.

[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 ]
In fact, you could have a 9-way tie over and over again.

[/ QUOTE ]
The probability that the process ends in a finite number of steps is 1. If this does not meet the interviewer's definition of "DETERMINATIVE", then the answer is that it is impossible.

[Orlando Salazar]

[ QUOTE ]
This cannot be the answer, because the process fails in two regards. First, you experince difficulties when an odd number of shipmates flip the same as the group flip. More importantly, this is not determinitive, since all flips of a set or sub set may tie the group flip.


[/ QUOTE ]

What difficulties for ODD number? Just have those 5 make individual flips. Then repeat. You're wrong here.
I must agree in theory that everyone could keep flipping heads and always have the group flip be tails. Now, while it's damn near impossible, it could happen.

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