Example of operation; For example, let $n=4$, and $A_1, A_2, A_3, A_4$ has $2, 6, 0, 4$ pebbles each. Then Alice can pick box $A_1$ and divide it's pebbles into $(1, 0, 1, 0)$, and put it into boxes one by one so that $A_1, A_2, A_3, A_4$ has $1, 6, 1, 4$ pebbles each.

Any ideas?

excellent idea szjzc2018 wrote:

$jzc tql !!!!$

The answer is $3n-4(n\geq 3)$ The equailty is reached in (3,3,...,3). Define M=max($a_1$,$a_2$,...,$a_n$).Call a situation "good",if one can make a series of moves s.t. (1)After each move,M strictly increases(2)At last,the second-largest number $\ge n+1$ Define S=1 if a situation is good,otherwise S=0. All we need to prove is that after each move (M+S) at most increases by 1. Noticing that M at most increases by 2,so we need to prove that(1)if M+=2,then S-=1(2)if M+=1,then cannot have S+=1 __by jzc

For completeness: The answer is $3n-4$, achieved by $(a_1,\cdots,a_n)=(3,\cdots,3)$ only. In all parts of the proof, $A_n$ is the pile where all stones go in the end. This means $a_n=\max\{a_1,\cdots,a_n\}$ at all times. Therefore, $a_n$ always receives one stone or two stones; for it to receive three stones $a_j\ge 2n+1$ for some $j\ne n$, which means $a_j+a_n\ge 4n\ge 3n \ge \sum\limits_{k=1}^n a_k$, contradiction! \subsection{$f(3,3,\cdots,3)\le 3n-4$} We consider the following construction: \begin{itemize} \item Use $n-3$ operations, for each $i\in \{1,\cdots,n-3\}$, toggle $A_i$ and give 1 stone to $A_{n-2}, A_{n-1}, A_n$. I have $a_1=\cdots=a_{n-3}=0, a_{n-2}=a_{n-1}=a_n=n$. \item $A_{n-2}$ gives a stone to every pile so we have $a_1=\cdots=a_{n-2}=1, a_{n-1}=a_{n}=n+1$. \item $A_{n-1}$ gives 2 stones to $A_n$ and 1 stone to every other pile. Now, $a_1=\cdots=a_{n-2}=2, a_{n-1}=1, a_n=n+3$ Now each move gives one stone to $a_n$, so we need another $3n-(n+3)=2n-3$ moves. In total we have made $2n-3 + n-1=3n-4$ moves. \end{itemize} \subsection{$f(a_1,\cdots,a_n)\le 3n-5 \forall (a_1,\cdots,a_n)\ne (3,\cdots,3)$} There exists $j$ such that $a_j\ge 4$. If $a_j\ge 5$ in the beginning, making sure every move gives at least one stone to $a_j$ implies $f(a_1,\cdots,a_n)\le 3n-5$. Otherwise, $a_j\le 4$ for all $1\le j\le n$. WLOG, $a_n=4$. If we can make sure $a_n$ receives at least one stone in every operation and receives two stones in one operation, we are done. We have $\max\{a_1,\cdots,a_{n-3}\} \in \{3,4\}$. Case 1: $\max\{a_1,\cdots,a_{n-3}\}=3$ The strategy is to have $a_{n-1}$ have $n+1$ stones at one point and have other $a_j$ send stone to both $a_{n-1}$ and $a_n$. If $\max\{a_1,\cdots,a_{n-1}\}=3$ then multiset $\{a_1,\cdots,a_n\}=\{2,3,\cdots,3,4\}$ since $\sum_{j=1}^{n-1} a_j=3(n-1)-1$ and $a_j\le 3$ for all $1\le j\le n-1$. For all $1\le j\le n-2$, Alice clears $A_j$ and gives one stone to $A_{n-1}$ and one to $A_n$. This guarantees $a_{n-1}=n+1$ at some point. Case 2: $\{max\{ a_1,\cdots,a_{n-1}\} = 4$. WLOG $a_{n-1}=4$ and we want $a_{n-1}$ to be incremented $n-3$ times, while $a_n$ is being incremented each time as well. This is sufficient because $a_{n-1}=n+1$ and thus $A_{n-1}$ can give two stones to $a_n$. We have $a_1,a_2,\cdots,a_{n-2} \in [0,4]$ and their sum is $3n-8$. We need to make sure all but one of $1,\cdots,n-2$ gives a stone to $n-1$, which means when they give they must have at least 2 stones. Once $A_j$ has given one stone each to $A_{n-1},A_n$ we marked it. If $a_j$ has more than 2 stones, it gives stones to piles with 0 or 1 stones. We induct on $n$ to show if $a_1+\cdots+a_{n-2}\ge 2(n-2)$ we can give at least $n-3$ stones to $A_{n-1}$. The base case, $n=4$ is checkable by hand. For the inductive step, once $A_j$ gives 2 stones to $A_n,A_{n-1}$, it gives stones to $a_1,\cdots,a_{n-2}$ except for $a_j$, and we can use the process for $\{ a_1,\cdots,a_{n-2} \} \backslash a_j$ to complete our induction. Therefore, we can form a pile $A_{n-1}$ with $n+1$ stones, which gives 2 stones to $A_n$ in one turn, which guarantees $a_n=3n$ with at most $3n-4-1=3n-5$ moves as each move gives at least 1 stone to $A_n$. \subsection{ $f(3,3,\cdots,3)\ge 3n-4$} Assume for contradiction $f(3,\cdots,3)\le 3n-5$. This implies $a_n$ incremented by 2 (at least) twice. Consider the earliest moment when one pile other than $A_n$ first reaches $n+1$ stones and gives two stones to $A_n$. At the moment right before $A_n$ receives two stones, $a_n\ge n+1$. Therefore, after this pile gives off 2 stones to $A_n$, $a_1+a_2+\cdots+a_{n-1}\le 3n-(n+3)=2n-3$ and $a_j\ge 1$ for all $1\le j\le n-1$ Now suppose each pile tries to create another pile of $n+1$ stones among $a_1,\cdots, a_n$. First deal with the case where $a_n$ increases by 1 every turn. Suppose we can make one pile (WLOG $A_{n-1}$) have $n+1$ stones. Each of $A_1,\cdots,A_{n-2}$ can has at most $a_j-1$ stones that can go to other piles because it needs to give one stone to $a_n$ all the time. Therefore, after all of $A_1,\cdots,A_{n-2}$ gives a stone to $A_{n-1}$, $$a_{n-1, \text{final}}\le \sum\limits_{j=1}^{n-2} (a_j-1) + a_{n-1} \le \sum a_i - (n-2) = (2n-3) - (n-2) = n-1$$ Therefore, if we make sure we give one stone to $A_n$ every time, the maximum value $\max\{a_1,\cdots,a_{n-1}\}$ can achieve is $n-1$. For every stone we send to $A_n$, we can send to one of $a_1,\cdots,a_{n-1}$ instead to create a pile of $n+1$ stones. However, every time after the first time I try to create a pile of $n+1$ stones, observe \begin{itemize} \item Each stone not sent to $A_n$ can only contribute at most 1 stone to a candidate pile with $n+1$ stones \item Always sending a stone to $A_n$ produces an upper bound of $n-1$ \end{itemize} Therefore, we need to choose to not add to $A_n$ at least twice, so it will result in a process with strictly more steps as $a_n$ can only increment by at most 2 each time.

milumengxin wrote: The answer is $3n-4(n\geq 3)$ The equailty is reached in (3,3,...,3). Define M=max($a_1$,$a_2$,...,$a_n$).Call a situation "good",if one can make a series of moves s.t. (1)After each move,M strictly increases(2)At last,the second-largest number $\ge n+1$ Define S=1 if a situation is good,otherwise S=0. All we need to prove is that after each move (M+S) at most increases by 1. Noticing that M at most increases by 2,so we need to prove that(1)if M+=2,then S-=1(2)if M+=1,then cannot have S+=1 __by jzc It is exactly the same as my idea.