Let $k$ be a positive integer. Determine the least positive integer $n$, with $n\geq k+1$, for which the game below can be played indefinitely: Consider $n$ boxes, labelled $b_1,b_2,...,b_n$. For each index $i$, box $b_i$ contains exactly $i$ coins. At each step, the following three substeps are performed in order: (1) Choose $k+1$ boxes; (2) Of these $k+1$ boxes, choose $k$ and remove at least half of the coins from each, and add to the remaining box, if labelled $b_i$, a number of $i$ coins. (3) If one of the boxes is left empty, the game ends; otherwise, go to the next step. Proposed by Demetres Christofides, Cyprus
Problem
Source: Problem 3, BMO 2020
Tags: combinatorics, BMO
grupyorum
01.11.2020 20:10
As soon as I saw the problem, knew it was proposed by Demetres
green_leaf
01.11.2020 21:32
dangerousliri wrote: (2) and add to the remaining box, if labelled $b_i$, a number of coins/ Can you clarify what this means? I don't think I have understood this correctly. Does it mean that add any number of coins to the box that is not chosen?
steppewolf
01.11.2020 21:53
@above It means if the box not chosen has label $b_{i}$, then add $i$ coins to that box. There is a part missing.
mastermind.hk16
01.11.2020 21:54
I claim that the answer is $2^k +k-1$. First, let's show $n \geq 2^k+k-1$. Suppose $n < 2^k+k-1$. And if $2^r \le a < 2^{r+1}$ define $f(a)=r$. It's quite clear that $f$ counts the maximum number of steps a box is away from $1$, if I keep removing from that box. Consider $S = f(b_1) + f(b_2) + \dots + f(b_n)$. See that at every step, first $S$ decreases by at least $k$ when you remove from $k$ boxes but then it increases by $f(b_m+m) - f(b_m)$ where $B_m$ is the box where you add $m$ coins. So after some point we need (or else $S$ will decrease to zero and the game ends), $$f(b_m + m) -f(b_m) \ge k$$The maximum change comes when $b_m=1$. So $f(m+1) - f(1) = f(m+1) \ge k$ so $m \ge 2^k-1$. Also, we cannot have $f(b_m+m) -f(b_m) > k$ since $2^k+k-1< 2^{k+1}$. If the game is to continue indefinitely we need to keep choosing a box with index $j \ge 2^k-1$ after some point $(*)$. There are at most $k$ such boxes. Since each time one of these boxes occupy the 'getting' spot, we keep removing from boxes with index $<2^k-1$ indefinitely. Moreover, these boxes never get more stones by $(*)$. So at some point one of them is empty. Now, let's construct for $n=2^k+k-1$. Set $b_{2^{k}-1}, \dots b_{2^k+k-2} = (1,2,2^2, \dots , 2^{k-1})$ and add to box 1. Now $f(b_{2^k-1+i}) = i$. So repeat the following steps indefinitely; Step $1$. Halve boxes $b_{2^k-1+i}$ where $i \ne 0$ and add to box $b_{2^k-1}$. Step $2$. Halve boxes $b_{2^k-1+i}$ where $i \ne 1$ and add to box $b_{2^k}$. $$\vdots$$Step $k+1$. Halve boxes $b_{2^k-1+i}$ where $i \ne k$ and add to box $b_{2^k+k-1}$.
SnowPanda
16.01.2022 05:17
The answer is $n = 2^k + k - 1$. To show that this $n$ works, let $a_0 \leq a_1 \leq \cdots \leq a_k$ be the numbers of coins in the $k + 1$ largest-indexed boxes, in sorted order, and call a position full if $a_i \geq 2^i$ for each $0 \leq i \leq k$. Then the initial position is full, and if we add to the box with $a_0$ coins (whose index is at least $2^k - 1$) and subtract from the other $k$, fullness is preserved.
Now we show that $n < 2^k + k - 1$ does not work.
For any positive integer $n$, let $f(n)$ be the greatest nonnegative integer $r$ with $2^r \leq n$. If box $i$ has $c_i$ coins, let the score of the position be $\sum f(c_i)$ over all boxes $i$.
Claim: $f(x + y - 1) \leq f(x) + f(y)$.
Proof. If $x$ or $y$ is $1$ this is clearly true. Otherwise let $f(x) = r$ and $f(y) = s$, with $r \geq s \geq 1$. Then \[x + y - 1 < 2^{r + 1} + 2^{s + 1} - 1 < 2^{r + 1} + 2^{r + 1} = 2^{r + 2} \leq 2^{r + s + 1},\]which means $f(x + y - 1) \leq r + s$. $\blacksquare$
If we remove at least half the coins from box $i$, this subtracts at least $1$ from $f(c_i)$. Meanwhile, if we add $i$ coins to box $i$, by the above claim this adds at most $f(i + 1) \leq k$ coins to box $i$, and equality holds for at most $k$ values of $i$. So the score can never increase in a step, and there are at most $k$ boxes (chosen as the box being added to) for which the score remains the same.
The score is always a nonnegative integer, so after some point we must only add to one of those $k$ boxes. But then we must subtract from one of the remaining $n - k$ boxes, which means the number of coins in those $n - k$ boxes strictly decreases every step, contradiction.