Problem 4. Angel has a warehouse, which initially contains $100$ piles of $100$ pieces of rubbish each. Each morning, Angel performs exactly one of the following moves: (a) He clears every piece of rubbish from a single pile. (b) He clears one piece of rubbish from each pile. However, every evening, a demon sneaks into the warehouse and performs exactly one of the following moves: (a) He adds one piece of rubbish to each non-empty pile. (b) He creates a new pile with one piece of rubbish. What is the first morning when Angel can guarantee to have cleared all the rubbish from the warehouse?
Problem
Source: Balkan MO Problem 4
Tags: Balkan Mathematics Olympiad
R8kt
08.09.2021 20:46
198. Proof: after first morning there will be 99 groups of 99 trash left. We see that after the demons move and angels move combined we get 3 possible outcomes 1. There is -1 pile 2. There is -1 trash from every piles 3. 1 and 2 combined. Since we have 99 piles and 99 groups and every 2 moves at least 1 of them decreases by 1 ( as soon as someone hits 0 it’s game over) we can see that it takes at most 99*2 - 1 moves. Hence the upper bound is (99*2-1)+1 = 198 Lower bound the first 98 times the devil adds 1 to all groups, and then he always adds a new group. I think this works, but there might be a mistake somewhere.
sbealing
08.09.2021 20:57
This problem is also a UK proposal joint between Sam Bealing (me) and Alexander Betts. Here is the solution we submitted with the problem: The answer is morning $\boxed{2 \times 100-1=199}$. We proceed in two stages: first showing this is achievable and secondly showing that the demon can ensure that there is rubbish left on morning $198$. If the piles have size $\left(x_1,\ldots,x_n\right)$ then define the Angel score to be: $$\textit{Angel score}=-1+\sum_{i=1}^{n}{\min{\{x_i,2\}}}=2 \beta+\alpha-1$$where $\alpha,\beta$ are the number of piles containing $=1$ and $\geq 2$ pieces of rubbish respectively. We claim that Angel requires at most $\max{\{\text{Angel score},1\}}$ days to remove the rubbish. For $\beta=0$, all of the piles have size $1$ so Angel can immediately remove them. We now induct on $(\beta,\alpha)$ in lexicographical order. $\alpha=0$: Let the piles be $\left(x_1,\ldots,x_\beta\right)$ then Angel should remove the $x_{\beta}$ pile leaving $\left(x_1,\ldots,x_{\beta-1}\right)$. The demon can then either leave: $$\left(x_1+1,\ldots,x_{\beta-1}+1\right) \quad \text{or} \quad \left(1,x_{1},\ldots,x_{\beta-1}\right)$$Applying the inductive hypothesis, these require at most $\max{\left\{1,2(\beta-1)-1\right\}}$ and $2(\beta-1)$ days respectively so the Angel will require at most: $$2(\beta-1)+1=2\beta-1=2\beta+\alpha-1$$days to remove the rubbish as needed. $\alpha=1$: Let the piles be $\left(1,x_1,\ldots,x_{\beta}\right)$. The Angel should again remove pile $x_{\beta}$. The demon can leave either: $$\left(2,x_{1}+1,\ldots,x_{\beta-1}+1\right) \quad \text{or} \quad \left(1,1,x_1,\ldots,x_{\beta-1}\right)$$Applying the inductive hypothesis (and $\alpha=0$ case from above) we see these require at most $2\beta-1$ and $2(\beta-1)+2-1=2\beta-1$ days to clear so the Angel can clear the rubbish in at most $2\beta-1+1=2\beta+\alpha-1$ days. $\alpha \geq 2$: Let the piles be $\left(1,\ldots,1,x_1,\ldots,x_{\beta}\right)$ then the Angel should remove 1 from each pile leaving $\left(x_1-1,\ldots,x_{\beta}-1\right)$. The demon can then leave either: $$\left(x_1,\ldots,x_\beta\right) \quad \text{or} \quad \left(1,x_{1}-1,\ldots,x_{\beta}-1\right)$$Applying the inductive hypothesis, the first case requires at most $2\beta-1$ days to clear. For the second case, using the definition of the score, it requires at most: $$-1+1+\sum_{i=1}^{\beta}{\max{\left\{x_{i}-1,2\right\}}} \leq 2 \beta$$Hence the Angel can clear the rubbish in at most: $$2 \beta+1 \leq 2 \beta+\alpha-1 \quad \text{as} \quad \alpha \geq 2$$days which completes the induction. Using the notation from above, we define the Demon score to be: $$\text{Demon score}=\begin{cases} 2 \beta-1 & \alpha=0 \\ 2 \beta & \alpha \geq 1 \end{cases}$$We claim that for $\alpha,\beta$ not both $0$, the demon can ensure that Angel requires $\text{Demon score}$ mornings to clear the rubbish. The base case when $\beta=0$ is clear as the Demon score is $0$. $\alpha=0$: Let the piles be $\left(x_1,\ldots,x_{\beta}\right)$. If Angel removes one from each pile then the demon can just restore the original configuration so WLOG the Angel removes a pile say $x_{\beta}$. Then the demon should add a pile of $1$ leaving the piles $\left(x_1,\ldots,x_{\beta-1},1\right)$ which by the inductive hypothesis takes $2(\beta-1)=2\beta-2$ days to remove so the Angel needs at least $2\beta-2+1=2\beta-1$ days to remove the original piles. $\alpha \geq 1$: Whatever Angel does, the demon should add one to each of the remaining piles. If the Angel removes one from each pile then after the demon's move the number of piles containing $\geq 2$ pieces of rubbish is still $\beta$. If the Angel removes a whole pile, then there will be at least $\beta+\alpha-1 \geq \beta$ piles with $\geq 2$ pieces. So in either case, by the inductive hypothesis, Angel will require at least $2\beta-1$ days to remove the rubbish and hence $2\beta-1+1=2\beta$ days in total completing the induction. In the case of the configuration in the problem, both the Angel and Demon scores are equal to $199$ and hence $199$ days are both necessary and sufficient for Angel to clear all of the rubbish.. Remark: If we let $\alpha,\beta$ as above and define $\gamma=\min{\left\{x_i:x_i \neq 1\right\}}$ (setting $\gamma=1$ if the set is empty). A more detailed analysis shows: $$ \# \text{days required}= \begin{cases} 2 \beta-1 & \alpha=0 \\ 2 \beta & \alpha=1 \\ 2 \beta & \alpha \geq 2 \text{ and } \gamma=2 \\ 2 \beta+1 & \alpha \geq 2 \text{ and } \gamma \geq 3 \end{cases} $$
SnowPanda
14.01.2022 00:45
The answer is the $199$th morning.
Let $x$ be the number of piles of at least $2$ pieces of rubbish, and $y$ the number of piles of $1$ piece of rubbish. Let the score of a position be $s = 2x + y$.
Claim: If $s \geq 2$, then Angel can guarantee that at the end of the day, the score has decreased by at least $1$.
Proof. If $y \leq 1$ then Angel clears a pile of at least $2$ pieces of rubbish; if $y \geq 2$ then he clears one piece from each pile.
In the first case, the position is now $(x - 1, y)$. If the demon then adds one piece to each nonempty pile, the position becomes $(x - 1 + y, 0)$, which means the score has decreased by $2 - y \geq 1$. Meanwhile, if the demon creates a new pile with one piece of rubbish, the position becomes $(x - 1, y + 1)$ and the score has decreased by $1$.
In the second case, the position is now $(x - c, c)$ for some $c \geq 0$. If the demon adds one piece to each nonempty pile, the position becomes $(x, 0)$ and the score has decreased by $y \geq 2$. If the demon creates a new pile with one piece, the position is now $(x - c, c + 1)$ and the score has decreased by $y + c - 1 \geq 1$. $\blacksquare$
The score starts at $200$, so after $198$ days the score is at most $2$, and Angel wins on the $199$th morning.
Claim: The demon can guarantee that at the end of each day, $y \leq 1$ and the score has decreased by at most $1$.
Proof. The demon follows the strategy that if $y \geq 1$ he adds a piece to each pile, while if $y = 0$ he creates a new pile. This guarantees that $y \leq 1$ after his turn; it also increases the score by at least $1$, so in order for the score to decrease by more than $1$, Angel has to decrease the score by more than $2$.
But $y \leq 1$, so the only way this can occur is if Angel clears one piece from each pile, and this turns at least one pile of $2$ pieces into a pile of $1$ piece. In this case the demon's strategy has him add a piece to each pile, which means the position went from $(x, y)$ to $(x, 0)$, and the score decreased by $y \leq 1$. $\blacksquare$
So for $k \leq 198$, at the start of the $k$th day the score is at least $200 - (k - 1) \geq 3$. Since $y \leq 1$ this means there are at least $2$ piles and there is at least one pile of size at least $2$, so Angel cannot win until the $199$th morning.
txc
14.01.2022 14:50
The answer is $199$. Let $(a_1,a_2,\dots,a_n)$ denote the warehouse with $n$ piles of $a_1,a_2,\dots,a_n$ pieces of rubbish respectively. Consider the warehouse on a given afternoon, i.e. the angel has moved but the demon has not. We assign the warehouse a score of $$s(a_1,a_2,\dots,a_n)= \begin{cases} 2n-1 & \text{if } \min\{a_1,a_2,\dots,a_n\}=1 \\ 2n & \text{otherwise.} \end{cases}$$An empty warehouse has a score of zero. We claim that the angel requires as many days to clear the warehouse as the score. It suffices to show: (1) The angel can ensure that the score decreases by at least $1$ each day. (2) The demon can ensure that the score decreases by at most $1$ each day. Let the warehouse $(a_1,a_2,\dots,a_n)$ have score $s>0$. Suppose $s=2n-1$. If the demon does $(a_1+1,a_2+1,\dots,a_n+1)$, the angel can, without loss of generality, get the warehouse to either $s(a_1,a_2,\dots,a_n)=2n-1$ or $s(a_1+1,a_2+1,\dots,a_{n-1}+1)=2n-2$. If the demon does $(a_1,a_2,\dots,a_n,1)$, the angel can remove one piece of rubbish from each pile, which empties at least two piles, leaving a score of at most $2n-2$. Suppose $s=2n$. If the demon does $(a_1+1,a_2+1,\dots,a_n+1)$, the angel can remove a pile, leaving a score of $2n-2$. If the demon does $(a_1,a_2,\dots,a_n,1)$, the angel can, without loss of generality, get the warehouse to either $s(a_1,a_2,\dots,a_n)=2n$, $s(a_1,a_2,\dots,a_{n-1},1)=2n-1$ or $s(a_1-1,a_2-1,\dots,a_n-1)=2n\text{ or }2n-1$. Inspecting the two cases shows that (1) and (2) are true in both cases. After the first morning, the warehouse is either $99$ piles of $100$ or $100$ piles of $99$, with scores $198$ and $200$ respectively. The angel will pick the first option, so a total of $1+198=199$ days are required. $\Box$
simpleK
15.01.2023 13:16
199th.
Call a pile unit if it contains exactly one rubbish piece. Consider $u$ as the number of unit piles while $n$ is the total number of non-empty piles.
Consider the following strategy for Angel:
1) If Angel can clear all the piles he does it. Else,
2) If there is at most one unit pile Angel clears all the rubbish pieces from some non unit pile (he can do this 'cause in the opposite case he does 1) instead of 2)).
3) If there are at least two unit piles Angel clears one piece of rubbish in each pile.
Claim. Using this strategy, Angel decreases the value of $n + u$ by at least 1.
Proof. The 1st kind of Angel's moves obviously makes the sum $n + u$ equals to 0 therefore decreases the expression. The 2nd kind moves decreases this sum exactly by 2 while easy to see that demon can increase it at most by 1 in this case. Finally, the 3rd kind of moves decreases the sum by $u + k$ where $k$ is the number of piles with exactly 2 pieces. However, demon can increase the sum by either $k$ or 1 which is strictly smaller than $u + k$ since $u \geq 2$. $\Box$
It remains to notice that initially $n + u = 200$ and in case when $n + u \leq 2$ Angel wins. It follows he can clear all the piles in at most 199 mornings.
Firstly, make an easy observation that Angel doesn't do worthless moves, i.e. he doesn't clear one piece of rubbish from each pile while there are no unit piles (else, demon add 1 rubbish piece to each pile returning Angel to the previous step) and doesn't clear unit pile (if it is not only one remaining).
Claim. If there are initially $n$ non unit piles and no unit piles demon can "bother" Angel at least $2n - 1$ moves.
Proof. Induct on $n$ where base cases $n = 1, 2$ can be checked by hands.
Suppose, we have proved the claim for all positive integers smaller than $n + 1$. Now, there are $n + 1$ non unit piles. Since our observation before the claim, Angel has to clear all the rubbish pieces from some pile, so next let demon creates one new pile w/ one piece of rubbish. Then:
1) If Angel clears some non unit pile then demon adds one new rubbish piece in each of $n$ piles making them all non unit. From here, we can use induction hypothesis.
2) If Angel clears one rubbish item in each pile then the number of piles decreases by 1 and some of them may become unit. In this case, demon also adds one new rubbish piece in each of $n$ piece and they all become non unit, next hypothesis again.
The strategy for demon in the given problem follows from claim statement for $n = 100$.
Davdav1232
14.12.2024 20:38
Here is a nice proof for the demon's strategy: After the first move, the piles are 99 piles of 100 rubbish. Now we will worsen our situation: We may assume the piles are of size $(100, 99, 98, ..., 2)$. On our move, we will add a pile of $1$ to make the position $(1, 2, ..., 100)$. Claim: to remove the piles $(1, 2, 3, .., n)$, Angel needs at least $2n-2$ moves. We will prove by induction: base cases $n=1, 2$ are trivial. We can observe that no matter what Angel plays the position will become $(1, 2, ..., n-1)$. We'll add 1 to every pile. If Angel takes $1$ away from every pile, we add $1$ to every pile and arrive at the same position. So Angel removes the largest pile, so the position is $(2, .., n-1)$. Now we add a pile of $1$ and arrive at the position $(1, 2, ..., n-1)$ and win by induction. So it takes at least $1+2n-2=2n-1$ moves for Angel to win. Angel strategy: After move $1$ there are $n-1$ piles of more than $1$ rubbish. We claim we can get rid of a pile in $2$ moves. If on one of the $2$ moves the demon didn't add a pile, we just clear $2$ piles and the demon adds at most $1$. If he added $2$ piles, on our second move we will clear both of them. So we cleared at least $3$ piles and he added $2$, so we removed a pile. Do this $n-1$ times and win in $1+2n-2=2n-1$ moves.