Ketten játszák a következő játékot. 110 zsetonból felváltva vesznek el legalább egyet és legfeljebb kilencet. A soronkövetkező játékos nem ismételheti meg ellenfele lépését. A játékban az veszít, aki nem tud lépni. Melyik játékosnak van nyerő stratégiája.

Two players play the following game. From 110 tokens, they alternately take at least one and at most nine. The next player in turn cannot repeat the opponent's move. In the game, the one who cannot make a move loses. Which player has a winning strategy?
Solution. Let's create a table. In the first column, we write down the number of tokens $(0,1,2,3, \ldots)$, and in the second column, we write down the number that must be taken away to win for each number of tokens. If the second player cannot win with a given number of tokens, we strike out the corresponding row. We are looking for how many tokens we can take away so that we force the other player into a losing position. This can happen in two ways: either we create a number of tokens for which the second column is struck out; or we create a number of tokens where the only number of tokens the other player can take away is the same as the number we took away in the previous step, which the rules do not allow.

| number of tokens | winning moves | number of tokens | winning moves |
| :---: | :--- | :---: | :--- |
| 0 | - | 22 | - |
| 1 | 1 | 23 | 1,6 |
| 2 | 1,2 | 24 | 2 |
| 3 | 3 | 25 | 3 |
| 4 | 4 | 26 | $2,4,5$ |
| 5 | 5 | 27 | 5,8 |
| 6 | 3,6 | 28 | 3,6 |
| 7 | 7 | 29 | 7,9 |
| 8 | 4,8 | 30 | 8 |
| 9 | 9 | 31 | 9 |
| 10 | 5 | 32 | - |
| 11 | - | 33 | 1 |
| 12 | 1 | 34 | 1,2 |
| 13 | 1,2 | 35 | 3 |
| 14 | 3,7 | 36 | 4 |
| 15 | 4,5 | 37 | 5 |
| 16 | 5 | 38 | $3,6,8$ |
| 17 | 6 | 39 | 7 |
| 18 | 7,9 | 40 | $4,8,9$ |
| 19 | 8 | 41 | 9 |
| 20 | 9 | 42 | 5 |
| 21 | 5 | 43 | - |
|  |  |  |  |

Let's start from row 29. First, we check if there is a row among the 9 rows before it where the column is struck out. If there is, in our case it is row 22, we write the difference between the two row numbers in the second column of row 29.

Furthermore, we look for the row whose number of tokens, when subtracted from 29, results in a number between 1 and 9, and we find this number in the second column, and only this one number appears there. We can read from the table, for example, that $29-23=6$ appears in row 23, but there is also a 1 in the second column, so this is not good.

Let's follow the table from row 29:

- 1 row before (in row 28) there are two numbers, so taking 1 token is not a winning move;
- 2 rows before there are also two numbers, so this is not good either;
- 3 rows before there are three numbers, so this is not good either;
- 4 rows before there is only one number, but it is not the 4;
- 5 rows before there is also only one number, but it is not the 5;
- 6 rows before there are two numbers, so this is not good;
- 7 rows before there is a struck-out cell, so taking 7 tokens puts the other player in a losing position, so we write 7 in the second column of row 29;
- 8 rows before there is one number, but it is not the 8;
- 9 rows before there is also one number, the 9, which the opponent cannot repeat, so taking 9 tokens also puts the other player in a losing position. We write this down as well.

Thus, in the second cell of row 29, we write 7 and 9.

If we only look at the struck-out cells and those where only one number appears in the second column, we can discover a repetition starting from row 32, because the next 9 rows after row 32 have the same numbers (where only one number appears) as the first 9 rows.

Therefore, in the rows divisible by 32 (and only these): 32, 64, 96, the second cell is always struck out. 110 is not divisible by 32, so according to the above, the starting player wins the game.

Note. Since $110=96+14$, the starting player will have at least as many winning moves as the number of winning moves in row 14, which is at least two: 3 and 7, but there may be others. (Of course, if we went through the entire table, we would find out if there are any others.)