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?

The probability of a successful guess from n numbers is p(1,n)=1/n. The optimal strategy is to divide the range into two equal (or almost equal) parts, so the optimal number is (n+1)/2 for odd n and n/2 or n/2+1 for even n, where [x] is the integer part of x. After an unsuccessful guess we are left with [n/2] numbers, therefore the probability of a successful guess now is p(2,n)=1/[n/2]. Accordingly for x guesses p(x,n)=1/[n/2^(x-1)]. The answer is P(9,1000)=1/[1000/256]=1/3.

Posted by Art M on 2007-01-19 23:18:11