A single player game has the following rules: initially, there are $10$ piles of stones with $1,2,...,10$ stones, respectively. A movement consists on making one of the following operations: i) to choose $2$ piles, both of them with at least $2$ stones, combine them and then add $2$ stones to the new pile; ii) to choose a pile with at least $4$ stones, remove $2$ stones from it, and then split it into two piles with amount of piles to be chosen by the player. The game continues until is not possible to make an operation. Show that the number of piles with one stone in the end of the game is always the same, no matter how the movements are made.
Problem
Source: 2022 Brazilian National Mathematical Olympiad - Problem 1
Tags: combinatorics, game, Process, invariant
22.11.2022 02:48
I might be misunderstanding but I don't see why the game necessarily has to end. One can simply alternate between steps i) and ii) indefinitely (e.g., apply rule i) with the 9 and 10 stone piles to obtain a 21 stone pile. Then apply rule ii) on this 21 stone pile and split into a 9 stone and a 10 stone pile).
22.11.2022 09:26
Let $a$ be the number of piles and $b$ be the number of stones. If we apply $(1)$ then $(a,b)\rightarrow (a-1, b+2)$, if we apply $(2)$ we get $(a,b)\rightarrow (a+1, b -2)$, then $2a+b$ is invariant and equal to $2\cdot 10+55=75$ so that if the game ends we will have $k$ piles of $1$ stone and a number $x\geq 1\Rightarrow 2(k+1)+k+a=75=3k+a+2\Rightarrow a=1$ and we always end the game with $25$ piles of $1$ stone.
05.09.2024 17:50
Notice that performing an (unexpected to work) abstraccion of the moves you basically get: \[ \text{lose a pile, gain two rocks} \; \text{or} \; \text{lose two rocks, gain a pile} \]Now let $p$ the number of piles and $r$ the number of rocks, then from the abstraccion we notice that the number $2p+r$ is an invariant, and now it's equal to $2 \cdot 10+55=75$ so, now since the process doesn't change the parity of $r$ (odd), if the game finished as $e, 1, 1, \cdots, 1$ (with $p'$ piles) for some $3 \ge e \ge 1$ then $2p'+p'-1+e=75$ so $3p'+e=76$, first since $76 \equiv 1 \pmod 3$ this shows that $e=1$ and thus $p'=25$ so we must have that the game always ends with $25$ 1's, thus we are done .
17.10.2024 11:58
We show that irrespective of the order in which the movements are made, at the end of the game there will be exactly 25 piles with one stone each. Let $S$ denote the sum of the piles (the total number of stones) and $n$ the number of piles at any given instant. Our claim is that the following quantity is invariant. Claim : The quantity $\mathcal{Q}=S+2n$ is an invariant under the described moves. Proof : We have two kinds of moves, one in which two stones are added when 1 one is reduced, and one where to stones are removed when one stone is added. Thus, it is clear that the net change to $\mathcal{Q}$ after each move is 0 which proves the claim. Note that in the start, \[\mathcal{Q}=S+2n=1+2+\dots + 10 + 2\cdot 10 = 75\]Next, consider the end state of this game. Due to the nature of our allowed moves, each piles can have atmost 3 stones in it and we can have atmost 1 pile with more than 1 stone in it. Thus, we have 3 cases to inspect. Case 1 : Piles consisting of only 1 stone. If we have $k$ such piles, \begin{align*} S + 2n &= 75\\ k + 2k &= 75\\ k &= 25 \end{align*}as claimed. Case 2 : Piles consisting of only 1 stone, and exactly one pile consisting of 2 stones. If we have $k$ piles of size 1, \begin{align*} S+2n &= 75\\ (k+2) + 2(k+1) &=75\\ 3k &= 71 \end{align*}which clearly has no integer solutions. Thus, this is not a possible end state. Case 3 : Piles consisting of only 1 stone and exactly 1 pile with 3 stones. If we have $k$ piles of 1 stone each, \begin{align*} S+ 2n & = 75\\ (k+3) + 2(k+1) &= 75\\ 3k &= 70 \end{align*}which has no integer solutions. Thus, this too is not a possible end state. Thus, the only possible end state is that with $25$ piles of one stone each and we are done.