There are 60 empty boxes $B_1,\ldots,B_{60}$ in a row on a table and an unlimited supply of pebbles. Given a positive integer $n$, Alice and Bob play the following game. In the first round, Alice takes $n$ pebbles and distributes them into the 60 boxes as she wishes. Each subsequent round consists of two steps: (a) Bob chooses an integer $k$ with $1\leq k\leq 59$ and splits the boxes into the two groups $B_1,\ldots,B_k$ and $B_{k+1},\ldots,B_{60}$. (b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes one pebble from each box in the other group. Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest $n$ such that Alice can prevent Bob from winning. Czech Republic
Problem
Source: 2019 ISL C7
Tags: combinatorics, IMO Shortlist, IMO Shortlist 2019, game, Combinatorial games
23.09.2020 02:25
Rename the players Zeus and Athena. We'll solve the problem with $m$ boxes, the problem given is the $m=60$ case. We have the following lemma that will be useful throughout the solution. Lemma: Suppose that given a position, Zeus decides to add a positive number of stones to the boxes, and suppose after doing so, he has a winning strategy. Then, he also had a winning strategy before adding the stones. Conversely, if Athena decides to remove a positive number of stones to the boxes, and then has a winning strategy, she must have had one before removing the stones as well. Proof: Trivial. $\blacksquare$ Let $g(m)$ denote the configuration of stones given by \[\lfloor m/2\rfloor+1,\lfloor m/2\rfloor,\ldots,2,1,2,\ldots,\lfloor m/2\rfloor,(\lfloor m/2\rfloor+1\text{ if }m\text{ odd}),\]and let $f(m)$ be the total number of stones in $g(m)$. We claim the answer is $f(m)$. Zeus's Strategy. We show that if there are fewer than $f(m)$ stones, then Zeus wins. The proof is by induction on $m$, with the $m=2$ easy to check. Now suppose that Zeus can win with $m-1$ boxes and fewer than $f(m-1)$ stones. This means that in the $m$-box case, if any set of $m-1$ boxes has fewer than $f(m-1)$ stones, then Zeus wins by just focusing on those boxes. So WLOG suppose every set of $m-1$ boxes has at least $f(m-1)$ stones. It is easy to verify that \[f(m) = f(m-1)+\lfloor m/2\rfloor +1,\]so in fact, since there are total fewer than $f(m)$ stones, but every $m-1$ boxes have at least $f(m-1)$ stones, we have that every box has at most $\lfloor m/2\rfloor$ stones. The following claim then finishes the induction. Claim: If every box has at most $\lfloor m/2\rfloor$ stones, then Zeus has a winning strategy. Proof: Call position $A$ strictly smaller than position $B$ if $A$ can be made by removing a positive number of stones from $B$. Let $(\star)$ be the following statement: Athena never makes a move which leads to a position strictly smaller than some position that appeared before. We first show that if Zeus can win under the assumption $(\star)$, then he can win without the assumption. Indeed, if Athena plays to a position strictly smaller than something played before, then by the lemma Zeus can still win from this position, as it just backtracks in his strategy. The only thing that we have to worry about is Athena setting up an infinite loop, but this can't happen since she can only backtrack to a given position in Zeus's strategy finitely many times, and since Zeus has a finite strategy, Athena can only backtrack finitely many times. Thus, it suffices to show Zeus can win under the assumption $(\star)$. Zeus is to play as close to the middle as possible. WLOG Zeus plays $k=\lfloor m/2\rfloor$ and Athena decrements $B_1,\ldots,B_k$ (the other cases are similar). Now, Zeus plays $k=\lfloor m/2\rfloor-1$. Athena is forced to decrease $B_1,\ldots,B_k$ again now, under threat of violating $(\star)$. Now Zeus plays $k=\lfloor m/2\rfloor-1$, and again, Athena is forced to decrease $B_1,\ldots,B_k$ again. Zeus keeps going till $k=1$, and $B_1$ is decreased $\lfloor m/2\rfloor$ times, so to start, $B_1$ must have had at least $\lfloor m/2\rfloor+1$, which is a contradiction. Thus, Zeus wins, as desired. $\blacksquare$ This completes the Zeus strategy part of the problem. Athena's Strategy. We show that Athena can win with the configuration $g(m)$. Similar to before, call position $A$ weakly better than position $B$ if $A$ can be made from $B$ by adding a nonnegative number of stones. Similar to before, let $(\star\star)$ be the following statement: Zeus never plays a move which would allow Athena to get a position which is weakly better than something that appeared before. Call such a move weak. We first show that if Athena can stall under the assumption $(\star\star)$, she can stall without the assumption. Indeed, if Zeus ever plays a weak move, then by the lemma, Athena can still win from that position. Note that there is no infinite loop analysis here since Athena's only goal is to stall forever. Thus, it suffices to show Athena can stall Zeus under the assumption $(\star\star)$. By possibly flipping $g(m)$, suppose Zeus's first move is $k_0\le\lfloor m/2\rfloor$. Athena should decrease $B_1,\ldots,B_{k_0}$. BY $(\star\star)$, Zeus is forced to play $k_1<k_0$, and again, Athena should decrease $B_1,\ldots,B_{k_1}$. Zeus's next move needs to be $k_2<k_1$, and this continues till Zeus is at the very end with no moves left (in reality, his next move is forced to be weak). It's easy to see that Athena survives this, so we're done.
23.09.2020 02:27
The answer is $31+30+\dots+2+1+2+\dots+\dots+30 = 960$. A chop refers to a Bob-move. After each chop, Alice either adds left and subtracts right, or subtracts left and adds right. \medskip Sufficiency (strategy for Alice): To show that this is sufficient, let Alice keep a history of all the moves Bob makes. If Bob ever makes the same chop twice, then Alice responds in the opposite way and the two moves cancel out. Hence it is enough to consider the case where each chop is used at most once. Now, Alice distributes the pebbles in the V-shape $31+30+29+\dots+2+1+2+3+\dots+30$, and uses the following strategy. If Bob chops at $k \le 30$, Alice adds right and subtracts left. If Bob chops at $k \ge 31$, Alice adds left and subtracts right. This works, and now motivates the necessity proof. \medskip Necessity (strategy for Bob): Assume there is some minimal $n$. For convenience we will allow Bob to chop at $k=0$ and $k=60$ and require Alice to add right when $k=0$, and add left when $k=60$. Now consider possible placements $h$ for Bob's first move, and Alice's response to them. By ``discrete intermediate value'', we find that there is some $h$ such that Alice adds right on an $h$-chop but adds left on an $(h+1)$-chop. [asy][asy] usepackage("amssymb"); unitsize(10mm); label("$\ge 7$", (0,2)); label("$\ge 6$", (1,2)); label("$\ge 5$", (2,2)); label("$\ge 4$", (3,2)); label("$\ge 3$", (4,2)); label("$\ge 2$", (5,2)); label("$\bigstar$", (6,2), blue); label("$\bullet$", (7,2)); label("$\bullet$", (8,2)); label("$\bullet$", (9,2)); label("$\bullet$", (0,0)); label("$\bullet$", (1,0)); label("$\bullet$", (2,0)); label("$\bullet$", (3,0)); label("$\bullet$", (4,0)); label("$\bullet$", (5,0)); label("$\bigstar$", (6,0), blue); label("$\ge 2$", (7,0)); label("$\ge 3$", (8,0)); label("$\ge 4$", (9,0)); draw( (5.5,2.5)--(5.5,1.5) ); draw( (6.5,0.5)--(6.5,-0.5) ); label("$h$", (5.5,2.5), dir(90)); label("$h+1$", (6.5,0.5), dir(90)); label("($-1$)", (2.5,2.4), lightred); label("($+1$)", (7.5,2.4), deepgreen); label("($+1$)", (2.5,0.4), deepgreen); label("($-1$)", (7.5,0.4), lightred); [/asy][/asy] We now go as follows. Claim: There are at least $2+3+\dots+(h+1)$ stones among the first $h$ boxes. In fact, there were at least $2$ stones in the $h$th box, $3$ stones in the $(h-1)$st box, etc. Proof. Bob starts the game by chopping at $h$, and as promised Alice subtracts left. Now, Bob now implements the following stack-based procedure. Initially, Bob positions his thunderbolt (blade, etc.) at $h-1$. Bob chops at the position of his thunderbolt. If Alice subtracts left (the expected case), he moves the thunderbolt one box to the left. (So for example, if Alice always subtracts left, then Bob chops at $h-3$, $h-4$, \dots.) However, suppose unexpectedly Alice subtracted right at $h-k$ (but had subtracted left the previous turn). We call such an event a cancellation as the previous two moves, in tandem, do nothing but destroy $2$ stones. When this event occurs, Bob rewinds one step and now chops at $h-k+1$ instead, as if the previous two moves had not happened (but the total number of stones has decreased by $2$ for large $k$, although there may still be more than $n$). The thunderbolt can never rewind all the way back to $h$, because if it did so, the number of stones total would now be $n-2c < n$, where $c$ is the number of cancellations. However, there can also be at most a finite number of cancellations, since each cancellation destroyed two stones. So eventually, the thunderbolt reaches all the way to the left. Ignoring the cancellations as we may (since they each do nothing but destroy $2$ stones), we find the desired claim. $\blacksquare$ Remark: The stack-based procedure is a bit roundabout. You can be more succinct and more general by simply arguing as follows: if $k < \ell$, and on one round Bob chopped at $\ell$ to see Alice subtracting left, then you may as well assume Alice subtracts right if Bob then chops at $k$. For otherwise, Alice simply destroyed some stones (as in cancellation above), and this position is strictly worse than the one before these two moves. By exactly the same token, the $(h+1)$st box has at least $2$ stones, etc. Thus the number of stones is at least $1 + (2 + \dots + (h+1)) + (2 + 3 + \dots + (60-h))$ which can be checked to be at least $960$.
23.09.2020 04:47
23.09.2020 06:55
27.05.2021 17:21
Very nice problem! yay I solved a C7 The answer for $n = 2c$ boxes is $c^2 + 2c$. For the problem, with $c = 30$, the answer is $960$ pebbles. Call Bob splitting the boxes into $B_1, ..., B_k$ and $B_{k+1}, ..., B_{2k}$ a k-partition. Say Alice moves right if she adds pebbles to the right partition and say she moves left if she removes pebbles from the right partition. First, for Alice's strategy with $c^2 + ck$ pebbles. Alice places the pebbles as $c+1, c, c-1, ..., 2,1,2, 3, ..., c-1, c$ in the boxes, which is a total of $\frac{(c+1)(c+2)}{2} + \frac{c(c+1)}{2}- 1 = c^2 + 2c$ Suppose Bob partitions at $k$ for the second time, then Alice just moves in the reverse direction as she did the previous turn. This is equivalent to Alice not having moved either time and so we can ignore the two moves. So assume a k-partition occurs at most once. Alice uses the following strategy: If $k \le c$, then she moves right and if $k > c$, then she moves left. Its easy to see that this works since a box containing $n$ pebbles can lose at most $n-1$ of them. Now, we will show the converse. Suppose Alice can prevent Bob from winning with $n$ stones and further suppose this $n$ is the minimal such number of pebbles. We will show that $n = c^2 + 2c$ Observe that if Bob begins by partitioning at $1 \le k \le c-1$, then Alice has to move right since if she moves left, then the number of pebbles decreases and Alice must still have a strategy to prevent Bob from winning, which is impossible since we assumed $n$ was the minimum number of pebbles. Similarly, if Bob begins by partitioning at $c+1 \le k \le 2c$, then Alice has to move left. WLOG assume that when Bob partitions at $c$, Alice moves right. I will prove by induction that $B_{c-i}$ has at least $i+2$ pebbles in it. The base case for $i = 0$ is obvious since if $B_c$ had only one pebble, then Alice cannot move right for a c-partition So now, suppose boxes $B_{c-i}$ for $0 \le i \le z$ have at most $i+2$ pebbles in them. Bob partitions at $c$ and then moves leftward by partitioning at $k-1, k-2$ and so on. If Alice keeps moving right, then we have no problem and we can complete the induction easily. The problem arises when Alice decides to change her mind(How like a girl!) and moves left, suppose when Bob partitions at $B_z$. Then consider this move and the previous move where Bob partitioned at $B_{z+1}$ and Alice moved right. Observe that these two moves together effectively do nothing but reduce the number of pebbles in $B_z$ by $2$. Now, even a blind cat can see that no sane person who wants to prevent Bob from winning would do this. Indeed, suppose Alice did this, then Bob just partitions at $B_{z+1}$ and continues the algorithm. This can easily be seen to work since this does not make Alice's job any easier. Again, a problem arises, if in this manner, Alice forces Bob to go all the way back to $B_c$. But then, the total number of pebbles have decreased, which is impossible since $n$ was minimal. So, the induction is complete and every $B_{c-i}$ has at least $i+2$ pebbles. In a similar way, you can show that $B_{c+i}$ has at least $i$ pebbles by inducting rightward instead of leftward. So, this means that the boxes have a total of $(2+3+...+c+1)+1+(2+3+...+c) = c^2 + 2c$ pebbles, as desired. $\blacksquare$
29.12.2021 05:51
The answer is $31+30+\dots+2+1+2+\dots+30 = 960$. Strategy for Alice: Distribute the pebbles in the order $31,30, \dots 2,1,2, \dots , 30$ from left to right. Suppose Bob chooses an integer $k \ge 31,$ add to $B_1,\ldots,B_k$ if this is the $2n-1$th time Bob has made this choice for an integer $n.$ Otherwise, add to $B_{k+1},\ldots,B_{60}$. We can now assume that each integer has been toggled at most once, and it is easy to verify her strategy works. Strategy for Bob: Suppose for a positive integer $k$ there are $2k$ boxes with at most $k$ each. We claim Bob can win. First, Bob does a $k, k$ split. Assume WLOG Alice adds to the left. Now do a $k+1, k-1$ split. If Alice adds to the right, then the net effect after the last two rounds is that the $k+1$th box has one less pebble and the rest of the boxes are unaffected. Otherwise Alice adds to the left again. Now do a $k+2, k-2$ split. If Alice adds to the right, then the net effect after the last two rounds is that the $k+2$th box has one less pebble and the rest of the boxes are unaffected. Otherwise Alice adds to the left again. Now do a $k+3, k-3$ split, a $k+4, k-4$ split, and so on. Bob will continue performing moves in this way, and each time we may assume Alice adds to the left (otherwise she worsens her position). By the time he completes the $2k-1$ split, the rightmost box will be empty. If Bob cannot win, than for any positive integer $k < 60$ there are at least $60-2k+1$ boxes contain more than $k$ (and obviously each box has at least one pebble); so we need at least $60+59+57+ \cdots + 1 = 960$ pebbles.
06.08.2022 16:15
The answer is $31+30+\cdots+2+1+2+\cdots+30=960$. After Bob moves "on $k$", Alice can either choose to "add left/subtract right" or "add right/subtract left". The meanings of these definitions should be obvious. For a construction: let the boxes contain $(31,30,\ldots,2,1,2,\ldots,30)$ pebbles after distribution, so $B_{31}=1$. Alice will employ the following strategy: she keeps track of Bob's moves by writing them down. Initially, if Bob moves on $k \leq 30$, Alice adds right, otherwise she adds left. However, if $k$ is (nonstrictly) less than some previous term $x\geq 31$ that Bob has moved on (so Bob added left on $x$), then Alice adds right and erases both $k$ and $x$ from the list. This effectively cancels out the move on $x$ and then some: if these two moves had never occurred, then the pebble count would be nonstrictly lower everywhere. Similarly, if Bob moves on $k$ is (nonstrictly) greater than some previous term $x \leq 30$ that Bob has moved on, Alice can cancel the two moves out. Thus, if Bob plays optimally, he should either start at $k \leq 30$ and move (strictly) leftwards until he cannot, or start at $k \geq 31$ and move (strictly) rightwards until he cannot. In both cases, it is clear that Bob cannot make a box zero by doing this, so we're done. $\blacksquare$ We now prove that Alice cannot start with less than $960$ pebbles and win. I claim the following: we can start with at most $2n-1$ boxes with pebble count at most $n$. To prove this, ignore anything that starts with pebble count greater than $n$, and thus allow Bob to make a move either on the left of all of the remaining boxes or on the right. Suppose that Alice could win while having $2n$ boxes with pebble count exactly $n$, and renumber these boxes $1,\ldots,2n$. Bob should start by moving on $n$ (so the two groups are $1,\ldots,n$ and $n+1,\ldots,2n$), and WLOG Alice adds left in response. Then Bob moves on $n+1$: if Alice adds right, then the number of pebbles in each box has nonstrictly decreased from our position two moves ago, and Bob moves on $n$ again. Otherwise, Alice adds left and Bob moves on $n+2$ and so on. Formally, if Alice has added left on $n,n+1,\ldots,n+i$ already, Bob moves on $n+i+1$. If Alice also adds left, continue, else Bob goes back one step and moves on $n+i-1$. On one hand, if Alice never adds right, then she removes a pebble from box $2n$ at least $n$ times: once for every number in $\{n,\ldots,2n-1\}$, and thus loses. On the other hand, if Alice at some point adds left, her state is strictly worse than it was two moves ago, since we've removed some (nonzero) number of pebbles. Since we have finitely many pebbles, she cannot stall like this forever without losing, so she must eventually remove $n$ pebbles from box $2n$, which also results in her losing (note that she could also lose by removing $n$ pebbles from box $1$, but these two cases are symmetrical and more or less independent, so we don't consider it separately). To finish, from our claim it follows by induction on $n$ that the sum of the pebble counts among the boxes that start with at most $n$ pebbles (subject only to our claim, and not any other restriction) is $n+(n-1)+\cdots+2+1+2+\cdots+(n-1)+n$: this is clear for $n=1$, and if the claim holds true for some $n-1$, then: We need at least two boxes with $n$ pebbles If we have three (or more) boxes with $n$ pebbles, then we can remove a pebble from a box with $n$: the claim still holds, as we previously had at most $2(n-1)-2$ boxes with at most $n-1$ pebbles, so there are at least $2n+(n-1)+(n-2)+\cdots+2+1+2+\cdots+(n-2)+(n-1)$ pebbles among the boxes with at most $n$ pebbles, as desired. Thus, there are at most $59$ boxes with at most $30$ pebbles in them, which contain at least $30+\cdots+2+1+2+\cdots+30$ pebbles among them, so there are at least $31+30+\cdots+2+1+2+\cdots+30=960$ pebbles in total, as desired. $\blacksquare$
15.10.2022 17:54
We claim that the answer is $n=960=31+30+...+2+1+2+3+...+30$ $(\diamondsuit)$. We say that Alice picks either left or right group. Strategy (Alice). Let Alice distributes all $n\geq 960$ pebbles in a style of $(\diamondsuit)$ (we use exactly $960$ pebbles, other can be ignored). On move when Bob chooses some $k$ for the first time, say that Alice picks right group if $k<31,$ and picks left otherwise. If Bob chooses $k$ for the second time, say that Alice pick group opposite to first time of choosing $k.$ Thus we may assume, that each $1\leq k\leq 59$ was choosed at most once, and this strategy clearly works $\Box$ Strategy (Bob). Lemma. If there are at least $2k$ boxes containing at most $k$ pebbles for some $k\in \mathbb{Z}^+,$ then Bob can force a win. Proof. Let Bob firstly chooses $k$ and WLOG Alice picks left group. Then Bob will consequently choose $k+1,k+2,...,2k-1.$ If on two consecutive moves of Bob Alice responded by picking left and right groups respectively, then as a result there will be the number of pebbles lessen by $2.$ But if Bob has winning strategy for $n=N,$ he also have it for every $n<N,$ so we may suppose that on each move Alice picked left group. Then the number of pebbles in most right box with at most $k$ pebbles was lessening on each move and thus we are done $\Box$ Now by lemma Bob has winning strategy for $n<1+2\cdot 2+2\cdot 3+...+2\cdot 30+31=30+30\cdot 31=960$ $\blacksquare$
05.02.2023 17:08
The answer is $960$ which is achieved by the construction $31,30 \dots 2, 1, 2 \dots, 30$. We'll prove that this works, if Bob moves twice in some place, note that Alice can just reverse the order to negate the effect. Now if Bob fixes the partition at $k \leq 30$, subtract from left and add to right, and if Bob fixes the partition at $k > 30$, do the opposite, in this way a box with $k$ coins will atmost lose $k-1$ coins. Now, other claim, consider the minimal possible arrangement of coins, if $m < 31$, we can atmost have 2 boxes with $m$ coins, it is easy to see this, note that if we have 3 or more boxes with $m$ coins, we can basically make one of them to be 0 easily (you can induct or whatever, its pretty easy to see this) and if one of them doesn't reaches 0, Bob can make Alice reduce the number of coins globally, which is just a contradiction, which just completes the proof for minimality. So, we're done.
11.03.2023 11:25
the latter part is a fakesolve, ignore
29.04.2023 18:30
The answer is $31+30+...+2+1+2+...+28+29+30=960$. for two different "distributions" $A_1,A_2$, we say that $A_1$ is contained in $A_2$ iff for any box there is more pebbles in $A_2$ than those in $A_1$. Throughout the solution I'll work with general $2n$ case. Say that Bob "cuts" at k if he splits the boxes into $B_1,B_2,...,B_k$ and $B_{k+1},B_{k+2},...,B_{2n}$, and Alice "adds/subtracts" left or right as the obvious meaning. Alice Strategy: Alice starts with $n,n-1,...,2,1,2,...,n-1,n,n+1$. We say that a distribution is good if it contains a distribution of the form $k,k-1,...,2,1,2...,2n-k+1$. We claim the following: Claim: Starting with a good distribution, Alice can ensure staying in a good distribution. Proof: we can assume WLOG that the initial distribution is $k,k-1,...,2,1,2...,2n-k+1$. Assume WLOG that Bob cuts at $l\geq k$, of course Alice will add left, hence the following distribution is contained in $k+1,k,...,2,1,2,...,2n-k-1,2n-k$ and the claim is proved. (if the distribution was $2n,2n-1,...,1$ then assume WLOG it is $1,2,...,2n$ then continue as above) . $\square$ Bob Strategy: Claim: If we start with a distribution contained in $n,n,...,n,n$ then Bob can win.
in a distribution before two steps. So Bob cuts at $l-1$ and completes cutting to the right as nothing happens. if Alice keeps adding to the right then Bob repeats that process until one box becomes empty (if $l=n+1$ then notice that Bob maybe will cut to the left instead of the right, which doesn't affect the process). $\square$ Back to our $2n$ boxes, we proved that Bob can win if the distribution is contained in $n,n,...,n$ distribution, hence to prevent Bob from winning one box should contain at least $n+1$ Now burn this box, from the remaining boxes one box should contain at least $n$, keep burning boxes until one box is left which contains at least $1$. Hence we need at least $(n+1)+n+n+(n-1)+(n-1)+...+2+2+1=n(n+2)$. $\blacksquare$
24.01.2024 06:25
I claim the answer is $960$ achievable with the construction $31, 30, \dots, 2, 1, 2, \dots, 30$. Alice: Notice that if Bob ever picks the same $k$ twice, then Alice will add to the opposite side she added the first time. So WLOG we can assume that every $k$ is picked at most once. Now, for any sequence of these $k$, Alice will add to the left if $k \ge 31$ and add to the left if $k \le 30$. Now, this wins since box $i$ will be operated at most $\text{max}(31 - i, i - 31)$ times. Bob: AFTSOC that the minimal configuration has $n < 960$ stones. Now notice that Alice must add stones to the left if $k \le 29$ and add stones to the right if $k \ge 31$. Otherwise, it would contradict the minimality of the configuration. WLOG that Alice adds stones to the left if $k = 30$. Now start with $k = 30$, and then pick $k = 29$. Now if she adds to the right for $k= 29$, then we have the original configuration but with two stones removed, contradiction. Now if for some $m < 30$, Alice adds to the right for $m$ but to the left for $m+1$, then taking the original configuration but with two stones removed from box $m$. This will contradict the minimality of $n$. This is because Bob can choose $m + 2, \dots, 30$ and if Alice decides to add to the right for any of these moves this just deletes two stones and we just continue the process of "undoing" the moves until we reach box $30$. So we get that there must be $31 + 30 + \dots + 2$ stones in the first $30$ boxes and by symmetry at least $2 + 3 + \dots 30$ in the last $29$ boxes which gives the bound.
03.05.2024 19:35
Answer: The minimum required $n$ is $31 + 30 + 29 + \dots + 1 + 2 + \dots + 30 = 960$. We say that Bob makes a $k-$chop if he splits the boxes into $\{B_1, B_2, \dots, B_k\}$, $\{B_{k+1}, B_{k+2}, \dots, B_{60}\}$ Sufficiency: We'll show that the configuration $(31, 30, 29, \dots, 1, 2, \dots, 30)$ works. If Bob did $k$-chop twice, then Alice just need to do in the opposite way and the two chops cancel out. Thus, we may assume Bob will do $k$-chops at most $1$. Assume Bob did $k$-chop. If $k \le 30$, Alice adds right and subtracts left, else Alice adds left and subtracts right. It's clear that the above strategy works. Necessity: Say that one configuration is weaker than another if, for every box, that box contains less or equal number of pebbles than other one. Assume there is some minimal $n$. Since Alice can prevent from creating $0$, so there exists a positive integer $a$ such that, for every moment and for each box, the number of pebbles in that box is at least $a$. We may assume that at some point, there exists a box that contains exactly $a$ pebbles. Since we can't have $a-1$ pebbles in any box, the part that includes a box that has $a$ pebbles must be added and other part must be subtracted. This implies that $a$ has exactly same property as $1$, so we may assume $a = 1$. Now, assume at some point, we get a configuration $(b_{59-k}, b_{58-k}, \dots, b_1, 1, a_1, a_2, \dots, a_k)$. Then, we'll prove that $a_i, b_i \ge i + 1$ for all $i$, which immediately implies the necessity part. We only have to prove $a_i \ge i + 1$ as the other one is exactly same. Now Bob will do $60-k, 61-k, \dots$ chops. Consider the consecutive rounds. Suppose that in the first round, Bod made a $k$-chop and Alice added the left group, and the second round, Bob makes $k+1$-chop. Then, we may assume Alice again adds the left group, otherwise we will obtain a weaker configuration than previous one. Therefore, in the $59-k+i$-chop, Alice adds left group, which means that after $59-k+i$-chop, $a_i$ becomes $a_i-i$. Since $a_i-i \ge 1$, which implies $a_i \ge i+1$. Hence, the total number of pebbles must be at least $(60-k) + (59-k) + \dots + 2 + 1 + 2 + \dots + k+1 \ge 31 + \dots + 2 + 1 + 2 + \dots + 30 = 960$, as needed. $\blacksquare$
06.06.2024 11:29
The answer is $960$. Construction: \[ 31, 30, \dots, 2, 1, 2, \dots, 30 \]If Bob splits the boxes at the same place twice, then Alice can just do the reverse of what she did the first time and there is no change, so WLOG suppose Bob only divides the boxes at each place once. Alice's strategy is to add pebbles such that the box that starts with one pebble always increases. Then a box starting with $k$ pebbles will only decrease at most $k-1$ times, thus no box will be empty. Proof that $n \geq 960$: Claim: Any set of $2k$ boxes must contain a box with $\geq 2k+1$ pebbles. Proof. We ignore all other boxes. First, split the boxes after the $k$th box. WLOG, suppose Alice then adds to the boxes on the right. Next, split the boxes after the $k-1$th box, then the $k-2$th box, etc. If Alice ever adds pebbles to the left, then we are in the same position as two moves ago but two pebbles less. Then repeat the process starting at the $k$th box. Since the number of pebbles always decreases, we will eventually have an empty box. So assume Alice always adds pebbles to the right. Then the first box will be decreased by $k$ pebbles. Since it must be nonempty, it must have at least $2k+1$ pebbles. In the $60$ boxes, one must have $31$ pebbles. Then out of the other boxes two must have $30$ pebbles, etc. Therefore, there must be at least \[ 31 + 2\cdot 30 + 2 \cdot 29 + \dots + 2 \cdot 2 + 1 = 960 \]pebbles.