Subscribe to Computing Intelligence

Thursday, November 18, 2010

Puzzle Number 14: Fair Game?

We have just started looking in detail at randomized algorithms in my computational complexity course. In addition to being a fascinating topic, it is also full of all sorts of fantastic results that make for great puzzles.

This puzzle takes the form of a game for two players, Player A and Player B. Player A has two cards, and he must write a distinct non-negative integer on each card, then lie that card face down on the table. Player B then chooses to flip over the card either on the right or the left, view the value of the number recorded, and must guess whether that value is greater than or less than the number on the other card. Player A is sneaky, however, and adds a rule that Player B must tell Player A the method he will use for determining his guess before they play the game (and Player B is not allowed to deviate from it).

Even with Player A trying to obtain an unfair advantage, it is relatively straightforward to show that Player B can still come up with an algorithm to make his guess that will make the game a fair one (each player has an identical chance of winning):

Player B's Fair Strategy:

Flip over the left card.
If that card has the value 0, guess that the other card's value is larger;
Else randomly (with a 50% chance either way) guess that the other card's value is larger or smaller.

Knowing this strategy ahead of time, Player A will obviously never put a zero on the left-hand card. Other than that, however, there is nothing he can do to increase his odds of winning above 50%, and the game is therefore fair.

Is this the best that Player B can do, or is there an alternative algorithm that he can use that will put his chances of winning above 50%? If there is, what is that algorithm?