One of the integers in {1, 2, ... , 2002} is selected at random (with each integer having a chance 1/2002 of being selected). You wish to guess the correct integer in an odd number of guesses. After each guess you are told whether the actual integer is less than, equal to, or greater than your guess. You are not allowed to guess an integer which has already been ruled out by the earlier answers. Show that you can guess in such a way that you have a chance > 2/3 of guessing the correct integer in an odd number of guesses.
Solution
Guess 1, 3, 4, 6, 7, 9, ... , 3n-2, 3n, ... , 2001, 2002 until your guess is correct or greater than the selected number. If your guess is greater than the selected number, then the selected number must be one less than your guess and so you must guess it correctly on your next move.
If the selected number = 1 or 2 mod 3, then you guess it in an odd number of moves. If the selected number is 0 mod 3, then you guess it in an even number of moves. Thus the chance of taking an odd number of guesses is (2·667+1)/2002 = 1335/2002 > 2/3.
© John Scholes
jscholes@kalva.demon.co.uk
11 Dec 2002
Last corrected/updated 1 Jan 03