Kid and Karlsson play a game. Initially they have a square piece of chocolate $2019\times 2019$ grid with $1\times 1$ cells . On every turn Kid divides an arbitrary piece of chololate into three rectanglular pieces by cells, and then Karlsson chooses one of them and eats it. The game finishes when it's impossible to make a legal move. Kid wins if there was made an even number of moves, Karlsson wins if there was made an odd number of moves. Who has the winning strategy? (Д. Ширяев)
HIDE: Thanks Thanks to the user Vlados021 for translating the problem.Problem
Source:
Tags: combinatorics
14.04.2019 21:22
We claim that Karlsson has a winning strategy for all $m\times n$ chocolate pieces, for which it's possible to make at least one turn. We prove this by induction on $k=m+n$: Base. For $k=4$ the claim is obviously true. Step. Suppose the statement is true for all $4\leqslant k<l$, and we prove it for $k=l$. Let Kid cut the piece $m\times n$ with $m+n=l$ into three pieces $A$, $B$, and $C$, and, obviously, their perimeters are less than $2l$, so induction hypothetis works on them. Consider two cases: (1) Kid can perform moves with at least two of $A$, $B$, $C$. Then Karlsson eats one of them such that Kid can perform moves with the two pieces left. Then, by induction hypothetis Karlsson has a strategy such that on every of these pieces odd numbers of moves will be performed. So, on both of them an even number of operations will be performed, and including the first turn there is an odd number of operations, hence Karlsson wins. (2) Kid cannot perform moves with at least two of $A$, $B$, $C$. Then Karlsson eats such a piece that Kid cannot perform moves with the two pieces left. There is exactly one turn made, hence Karlsson also wins.
16.04.2019 18:42
Similar to the above Define a $\mathbf{stump}$ to be any $1 \times 1, 2\times 1,$ or $1 \times 2$ piece of chocolate. Then, it's easy to see that the game ends iff at the beginning of Kid's turn, there are only stumps left. Since the number of pieces increases by one at every move, Karlsson just needs to ensure that after each of his turns, the number of stumps is even (since then the number of pieces in the end is even, and so there were an odd number of moves). To do so, he will conduct casework on the number of stumps in the piece that Karlsson has just split. If there are three, then he eats one. If there are two, then he eats the non-stump. If there is one, he eats it. Finally, if there's zero, he can do whatever he wants. It's easy to see that this strategy preserves the parity of the number of stumps, so since it starts out even, it will also end even, and Karlsson wins. $\square$