# The Thirty-one Game: Winning Strategy for the First Player

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.

• You might have to include (a) here -- the solution makes a reference to the "target series," which probably is key to the solution. I suppose that the case of the opponent not choosing $2$ or $5$ you go to the last sentence: But if he ever departs from the "target series," you can enter the series and win. – MCT Jul 15 '16 at 4:31
• Your player 1 did not follow optimal play in your example. If player one begins with $5$ and player two follows up with $3$, player one's correct next move is to take a $2$. Once having done so, whatever player two continues to do, player one will be able to mirror it. The current total will be ten. There still remain at least three of every card, so player two picks whatever and then player one mirrors to get the total to 17. There still remain at least two of every card. So then player two picks whatever and player one mirrors to get total to 24. And then 31, and then player two loses – JMoravitz Jul 15 '16 at 4:42
• This game is very close to the game of Nim, with the added condition that no number can be chosen over a certain number of times. It makes sense that the strategy should be similar. The point is that under the normal Nim strategy, player two should have won, but there aren't enough copies of the 5 card to complete that strategy. – JMoravitz Jul 15 '16 at 4:48
• @MichaelTong Thank you for pointing it out. I have added an explanation to eliminate ambiguity. – Decong Liu Jul 15 '16 at 7:38

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.

• Thank you for your explanation. My problem was that I didn't figure out the winning positions in this problem, and now it makes sense to me. – Decong Liu Jul 15 '16 at 7:50

I just tried the same problem and with help of a friend was able to solve it.

Lets suppose you have the traditional game of Nim with one pile and you can pick 1,2,3,4,5,6 stones from it at a time and the player who first gets above 31 total stones picked(His and opponets') looses. How will you solve this problem?????

we know that the position corresponding to 31 ie if a player A starts picking stones and before this turn of his a total of 31 stones had already been picked . No matters what he picks 1,2,3,4,5,6 his sum gonna greater than 31 ie this is a loosing position.

if we consider any poition between 25-30 all are winning positions because at each position we can choose 6-1 stones respectively and make our opponent land on 31. so another loosing position is 24 similarly the loosing positions are using backtracking 31,24,17,10,3 ie of form 3+(7*n)

Or in another way we can directly say 24 is a loosing position because from 24 whatever no of stones we pick (1-6) we will land upon 25-30 respectively then our opponent will easily land us upon 31 by next adding 6-1 cards .Once upon 31 we will loose.So 24 is a loosing position . So concluding in a backtracking manner loosing positions are 31,24,17,10,3 or 31-7*n

Now come to our original problem.... Assuming we have unlimited supply of Ace,1,2,3,4,5,6 cards we would have solved the above problem similar like the game of nim ryt??

Side Note -

Target series

31,24,17,10,3

Getting into Target series

means choose a card such that after you pick your card the total sum is either of these {3,10,17,24,31} because now your opponent will start at these positions and we know when we start at these positions these are loosing ones.

Now we will devise a game plan assuming we are first player trying i always win first player will start with 5 if other player does not go into target series, you choose the card to get into target series ie(getting your opponent start at a turn when already either 3,10,17,24 or 31 cards have already been picked).Now even if he plays randomly u can always get him into taget series always and he looes which means you win.

  A random game example
first player   second player

0(choooses 5)  5(chooses 3)

8(choooses 2)  10(chooses 6)

16(choooses 1)  17(chooses 5)

22(choooses 2)  24(chooses 4)

28(choosees 3)   31(loosing position will always loose what he chooses)


and if other player chooses 5 to get into target series(ie trying to make you loose), you choose 2 why????

because we want the opponent(second player) to get into target series by choosing 5 each time and eventually make him loose all the 5's he has

for every card number 5 the opponent chooses,chooe 2

  first player   second player

0(choooses 5)  5(chooses 5)

10(choooses 2)  12(chooses 5)

17(choooses 2)  19(chooses 5)

24(choooses 2)  26


Now Second player arrives at position 26 and all the 5 have been used. Now to get into target series ie make first player land at position 31 he needs 5 which are over . So he will definitely not choose 6 at this point and cannot choose 5 also.

So he may choose

  2nd player Choice  ->    first player    -> second player
1               ->     27(choose 4)   ->  31
2               ->     28(choose 3)   ->  31
3               ->     29(choose 2)   ->  31(All 2's are not over)
4               ->     30(choose 1)   ->  31


Second player Looses . First Player wins!!!

Hope you get It. and eventually he will deviate from target series and you can get into target series and win the game and hence, first player always win this game