Game Theory – Winning Strategy for the Thirty-One Game

combinatorial-game-theorygame theoryrecreational-mathematics

I am going through UCLA's Game Theory, Part I. Below is an exercise on page 6:

The Thirty-one Game. (Geoffrey Mott-Smith (1954)) From a deck of cards, take the Ace, 2,3,4,5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one. The player who first makes the sum go above 31 loses. (The following words are left out.)

(a) (omitted)

(b) Nevertheless, the first player can win with optimal play. How?

Here is the solution for question (b):

(In the text below, a target position is a P-position, a position that are winning for the previous player. On that position, the next player has no way to win if the previous player uses the optimal strategy.)

Start with 5. If your opponent chooses 5 to get in the target series, you choose 2, and repeat 2 every time he chooses 5. When the sum is 26, it is his turn and there are no 5's left, so you will win. But if he ever departs from the target series, you can enter the series and win.

I do not quite understand the solution. The game is easy when the opponent chooses only 2 or 5. However, if the opponent departs from the target series, I think that it may go wrong. Let's consider the example below:

number  5 3 4 3 4 3 4 5
player  1 2 1 2 1 2 1 2

The first player chooses 5 initially, and then the second player chooses 3. In order to enter the series, the first player chooses 4 so that 3 + 4 = 7. However, in the last step, the second player chooses 5, making the sum 31, and thus the first player loses.

I believe that I must have misunderstood the solution. Please point out where I've made a mistake, and give me a detailed description and explanation on the optimal play for the first player. Thanks in advance.

Best Answer

The main thing to note here is that this is analogous to the game where one has as many of each card as desired, rather than just four. In particular, it is easy to see that, in this modified game, the winning positions are exactly the positions where the sum is of the form $31-7n$ for some $n$. This is presumably what is meant by the "target series". Therefore, if you play $5$ and your opponent plays $3$, then your next move should be to play $2$, not $4$, since $2$ brings the sum of all the flipped cards to $10=31-7\cdot 3$. That is, the strategy is as follows:

On the first move play $5$. As long as your opponent continues to choose $5$ on their move, play $2$. Once they deviate, make a move that brings you to a number of the form $31-7n$ and end your turn on such numbers for all subsequent moves.

I think the misunderstanding is in what it means to enter the "target series". In particular, you seem to have understood this as meaning that a player should always make sure that the sum of their move and their opponent's last move is equal to $7$. While it is true that this will happen once you are in the target series, in order to move from not being in the series to being in the series, some other sum is desired.

Related Question