Two players are going to take turns trying to guess a number selected randomly from 1 to 15. After each guess if the number was not chosen they will both be told whether the actual number is higher or lower. A player must make a reasonable guess among the possible numbers remaining on his turn.
What is sought in each of the following cases is the best strategy for each player and the chance they will win.
Case 1: Unlimited (up to 15 if needed) guesses. The winner gets $30.
Case 2: Only 4 guesses allowed total. If the number is guessed the winner gets $20 and the loser gets $10. If the number is not guessed neither gets anything.
The only way to guarantee that somebody wins is for each player on his turn to pick the middle of the available numbers.
On turn one, player 1 picks 7 and wins with probability 1/15.
The game is not over with probability 14/15. Player 2 picks the middle of the remaining 7 possible numbers, and wins with probability 1/7. (Expected win on round 2= 1/7 of 14/15 = 2/15).
The game is still not over with probability 12/15. Player 2 picks the middle of the remaining 3 possible numbers, and wins with probability 1/3. (Expected win on round 3 = 1/3 of 12/15 = 4/15).
The game is still not over with probability 8/15. Player 2 picks the last remaining number and wins. (Expected win on round 4 = 8/15).
So player 1 wins with probability 1/3 and player 2 wins with probability 2/3. Expected winnings for player 1 = 20*(1/3) + $10*(2/3) = $13.33. Expected winnings for player 2 = $17.67.
Does either player have a better strategy? I don't think so. Any other play by player 1 at turn one reduces his chances of winning outright, and also increases the chance that nobody would win. This same strategy both mazimizes the chances of winning outright and minimizes the chance of a "no-win". Similarly, at turn two, any other play by player 2 at turn one reduces his chances of winning outright, and also increases the chance that nobody would win. So both players are incented to adopt the above strategy.
I haven't really considered it, but the game might be more interesting if the players split the money if nobody guessed correctly in 4 guesses. In this case, player 1's best strategy is probably to play for the "no-win", by picking the low or high end of the available range at turn 1 and 3. Player 2's best strategy is probably to pick something mid-range at turn 2 (going for the win).
And it might be even more interesting if they split some amount other than $30 in the event of a "tie". I wonder what minimum amount is necessary to get player 1 to play to for the "no-win". Probably not a hard question, but I need to get back to work.
Edited on February 14, 2012, 11:44 am
Case 2 thoughts (spoiler)
