Here's one I saw a while ago:
A prisoner is presented with the following challenge by one of the guards of the jail. The prisoner is to be blindfolded and then the guard will place $n$ coins on a circular turntable with any combination of heads and tails facing up (with at least one tails showing initially). The prisoners goal is to flip over coins until all heads are showing.
This would be easy enough if the guard did not interfere. The prisoner could just try all $2^n$ combinations, and one of them would be guaranteed to result in all heads. However, to complicate matters, the guard may turn the table during this process. More specifically, the following process is repeated. First, the prisoner chooses a set of positions of coins to flip over. Then, before the coins are flipped, the guard turns the turntable so as to try to prevent the prisoner from flipping all of the coins to heads. Finally, the prisoner flips over the coins that are at the positions chosen in the first step. If all heads are showing, the game stops and the prisoner is set free.
The question is, for what values of $n$ does the prisoner have a winning strategy and how many moves does it take?
What if the guard uses 6-sided dice instead of coins with the goal of showing all ones (assuming the orientations of the dice are preserved relative to their positions on the turntable between rounds)?
In general, what values of $n$ allow a solution with $k$-sided dice?
No comments:
Post a Comment