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?

there is 1/1000 chance of getting it right in the first guess. You guess 500 so as if the guess is not right the number can be either among 1-499 or 501-1000.

Now if the guess is wrong there is 499/999 chance the no is within 1-499 and 500/999 chance the number is between 501-1000.

thus

 p(1000,9) = 1/1000 + (1000-1)/1000*(500/(1000-1)*p(500,9-1)+499/(1000-1)*p(499,9-1))=0.511000

the answer is .511 as i wrote a program which recursively calculates each value.

Posted by alex on 2007-04-10 13:40:05