Balkan Mathematical Olympiad Shortlisted Problems

Answer: $k=m$. Let the piles be labeled $1,2,\dots ,n$ such that the pile labeled $i$ has $a_i$ stones. We first provide a construction achieving $k\ge m$. Let $a_1=a_2=\cdots =a_{n-1}=m$ and $a_n=m\cdot n$. Then each stone removed from the pile $n$ can be matched to a stone removed from one of the first $n-1$ piles. Since the first $n-1$ piles have $m(n-1)$ stones in total, it follows that we cannot remove more than $m(n-1)$ stones from the last pile, so the game will finish with at least $m$ stones. We now prove that Aida can always force a position with at most $m$ stones. Before going further, we will prove that the game must end, regardless of how Aida and Bob play. Observe that after each move, the sum $a_1+\cdots +a_n$ either decreases or stays constant, and moreover, if it stays constant, then $a_1^2+\cdots +a_n^2$ increases. Hence, if the game never ends, from some point the total number of stones remains invariant, while $a_1^2+\cdots +a_n^2$ increases on each round, contradiction. The rest of the proof relies on the following lemma: Lemma. It is possible to split $\{1,2,\dots ,n\}$ into two non-empty subsets $A$ and $B$ such that $$\left|\sum _{i\in A}{a}_i-\sum _{j\in B}{a}_j\right|\le m.$$ Proof. Imagine a balance. First, place the pile with $a_n$ stones on one of the pans and then place $a_{n-1}$ on the other pan. After having placed $a_{i+1},\dots ,a_n$ on the balance, place $a_i$ on the lighter pan (ties broken arbitrarily). We claim that when $a_n,a_{n-1},\dots ,a_i$ are placed on the balance, the difference of weight is less than or equal to $m\cdot i$. We prove this by induction. The base case $i=n$ is trivial. For the inductive step, assume that immediately before placing $a_i$ the difference in weight is $t\ge 0$. Then the pans will differ by $|t-a_i|$ after placing $a_i$. Since $t\le m(i+1)$ by the inductive hypothesis, we have $-m\cdot i\le t-a_i\le m\cdot i$, so $|t-a_i|\le m\cdot i$. At the end, we will get the desired partition. □ Let's return to the problem. Aida can use the following strategy: she splits the piles into two groups, the ones with labels in $A$ and the ones with labels in $B$, where $A\cup B=\{1,2,\dots ,n\}$ is a partition such that $$0\le \sum _{i\in A}{a}_i-\sum _{j\in B}{a}_j\le m,$$ which is possible by the Lemma. Then, if Bob picks two piles from the same group, Aida moves the removed stones to the larger pile, whereas if Bob picks two piles from different groups, Aida will remove stones from the larger pile. If the two groups initially have total sums of $X$, respectively $Y$, then notice that $h=X-Y\in [0,m]$ is invariant due to this strategy. At the end of the game, there will be at most one nonempty pile. Since $X-Y$ is invariant, all piles in $B$ will be empty, and the piles in $A$ will have a total of $h\le m$ stones, as desired.

---

Alternative solution.

We provide an alternative construction and an alternative proof of the lemma. For the construction, pick $a_1,\dots ,a_n$ such that each of them is a multiple of $m$ and $a_1+\cdots +a_n\equiv m(\mathrm{mod}2m)$. Bob's strategy will be to always remove $m$ stones. It's easy to see that the size of each pile will remain a multiple of $m$, so this is a valid strategy. Moreover, the total number of stones is invariant (mod $2m$) so at any point there will be at least $m$ stones. We now turn to presenting an alternative proof of the lemma. We say that a finite nonempty sequence of reals is $m$-tight if, when ordered increasingly, no two consecutive elements differ by more than $m$. We will prove the following stronger statement: if $x_0,x_1,\dots ,x_n$ is a sequence of $n$ non-negative real numbers such that $x_0=0$ and $x_i\le x_0+\cdots +x_{i-1}+m$ for each $i\in [1,n]$. Then the sequence formed by the sums of all subsets of $\{x_0,\dots ,x_n\}$ is $m$-tight. We prove the statement by induction on $n$. Note that we allow $n=1$ here. The base case $n=1$ is trivial. For the inductive step, assume the property holds for $x_0,\dots ,x_{n-1}$ and we will prove it for $x_0,x_1,\dots ,x_n$. If $x_0,\dots ,x_{n-1}$ determine the sequence $S$ of sums, then the sequence for $x_0,\dots ,x_n$ is $S\cup (S+x_n)$. As both $S$ and $S+x_n$ are $m$-tight and $\min (S+x_n)=x_n\le x_0+x_1+\cdots +x_{n-1}+m=m+\max S$, our conclusion follows. For finishing the proof of the lemma, note that the sequence $a_1,a_2,\dots ,a_n$ satisfies the conditions required for the stronger statement, implying that $s=\frac{a_1+\cdots +a_n}{2}$ lies at a distance of at most $\frac{m}{2}$ from some ${\sum }_{i\in A}{a}_i$. If we let $B=\{1,2,\dots ,n\}\setminus A$, this is our desired partition.

---

Alternative solution.

We provide yet another proof of the lemma. We perform induction on $n$. The base cases $n=1,2$ are clear. For the induction step, assume that $n\ge 3$ and that the statement is true for $1,2,\dots ,n-1$. We replace $a_n$ and $a_{n-1}$ with $|a_n-a_{n-1}|$. It suffices that there is a partition for the new sequence: if we have such a partition, then we can place $\max (a_n,a_{n-1})$ in the same set as $|a_n-a_{n-1}|$ and $\min (a_n,a_{n-1})$ in the other set. We see that $|a_n-a_{n-1}|\le m(n-1)$. If $|a_n-a_{n-1}|\ge m$, then this follows by the inductive hypothesis applied to $a_1,\dots ,a_{n-2}$, $|a_n-a_{n-1}|$. If $|a_n-a_{n-1}|<m$, apply the inductive hypothesis to $a_1,\dots ,a_{n-2}$ to obtain a partition $A^{\prime }\cup B^{\prime }=\{1,2,\dots ,n-2\}$ such that $x={\sum }_{i\in A^{\prime }}{a}_i-{\sum }_{j\in B^{\prime }}{a}_j\in [0,m]$. If we add $|a_n-a_{n-1}|$ to $B^{\prime }$ this will make the difference between the two parts become $|x-|a_n-a_{n-1}||\le m$, as desired.