#8 Games and Strategies I

With moves \(1\) or \(2\), the losing positions are \(0,3,6,9,12,\ldots\). From a multiple of \(3\), every move leaves a non-multiple, while from any other residue one can leave a multiple of \(3\). Since \(14\equiv2\pmod3\), the first player takes \(2\) stones and leaves \(12\). Then the first player complements each opponent move to \(3\) stones.

The losing positions are multiples of \(4\). Since \(20\) is divisible by \(4\), the first player is in a losing position. Whatever the first player takes, the second takes enough to make the two moves remove \(4\) stones. Therefore the second player makes the last move.

The first player first adds \(1\). After an opponent move of \(a\), where \(1\le a\le4\), the first player adds \(5-a\). Then after the first player’s moves the totals are \(1,6,11,16,21\). Therefore the first player wins.

After each first-player move, the second player takes the same number of stones from the other pile. Thus after the second player’s move the piles are equal again. If the first player could take stones from one pile, the other pile had the same number of stones, so the response is legal. Hence the second player will not run out of moves before the first and will make the last move.

The first player places a token in the center. All other cells split into centrally symmetric pairs. If the second player places a token in one cell of a pair, the first player places a token in the other. Thus the first player always responds and makes the last move.

Since one may take from \(1\) to \(4\), the losing positions are multiples of \(5\). The number \(37\) has residue \(2\) modulo \(5\). The first player takes \(2\) stones and leaves \(35\). After that, if the opponent takes \(a\), the first player takes \(5-a\), again leaving a multiple of \(5\).

If one stone remains, the player to move loses. Then losing positions repeat every \(4\): \(1,5,9,\ldots\). Since \(28\equiv0\pmod4\), the first player takes \(3\) stones and leaves \(25\equiv1\pmod4\). Then the first player complements each opponent move to \(4\), until the opponent is left with one stone.

Since \(50\equiv1\pmod7\), the first player starts with \(1\). If the second adds \(a\), the first adds \(7-a\). Then after the first player’s moves the total increases by \(7\): \(1,8,15,22,29,36,43,50\). The first player wins.

The second player pairs the numbers as \((1,20),(2,19),\ldots,(10,11)\). Whenever the first player takes a number from a pair, the second takes the other number in that pair. Each pair sums to \(21\), and each player gets exactly one number from each pair. Therefore the final sums are equal.

After the first player’s move, the second places a domino on the cells centrally symmetric to those just occupied. On a \(6\times6\) board, no domino coincides with its central reflection, and the reflection of adjacent cells is again adjacent. If the reflected cells had already been occupied, then by symmetry the cells of the first player’s move would also have been occupied, impossible. Hence the response is always legal, and the second player makes the last move.

After \(k\) moves, exactly \(k\) rows and \(k\) columns are occupied. If \(k<7\), a free row and a free column remain, and a rook can be placed at their intersection. Thus the game always lasts exactly \(7\) moves. The seventh move is made by the first player, so the first player wins.

Initially there is \(1\) piece, and at the end there must be \(24\) unit squares. Each move increases the number of pieces by exactly \(1\). Therefore there are \(24-1=23\) moves. The odd-numbered last move is made by the first player, so the first player wins.

Positions with equal piles are losing: the opponent can copy the move in the other pile. Therefore the first player should reduce the pile \(17\) to \(12\), taking \(5\) stones. After that, every second-player move is copied in the other pile, and the first player wins.

Multiples of \(3\) are losing: from such a position, moves \(1,2,4\) lead to residues \(2,1,2\) modulo \(3\), while from any non-multiple of \(3\) one can take \(1\) or \(2\) to leave a multiple of \(3\). Since \(30\) is divisible by \(3\), the first player loses with perfect play.

Check positions with residues \(0\) and \(2\) modulo \(7\). From them, moves \(1,3,4\) never lead again to residues \(0\) or \(2\). From every other residue one can move to \(0\) or \(2\): from \(1\) take \(1\), from \(3\) take \(1\), from \(4\) take \(4\), from \(5\) take \(3\), from \(6\) take \(4\). Thus the losing positions are residues \(0\) and \(2\) modulo \(7\). Since \(31\equiv3\pmod7\), the first player takes \(1\) stone and leaves \(30\equiv2\pmod7\).

After each first-player move of \(a\), the second player adds \(10-a\). Then after the second player’s moves the totals are \(10,20,30,\ldots,100\). Therefore the second player reaches \(100\) and wins.

After \(k\) moves, \(k\) rows and \(k\) columns are occupied. As long as \(k<8\), there is a free row and a free column, so another rook can be placed. After \(8\) moves no free row remains, and no move is possible. The game lasts exactly \(8\) moves, so the second player wins.

Positions with residues \(0\) and \(1\) modulo \(7\) are losing: moves \(2,3,5\) from them do not lead back to residues \(0\) or \(1\). From residue \(2\) take \(2\), from \(3\) take \(2\), from \(4\) take \(3\), from \(5\) take \(5\), and from \(6\) take \(5\), leaving \(0\) or \(1\). Since \(52\equiv3\pmod7\), the first player takes \(2\) stones and leaves \(50\equiv1\pmod7\).

If the total is \(63\), any move makes the total at least \(64\), so the player to move loses. Thus \(63\) is losing. Earlier losing positions differ by \(6\): \(57,51,\ldots,3\). From any such position every move goes between neighboring losing positions, and from any other position one can move to the nearest losing one. From \(0\), the first player adds \(3\) and leaves a losing position. Then the first player complements the opponent’s moves to \(6\).

If one stone remains, the player to move loses. Thus the losing positions are \(1,6,11,\ldots\), that is \(1\pmod5\). Since \(47\equiv2\pmod5\), the first player takes \(1\) stone and leaves \(46\equiv1\pmod5\). Then the first player complements the opponent’s move to \(5\).

Compute the nim-sum: \(3\oplus4\oplus5=2\). We need to make it \(0\). If the pile \(3\) is reduced to \(1\), then \(1\oplus4\oplus5=0\). After any opponent move, the nim-sum becomes nonzero; one can reduce one pile to make it \(0\) again. Therefore the winning move is to take \(2\) stones from the pile \(3\).

For moves from \(1\) to \(7\), the losing positions are multiples of \(8\). Since \(2026\equiv2\pmod8\), the first player takes \(2\) stones and leaves \(2024\), a multiple of \(8\). After that, the first player answers a move of \(a\) by taking \(8-a\), always returning a multiple of \(8\) to the opponent.

The second player responds to each first-player domino by placing the centrally symmetric domino. Since the center cell is removed, no remaining cell maps to itself. The reflection of two adjacent cells is again two adjacent cells. If the reflected domino were already occupied, then by the symmetry strategy the domino just placed by the first player would already have been occupied too, impossible. Thus the second player’s response is always legal, and the second player makes the last move.

In binary, \(7=0111\), \(11=1011\), and \(13=1101\). The nim-sum is \(0111\oplus1011\oplus1101=0001\). We need to reduce one pile so that the nim-sum becomes \(0\). For example, reduce \(13\) to \(12\), because \(7\oplus11\oplus12=0\). After that, if the opponent changes one pile, the nim-sum becomes nonzero. In the pile containing the highest set bit of this nim-sum, one can reduce the number so that the total nim-sum becomes \(0\) again. Repeating this, the first player always returns a zero nim-sum to the opponent and eventually takes the last stone.