I generate a random number from 1 to 1000 and ask a student to make a guess of a number. After this guess I tell the student whether they are right or if the correct number is higher or lower. They will get a total of 10 guesses.

I tell my students that if they choose their guess correctly they can always win, which is true. In practice they do not always win because they must guess rather quickly and do any computations in their heads.

If I give you only 9 guesses, what is the probability you will guess the number with optimal guessing?

If I pick a random number from 1 to n with equal probability, tell you the upper limit, and give you x guesses, what is the probability you will win with optimal guessing?

If I am given x guesses, I can discern 2^x - 1 numbers. If instead there are n numbers, my last guess will be some number, and I will still have covered 2^x - 1 of them, so the probability of getting it right is (2^x - 1) / n, or 1, whichever is smaller.

With 9 guesses and 1000 numbers, the probability would be 511/1000.

Part of my optimization would be to choose randomly among the remaining possibilities on the last guess, so that you couldn't choose a number that would be avoided in a strict binary search, such as 1000 itself, in which the guesses would be 500, 750, 875, 938, 969, 985, 993, 997, 999; thus on the last trial, told that 997 is too small, 998, 999 and 1000 should be tried with equal probability.  But if you have chosen your number at random, not trying to game my strategy, this should not matter.

Posted by Charlie on 2007-01-15 12:31:23