Three friends Archie, Billie, and Charlie play a game. At the beginning of the game, each of them has a pile of $2024$ pebbles. Archie makes the first move, Billie makes the second, Charlie makes the third and they continue to make moves in the same order. In each move, the player making the move must choose a positive integer $n$ greater than any previously chosen number by any player, take $2n$ pebbles from his pile and distribute them equally to the other two players. If a player cannot make a move, the game ends and that player loses the game. $\hspace{5px}$ Determine all the players who have a strategy such that, regardless of how the other two players play, they will not lose the game. Proposed by Ilija Jovčeski, Macedonia
Problem
Source: JBMO 2024
Tags: Junior, Balkan, JBMO, combinatorics, game, Strategy
27.06.2024 20:19
A refreshing combi. Somewhat unintuitively (or maybe not), only $C$ can guarantee not to lose. Firstly, we show $C$ guarantees not to lose with the following strategy: Let $A$ make the first move and then mimic $B$ by always playing one more pebble than him. This works as after the first move, $C$ has $2025$ pebbles, and we'll prove that after every move, $A$ makes this remains true. Additionally, we'll show that $C$ can make the desired move. Assume $B$ plays $n$. Then $2n\leq 3\cdot 2024-2025$, so $n$ is at most $2023$. Then $C$ has at least $2025+n\geq 2n+2$ pebbles, so he can make his move of $n+1$. Also, $A$ must add at least $n+2$ to $C$'s pile so Charlie doesn't lose pebbles overall in these three moves because $n+(n+2)=2(n+1)$. Thus, $C$ can't lose. We now show that $C$ can play in such a way that he chooses which $A$ and $B$ loses. We presume that both $A$ and $B$ play so that they guarantee that the other two players can't force them to lose at each move of theirs. With this in mind, we'll show that $A$ plays $n=1$, then $B$ plays $n=2$, and so on. Denote by $p_k$ the position where $A$ has $2024+3k$ pebbles, $B$ has $2024$ pebbles and $C$ has the remaining $2024-3k$ pebbles. In particular, the starting position is trivially $p_0$. We can show that in a $p_k$, whatever $A$ plays, $B$ and $C$ can make moves in such a way that after these three moves, we emerge in $p_{k+1}$ if $k\leq 673$. Indeed, if $A$ chooses $n$, $B$ and $C$ can commit to choosing $n+1$ and $n+2$. Note that $2024-3k\geq 5$, so $2024+3k\leq 4043$. This implies $n\leq 2021$. Therefore, $2(n+1)<2024+n$, and $B$ can play $n+1$. After that $C$ has $n+(n+1)+(2024-3k)\geq 2n+6>2(n+2)$ pebbles, so he can play $n+2$. Therefore, if $k\leq 673$, $B$ and $C$ can play so that $p_k$ becomes $p_{k+1}$. However, $A$ would like not to lose. This is only possible in the position $p_{674}$ and only if $A$ can play $2023$ in that position. Therefore, going back, $A$ can't play $n>3k+1$ at a position $p_k$ because then $B$ and $C$ can force him to have to play $n>2023$ in $p_{674}$ or lose earlier, contradiction. This implies that $A$ must play $n=1$ in $p_0$. Now, on to the first move of $B$, assume it's not $n=2$. Then, with a similar strategy (here the roles are switched cyclically; $C$ plays $B$, $A$ plays as $C$, and $A$ plays as $C$), we'll show $B$ loses if $C$ and $A$ team up. Also, $B$ has $2025$ pebbles initially, so the inequalities required are met. We go into positions $(2025+3k, 2025, 2022-3k)$ for $(B, C, A)$, respectively, and if $B$ dares to increase $n$ by more than three between every three moves, then the $n\to n+1\to n+2$ strategy fails him. Therefore, $B$ must play $3$, then $6$ and so on. In the end, we have: \[(4044, 2025, 3) \to (0, 4047, 2025) \to (2023, 1, 4048) \to (4047, 2025, 0)\text{ and $B$ loses.}\]In summary, to avoid losing, $A$ must therefore play $n=1$, and then $B$ must play $n=2$. Then $C$ may play $n=3$, and the steps continue consecutively using the same logic. We now consider what happens and how $C$ can choose who loses. We have: \[(4043, 2024, 5) \to (3, 4044, 2025) \to (2024, 2, 4046)\]Now if $C$ plays $n=2023$, $A$ loses, and if $C$ plays $n=2022$, $B$ loses. This completes the proof.
28.06.2024 23:27
New JBMO record: this problem has been solved completely by only one contestant (Nina Susic from Serbia). Let us hope that in a future edition there will not be a problem with zero solutions.
29.06.2024 00:03
01.07.2024 17:45
Alternative Solution for $C$: Lemma $1$: The game ends in at most $2023$ turns. Proof $1$: Let's prove that $B_i\leq B_{i-1}-3$ where $B_j$ is the number of pebbles $B$ has after his $j.$ move. \[(a_i,b_i,c_{i-1})\rightarrow (a_i+x,b_i+x,c_{i-1}-2x)\rightarrow (a_i+x-2y,b_i+x+y,c_{i-1}-2x+y)\rightarrow (a_i+x-2y+z,b_i+x+y-2z,c_{i-1}-2x+y+z)\]Hence $b_{i+1}=b_i+(x+y-2z)$ where $z>y>x$. $b_{i+1}=b_i+(x-z)+(y-z)\leq b_i+(-2)+(-1)=b_i-3$ Suppose that the game did not end in $2023$ turns. Then, $B$ makes at least $675$ moves. \[B_{675}\leq B_0-3.675=2024-2025=-1\]Which is impossible.$\square$ Lemma $2$: If $C$ loses after some number of turns, then $2.(\text{number of pebbles of C)}-(\text{number of pebbles of B})\leq 2$ must hold after a move of $A$. Proof $2$: Assume that $2c-b\geq 3$ after each move of $A$. \[(a,b,c)\rightarrow (a+k,b-2k,c+k)\]If $C$ cannot make a move, then $c+k<2(k+1)\iff c+k\leq 2k+1\iff c\leq k+1$. Also $b-2k\geq 0\iff b\geq 2k$. Thus, $\frac{b}{2}\geq k\geq c-1\implies 1\geq c-\frac{b}{2}\iff2\geq 2c-b$ which gives a contradiction.$\square$ Now let's prove that if $c_i=b_i+1,$ then $C$ doesn't lose the game. We will show that $2c-b\geq 3$ after $A'$s moves during $\leq 2023$ turns. Let $f(i)=2c-b$ after $i.$ move. \[(a,b,c)\rightarrow (a+x,b-2x,c+x)\rightarrow (a+2x+1,b-x+1,c-x-2)\rightarrow (a+2x+1-2y,b-x+1+y,c-x-2+y)\]$f(3i+1)=2c-2x-4+2y-b+x-1-y=(2c-b)+(y-x)-5\geq (2c-b)-3=f(3i-2)+3$ Hence $f(3k+1)\geq f(3k-2)-3$. Since $f(1)\geq 2.2025-2025=2025,$ we have $f(3k+1)\geq f(1)-3k\geq 2025-2022=3$ which shows that $f\geq 3$ during the game as desired.$\blacksquare$
09.11.2024 10:26
Let A,B and C be the number of pebbles in pile of the players Archie Billie and Charlie respectively we since there are $1012$ even integers less than $2024$ we know that if all the players play perfectly game will end in $1012$ steps since $1012$ is $1(\bmod 3)$ we know Alice made the last move.If so,Billie loses but if do the calculations as follows; $A=A_0-2(\sum n_{3k+1})+\sum n_{3k+2}+\sum n_{3k}$ $B=B_0-2(\sum n_{3k+2})+\sum n_{3k+1} +\sum n_{3k}$ $C=C_0-2(\sum n_{3k})+\sum n_{3k+1} +\sum n_{3k+2}$ Since all the numbers $A,B$ and $C$ should be positive if we sum $A+B+C$ is also a positive integer.But if you sum all the $RHS$’s you will get $-1012.1013$ which is a negative integer.From this we can say that $A$ cant make a move and the player who makes a move before $A$ wins and that is Charlie