PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 86(100) (2009), 21–25 DOI: 10.2298/PIM0900021A

ON A COMBINATORIAL GAME

Vladica Andrejić

Communicated by Rade Živaljević

Abstract. We introduce a new Nim-like two-player combinatorial game and present a complete winning strategy for the winning side.

1. Introduction

In this paper we develop a winning strategy for a new variation of well known combinatorial game of Nim [1]. The basic work in this topic are series of books, Winning ways by Berlekamp, Conway, and Guy [2] which gives strategy and mathematics of popular games, and describes a number of new games. Further developments are given in the two volumes Games of no chance [3] and More games of no chance [4] which are collections of articles about all aspects of combinatorial game theory. We shall consider the following two-player game of perfect knowledge (no chance).

The Game: There is a pile containing n chips. Two players alternate taking at least one, but no more than 10 chips. The game ends when all the chips are taken, i.e., when a+b = n, where a and b are the numbers of chips taken by players A and B respectively. Player A begins the game and he becomes the winner if numbers a and b are co-prime, otherwise B is the winner.

Variations of Nim have been played since ancient times, and our aim is to solve our new variation, and prove the following theorem.

Theorem 1.1. The player B has the winning strategy if and only if n is an even number greater than or equal to 12 which is not an integer power of 2, or if n = 15, or if n is divisible by 105, 165, 195, 231, 255, 273, or 285.

At the beginning the author considered n which is not divisible by 2, 3, and 5. Let us suppose that player A follows the following strategy: A takes 5 chips on the first move; in each next move A takes, if he can, the same amount of chips taken by B in his previous move; if B took in his last move more chips than there are left, A takes all the chips left. It is obvious that before B’s last move a − b = 5 holds. As till the end of the game A will not take more chips than B, must be a − b ⩽ 5, and as B can take at most 10 chips, b − a ⩽ 5 also holds. Thus it arises |a − b| ⩽ 5, and since (a, b) divides |a − b|, we obtain (a, b) ⩽ 5. Since (a, b) divides a + b = n, and all factors of n are greater than 5, it must be (a, b) = 1, and A wins. It is interesting that if n is a prime, then A wins regardless of his play. Now we should generalize the result for all integers n.

2000 Mathematics Subject Classification: Primary 91A46.

Partially supported by Serbian Ministry of Science and Technological Development, project No. 144032D.

There are generalizations of this game. We can say that the players take at least one, but no more than f(n) chips, for some function f. We shall consider such game conditions in a future paper, in particular the case when f is constant.

2. The Proof

Let us suppose that n is even and n ⩾ 12 (A can win in obvious manner for n < 12). Let us look at the following table that helps us resolve the problem.

-  A has even  A has odd
Remaining A moves B moves A moves B moves
0  B  B  A  A
1  A 1  B 1  B ♠  A ♠
2  A 1  B 2  A 2  B 1
3  A 3  B 3  A 2  B 2
4  A 3  B 4  A 4  B 3
5  A 5  B 5  A 4  B 4
6  A 5  B 6  A 6  B 5
7  A 7  B 7  A 6  B 6
8  A 7  B 8  A 8  B 7
9  A 9  B 9  A 8  B 8
10  A 9  B 10  A 10  B 9
11  B ♠  A ♠  A 10  B 10
12  B ♠  B 1  A 1  A ♠
13  A 1,2  B 1,2  B ♠  A ♠
14  A 1  B 2,3  A 2,3  B 1
15  A 3,4  B 3,4  A 2  B 2
16  A 3  B 4,5  A 4,5  B 3
17  A 5,6  B 5,6  A 4  B 4
18  A 5  B 6,7  A 6,7  B 5
19  A 7,8  B 7,8  A 6  B 6
20  A 7  B 8,9  A 8,9  B 7
21  A 9,10 B 9,10  A 8  B 8
22  A 9  B 10  A 10  B 9
23  B ♠  A ♠  A 10  B 10
24  B ♠  B 1  A 1  A ♠
25  A 1,2  B 1,2  B ♠  A ♠

The first column stands for the number of remaining chips of the pile. The remaining four columns show the possibilities that depend on two things: which player is on the move and whether the number that A took is even or odd. The value in the particular cell tells us which player wins and how many chips he should take in order to win. ♠ in the cell means that the player on the move loses no matter how many chips he takes. We can obtain this table first by filling in the 0-th row with obvious letters. Then using previous ten rows (because player can take at most 10 chips) we fill in the next row. When we make the table, we can notice that winners in rows 1–12 are exactly the same as in the rows 13–24 which gives us that rows will repeat with the period of twelve. Since n is even, A has to play according to the table in order not to take even number of chips.

From the table we can see that B can make a to be even (and won the game) only if n is 12k − 1 or 12k for an integer k. This is not the case if n is a power of 2, so A should play according to the table, and at the end a will be odd. But 2 is the only prime involved in n, so A wins.

Let n = 2m, for odd m > 5. Player B wishes to make A take exactly m chips which will bring B to the victory. n ≡ 2 (mod 4), so n ≡ 2, 6 or 10 (mod 12). According to row 14, 18, or 22, A must take 1, 5, or 9 chips respectively to reach the rightmost cell of the row 25. If B now takes 6 chips, A will have to take also 6 chips (row 19) and head back to the row 25. B is going to play this way until there are 13 chips left with him on the move. Then he will take 7, 9, or 10 chips, depending on starting position, and A must follow with 6, 4, or 2. It is now easy to see that this will lead to a = b = m, giving B the victory.

Let n = 2^{α} · m, where α ⩾ 2, and m > 1 odd integer. Since A has to play according to the table again, the aim of the player B will be to collect m(2^{α−1} − 1) chips, leaving A with m(2^{α−1} + 1) chips, and winning the game. If 3|m then 12|n, so B wins. We are left now with m ≡ ±1 (mod 3), from where n ≡ ±4 (mod 12). Now A must take 3 (or 7) chips and go to row 25. From the table we can see that if after that B takes 2t chips, A must take 12 − 2t and return to the row 25. In this manner player B can increase the difference a − b by 0, 4 or 8 on every 12 chips. Since at the end, there is only one chip left, it will be taken by B and depending on the starting position a − b is 2 (or 6). This value can be increased for 4k, where k is at most 2 · ⌊\frac{n}{12} ⌋. Therefore, B wishes to increase the final value of a − b for 2m − 2 (or 2m − 6). It is now clear that B wins if

2 · ⌊ \frac{n}{12}⌋ ⩾ \frac{2m − 2}{4} ⩾ \frac{2m − 6}{4} .

However,

⌊ \frac{n}{12}⌋ = ⌊ \frac{2^{α} · m}{12}⌋ = ⌊ \frac{2^{α−2} · m}{3}⌋ ⩾ \frac{2^{α−2} · m − 2}{3}

holds, so it is enough to prove that

2 · \frac{2^{α−2} · m − 2}{3} ⩾ \frac{2m − 2}{4} .

This becomes 4(2^{α−2} · m − 2) ⩾ 3(m − 1), and hence (2^{α} − 3)m ⩾ 5. Since m ≡ ±1 (mod 3), odd, and greater than 1, then it is at least 5, so the inequality above holds for α ⩾ 2. This completes the proof in the case of even n.

If we suppose that n = a+b is odd, then (a, b) = 1 if and only if (|a−b|, n) = 1, so some values of |a − b| are good for one, and the remaining values are good for the other player. Let’s try to find the winning strategy for player B, for odd n, for example divisible by 105. Values |a−b| which are good for him are 3, 5, 7, 9, 15, …, but we shall make stronger condition, and demand the victory with final |a − b| ∈ S = {3, 5, 7, 9}. Denote position as triple:

(player on move, current value of a − b, remaining number of chips). If we find for B to win in positions (A, 0, k) for odd k and k_{0} ⩽ k ⩽ k_{0} + 18, it will be easy to prove B to win for every odd k ⩾ k_{0}. In fact for k ⩾ k_{0} + 20 after A takes i and (B, i, k − i), B will take i chips too, which returning to (A, 0, k − 2i) and B won by induction. It is not hard to make a C-program which can prove that B wins in our case for (A, 0, 7), (A, 0, 9), …, (A, 0, 25) so this should be won by B in all (A, 0, k) for odd k ⩾ k_{0} = 7. Of course n ⩾ 105 ⩾ 7 = k_{0}, so B will win in starting position (A, 0, n).

This way we can solve other factorizations of n. In the table below we have factorization of n in which B wins by returning to positions (A, 0, k), for k ⩾ k_{0} which makes it possible |a − b| ∈ S, because of n ⩾ k_{0}.

\begin{matrix}3|n, 5|n, 7|n & S = \{3, 5, 7, 9\} & k_{0} = 7 \\ 3|n, 5|n, 11|n & S = \{3, 5, 9, 11\} & k_{0} = 11 \\ 3|n, 5|n, 13|n & S = \{3, 5, 9, 13, 15\} & k_{0} = 11 \\ 3|n, 5|n, 17|n & S = \{3, 5, 9, 15, 17, 21\} & k_{0} = 27 \\ 3|n, 5|n, 19|n & S = \{3, 5, 9, 15, 19, 21, 25, 27\} & k_{0} = 31 \\ 3|n, 7|n, 11|n & S = \{3, 7, 9, 11, 15, 21\} & k_{0} = 11 \\ 3|n, 7|n, 13|n & S = \{3, 7, 9, 13, 15, 21\} & k_{0} = 19 \end{matrix}

Now we shall find the winning strategy for player A and odd n. A plays first and takes a_{0} chips, so we should look at positions (B, a_{0}, k) with odd a_{0} + k. Using the C-program we can solve remaining factorizations of n:

3 ∤ n  S = {1, 3, 9}  a_{0} = 6 k_{0} = 7
3|n and 5, 7 ∤ n  S = {1, 5, 7}  a_{0} = 4 k_{0} = 11
3, 7|n and 5, 11, 13 ∤ n  S = {1, 5, 11, 13}  a_{0} = 4 k_{0} = 23
3, 5|n and 7, 11, 13, 17, 19 ∤ n S = {1, 7, 11, 13, 17, 19} a_{0} = 5 k_{0} = 32

We see now that this completes the factorizations of odd n, but we should check possible counterexamples. For this to happen it should be n < a_{0} + k_{0} ⩽ 37, and after a simple check (using computer), we find only one counterexample n = 15 where B should win. So we have completed the values of n, which proves the theorem.

References

[1] C. L. Bouton, Nim, a game with a complete mathematical theory, Ann. of Math. 3 (1901–1902), 35–39.

[2] E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Academic Press, 1982.

[3] R. J. Nowakowski, Games of no chance, MSRI Publications, Vol. 29, 1998.

[4] R. J. Nowakowski, More games of no chance, MSRI Publications, Vol. 42, 2002.

Faculty of Mathematics (Received 20 12 2008) University of Belgrade Belgrade Serbia

andrew@matf.bg.ac.rs