Can This Be The Answer??!!

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

[bigpooch]

Another (perhaps simpler) way of seeing that the binary
representation of 1/9 is 0.000111000111... is that if you
multiply this by 8 (or shift left by 3) and add the result
to 0.000111000111..., the result is 0.111111... = 1.

[bigpooch]

The solution that BruceZ gave is best in the sense that the
expected number of coin flips is minimized. That is a very
important (and arguably the most important) criterion for
choosing among solutions.

The expected number of flips until the first head is given
by S = 1/2 + 2/4 + 3/8 +... so S-S/2=1 or S=2. Then, (8/9)
of the time, you flip another three times, so the expected
number of coin flips is 2+(8/9)3=2+8/3=14/3.

This solution is perhaps best in the sense that among those
solutions that minimize the expected number of coin flips,
it is easily implemented. It's also an elegant solution
among those that minimize the expected coin flips.

For example, one could use the following schedule to
determine a random variable X with range {1,2,..., 9} with
P(X=k) = 1/9 for all k in the range:

Let H=heads, T=tails.

HHHH: 1
HHHT: 2
HHTH: 3
HHTT: 4
HTHH: 5
HTHT: 6
HTTH: 7
HTTT: 8
THHH: 9
THHT: flip again 1 or 2
THTH: flip again 3 or 4
THTT: flip again 5 or 6
TTHH: flip again 7 or 8
TTHT: flip again 9 or (flip again 9 or #)
TTTH: flip twice again to determine between 1,2,3 and 4
TTTT: flip twice again to determine between 5,6,7 and 8

In case one reaches the "#" sign above, you repeat the
process (this occurs with probability 1/64). Each of the
numbers 1 through 9 are chosen immediately (well, in one
"iteration" of four coin flips) with probability
(1/16)(1+1/2+1/4)= 7/64, so that leaves a "remainder" of
just 1/64.

For this schedule, if E is the expected number of flips,

E = (1/16) [ 9x4 + 4x5 + 2x6 + ((1/2)5+(1/4)6+(1/4)(6+E)) ]
or E = 68/16 + (1/16)((11/2)+E/4) = (147/32) + E/64.
Then, (63/64)E = 147/32 or 63E = 294 which gives E=14/3.
Thus, the above schedule also yields the same expected
number of coin flips.

Also, the solution that BruceZ mentions is one that also
solves the problem in general: i.e., if there are instead
of 9 people, what if there are n where n is not some exact
power of two? [Clearly, if n=3, you only need to know that
1/3 in base two is 0.010101...]

The question now is: for general n (n people), what are all
the "optimal solutions"? And which of these is the most
"elegant"? A proof of "optimality" in general would be
nice!

[BruceZ]

[ QUOTE ]
The question now is: for general n (n people), what are all
the "optimal solutions"? And which of these is the most
"elegant"? A proof of "optimality" in general would be
nice!

[/ QUOTE ]

When N is a power of 2, the solution is trivial. Simply use the result of k flips where N = 2^k. For N a non-power of 2, consider the binary representation of the fraction (2^k)/N where 2^k < N < 2^(k+1). Flip until heads is obtained, and if the first head occurs on a flip corresponding to a 1 in this binary representation, then make k additional flips to determine the selection out of 2^k of the N candidates. Otherwise, repeat this procedure with N replaced by N - 2^k. Continue in this fashion until we have made a selection or until N - 2^k = 1, in which case we select the 1 remaining candidate and terminate.

For example, take N = 45. Consider the binary representation of 2^5/45 = 32/45. Flip until heads is obtained, and if the first head occurs on a flip corresponding to a 1 in this binary representation, then make 5 additional flips to determine the selection out of 32 of the 45 candidates. Otherwise, we repeat this procedure with N replaced by 45-32 = 13, so consider the binary representation of 2^3/13 = 8/13. Flip until heads is obtained, and if the first head occurs on a flip corresponding to a 1 in this binary representation, then make 3 additional flips to determine the selection out of 8 of the 13 remaining candidates. Otherwise, we repeat this procedure with N replaced by 13-8 = 5, so consider the binary representation of 2^2/13 = 4/13. Flip until heads is obtained, and if the first head occurs on a flip corresponding to a 1 in this binary representation, then make 2 additional flips to determine the selection out of 4 of the 5 remaining candidates. Otherwise, select the 5th candidate and terminate.

[nightlyraver]

[ QUOTE ]
The solution that BruceZ gave is best in the sense that the
expected number of coin flips is minimized.

[/ QUOTE ]

This statement makes BruceZ's answer incorrect given the requirements of the correct answer. There must be a finite number of flips for the answer to be correct. Although the odds are almost non-existant, you could theoretically flip tails over and over again, ad infinitum.

I'm starting to think that there is no answer...

[fnord_too]

[ QUOTE ]

I'm starting to think that there is no answer...

[/ QUOTE ]

Hmmm, there is probably a Gallois theory proof if that is the case. That is what was used to show there are no general solutions to quintic equations, all the classic Greek problems (like squaring the circle) are unsolvable, and lots of other stuff that makes my brain hurt just thinking about it.

By the way, this question is exactly the same as deciding between three people (just break up into 3 groups of 3, decide, then take the 'winners' from those groups and decide again).

[bigpooch]

BruceZ:

Okay, what you've given is a solution for general N, but not
necessarily an "optimal one" in minimizing expected coin
flips.

Let S(N) be the minimal number of expected coinflips for the
case of N people where N is an integer >=2. Thus, S(2)=1.
Also, it doesn't take much to show S(3)=8/3 and clearly
S(4)=2.

For the case N=7, if we were to use the method described in
your post, the expected number of coin flips is 2+(4/7)2+
(3/7)S(3)=2+(8/7)+(3/7)(8/3)= 30/7.

On the other hand, suppose I were to flip a coin three times
and use the following schedule:

HHH: 1
HHT: 2
HTH: 3
HTT: 4
THH: 5
THT: 6
TTH: 7
TTT: #

Here, "#" means to flip three times again as if starting
from "square one". The expected number of coin tosses here
is given by E = 3+(1/8)E or E = (8/7)3 = 24/7.

Thus, S(2^k-1)= k(2^k)/(2^k-1) by using the same idea (where
k>=2 is some integer).

Even N
-------

If N is even, it makes sense to keep dividing N by two until
you have an odd factor M, so really S(N) = k+S(M) where k is
the highest power of two that divides N. Once S(M) is
determined for all M where M is odd, then S(N) is found for
all integers.

Close to a power of two
-----------------------

The "elegant" solution you gave works well for any M
"slightly bigger" than some power of two, so this means
S(2^k+1)=2+(k)(2^k)/((2^k)+1). For other values slightly
bigger, it might take some work to find "optimal solutions".

When M is slightly smaller than 2^k-1, it makes sense to
further partition M to minimize further coin-flipping and
finding optimal solutions may be messy.

Here's a short list of values of S(M):

S(3) = 8/3
S(5) = 18/5
S(7) = 24/7
S(9) = 42/9 = 14/3

Anyone care to compute S(11) and S(13) (or S(M) in general
for odd M) ?

[bigpooch]

How so? The expected number of coinflips is finite and the
probability of requiring an infinite number of coinflips is
not only zero, but is a mere "point" on the unit interval.
You apparently don't understand the technical requirements
of a solution, let alone an "optimal one".

[BruceZ]

[ QUOTE ]
[ QUOTE ]
The solution that BruceZ gave is best in the sense that the
expected number of coin flips is minimized.

[/ QUOTE ]

This statement makes BruceZ's answer incorrect given the requirements of the correct answer. There must be a finite number of flips for the answer to be correct. Although the odds are almost non-existant, you could theoretically flip tails over and over again, ad infinitum.

[/ QUOTE ]

The odds are not "almost non-existent". The probability of an infinite sequence of tails is zero. There will be a finite number of flips with probability 1, or 100% of the time. Whether or not this solution satisfies the requirements of a correct answer depends on whether you want a practical solution that will satisfy the requirements every time in the real world, or one which meets some theoretical requirement that has nothing whatsoever to do with reality. Given that this was stated as a real world problem, I would think that the real world answer should be perfectly acceptable, especially when it is completely explained, and especially given that this was asked in an interview, presumably for a real world job.


[ QUOTE ]
I'm starting to think that there is no answer...

[/ QUOTE ]

It should have been obvious to you yesterday that there can be no algorithm which specifies a maximum number of flips in advance and generates a probability of 1/9. If there were such an algorithm, then it would follow that we could represent the probability 1/9 with a finite number of binary digits. This is so because any such algorithm would be represented by a set of sequences of heads and tails whose combined probability is 1/9. Since the probability of any sequence of heads and tails is a power of 1/2, the sum of the probabilities of all the sequences in your solution would be a finite sum of powers of 1/2, which in turn could be represented by a binary number with a finite number of digits, and I showed you yesterday that this is not possible.

Since the question has been answered under both possible interpretations as of yesterday, I'm not sure why we are still talking about this.

[pzhon]

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

[/ QUOTE ]
This is implausible. It sounds like a typical incorrect urban legend. This is a standard problem.

Of course the standard answer has been posted, whether or not the OP accepts it. Trick answers include using the coin in other physical ways such as spinning it or bouncing it.