qwedsazxc wrote: $$\text{(Procedure) Chosen two positive integers }1\geq i\geq j\geq n\text{, we add one ball each to the boxes }B_k\text{ that }i\geq k\geq j.$$ Do you mean this? $$\text{(Procedure) Chosen two positive integers }1\leqslant i\leqslant j\leqslant n\text{, we add one ball each to the boxes }B_k\text{ that }i\leqslant k\leqslant j.$$

PhilippineMonkey wrote: qwedsazxc wrote: $$\text{(Procedure) Chosen two positive integers }1\geq i\geq j\geq n\text{, we add one ball each to the boxes }B_k\text{ that }i\geq k\geq j.$$ Do you mean this? $$\text{(Procedure) Chosen two positive integers }1\leqslant i\leqslant j\leqslant n\text{, we add one ball each to the boxes }B_k\text{ that }i\leqslant k\leqslant j.$$ Oops, I made a mistake. I fixed it.

I think the answer is $$f_{\max}(x_1,\ldots ,x_n)=\begin{cases}\frac{2n}{3}+1 & n\equiv 0\pmod 3\\ \frac{2n+1}{3}+1 & n\equiv 1\pmod 3\\ \frac{2n-1}{3}+1 & n\equiv 2\pmod 3\end{cases}$$The construction should be similar to this form $'120120120\cdots '$.

PhilippineMonkey wrote: I think the answer is $$f_{\max}(x_1,\ldots ,x_n)=\begin{cases}\frac{2n}{3}+1 & n\equiv 0\pmod 3\\ \frac{2n+1}{3}+1 & n\equiv 1\pmod 3\\ \frac{2n-1}{3}+1 & n\equiv 2\pmod 3\end{cases}$$The construction should be similar to this form $'120120120\cdots '$. That's correct. It's floor((2n+4)/3), if I solved correctly at the test.

Does anyone have a solution?

This is my aftertest solution.. couldnt solve it during the test and I solved only the upper part. The answer is $(n+1)-[\frac{n+1}{3}]$, and we will solve this by induction. In small $n$, it is trivial. Now, in $n=n$, Firstly, we can assume $x_i \in {0,1,2}$. The sequence of $x_i$ will be like 12020212010201101201201. In this 'code', we can find the parts where it can be deleted by few procedures. Some of them are this: (* denotes the start of the code) 00, 11, 22 (can be reduced to 0,1,2 : 0 procedure, 1 out) 101, 212, 020 (by adding 1 to the middle, can be reduced to 1,2,0 : 1 procedure, 2out) (*)xx0 ($x_3 =0$) (can make the first two into 0 by applying n=2 : 2 procedure, 3 out) (*)20 (add 1 to 2 : 1 procedure, 2 out) (*)0 (delete the 0 : 0 procedure, 1 out) So in these cases, $m$ numbers can be reduced using less than $\frac{2}{3} m$ procedures, therefore number of procedure required is less than $(n+1)-[\frac{n+1}{3}]$ by induction condition. It is enough to prove when in the code there is none of the above. If it start with 2, 21->210->x 212->x 20->x If it starts with 0, 0->x If it starts with 1, 10->101->x 102->1021->10210->10210210210... (A) 12->120->x 121->1210->1210210210....... (B) In both (A), (B), the right end of the code isnt (A) nor (B), so contradiction. It means that there is no case. Therefore $f_{max} \le (n+1)-[\frac{n+1}{3}]$ and the equivalent case has to be repeat of 120 or 210, but I dont know why in this case $(n+1)-[\frac{n+1}{3}]$ procedure is needed.

chrono223 wrote: This is my aftertest solution.. couldnt solve it during the test and I solved only the upper part. The answer is $(n+1)-[\frac{n+1}{3}]$, and we will solve this by induction. In small $n$, it is trivial. Now, in $n=n$, Firstly, we can assume $x_i \in {0,1,2}$. The sequence of $x_i$ will be like 12020212010201101201201. In this 'code', we can find the parts where it can be deleted by few procedures. Some of them are this: (* denotes the start of the code) 00, 11, 22 (can be reduced to 0,1,2 : 0 procedure, 1 out) 101, 212, 020 (by adding 1 to the middle, can be reduced to 1,2,0 : 1 procedure, 2out) (*)xx0 ($x_3 =0$) (can make the first two into 0 by applying n=2 : 2 procedure, 3 out) (*)20 (add 1 to 2 : 1 procedure, 2 out) (*)0 (delete the 0 : 0 procedure, 1 out) So in these cases, $m$ numbers can be reduced using less than $\frac{2}{3} m$ procedures, therefore number of procedure required is less than $(n+1)-[\frac{n+1}{3}]$ by induction condition. It is enough to prove when in the code there is none of the above. If it start with 2, 21->210->x 212->x 20->x If it starts with 0, 0->x If it starts with 1, 10->101->x 102->1021->10210->10210210210... (A) 12->120->x 121->1210->1210210210....... (B) In both (A), (B), the right end of the code isnt (A) nor (B), so contradiction. It means that there is no case. Therefore $f_{max} \le (n+1)-[\frac{n+1}{3}]$ and the equivalent case has to be repeat of 120 or 210, but I dont know why in this case $(n+1)-[\frac{n+1}{3}]$ procedure is needed. I got the upper bound during the test but I could never get the lower bound. Still, thanks for the nicely written proof for the upper bound.

Consider the numbers $\pmod3$. Suppose the maximum number of operations we need is $k$. The answer is as follows: For $n=3m, k=2m+1$. For $n=3m+1, k=2m+2$. For $n=3m+2, k=2m+2$. Construction: Suppose the number of $0$s, $1$s, $2$s be $A$, $B$, $C$. We consider 3 possible algorithms: Algorithm 1: Change the $B$ $1$s to $2$s. Now, change the consecutive subsequences of $2$s into $0$s. The first step takes $B$ moves, while the second takes $\le A+1$ (Since there $A$ $0$s, there are at most $A+1$ consecutive subsequences of $2$s). Hence, this procedure finishes in $\boxed{A+B+1}$ moves maximum. Algorithm 2: Change the $C$ $2$s into $0$s. Now, change the consecutive subsequences of $0$s into $1$s. Finally, change all $1$s into $0$s. The first step takes $C$ moves, while the second takes $\le B-1$ (since we can ignore the $0$s at the ends). The last step takes $2$, so in total we finish in $\boxed{C+B+1}$ moves maximum. Algorithm 3: Change the $A$ $0$s into $1$s. Now, change the consecutive subsequences of $1$s into $2$s. Finally, change all $2$s into $1$s. The first step takes $A$ moves, while the second takes $\le C+1$, and the last takes $1$ for a total of $\boxed{A+C+2}$. Hence, it suffices to show that one of $A+B+1,B+C+1,A+C+2$ is $\le k$. Note their sum is $2(A+B+C)+4=2n+4\le 3k+2$, so we are done by pigeonhole. Bound: For $n=3m+1$, consider $|1|2|0|1|2|0|\cdots |1|2|0|1|$. For each range, we consider the two $|$ it is made of, and put an $S$ at the starting $|$ and an $E$ at the ending $|$. If we have an $S$ and an $E$ on the same $|$, we can merge the two ranges. If we have $3$ $S$s on the same $|$, we can change the ranges $(a,b),(a,c),(a,d)$ with $(b+1,c),(b+1,d)$. The same is true for $3$ $E$s. Hence, assume each $|$ has at most $2$ letters, which are the same. Note if there is an $S$ at a $|$, there must be two of them. This is because the number on the right of the $|$ is one larger than the number on the left, $\pmod3$. The only time this difference changes is when a range starts at that position, and since it must increase by at least two, there must be at least $2$ $S$s. Also, every position must have a letter by the same logic, and the last $|$ must have $2$ $E$s. Now suppose on the contrary that there are $\le 2m+1$ ranges, then there are $2m+1$ $E$s, hence at most $2m$ $|$s have $E$s (the last $|$ has $2$.) Hence at least $3m+2-2m=m+2$ $|$s have $S$s, and so there are at least $2m+4$ $S$s, a contradiction. For $n=3m+2$, the same proof suffices (add a $0$ at the front, if it is used it is used at least thrice, contradiction). For $n=3m$, consider $|1|0|1|2|0|1|2|0|\cdots |1|2|0|1|$. The logic is similar. (If there are $\le 2m$ ranges, then there are $\le 2m-1$ $|$s with $E$s, so $\ge m+1$ $|$ with $S$s, so at least $2m+1$ $S$s [all must have $\ge 2$ except the $1|0$, contradiction).

The answer is $\lfloor \tfrac{2n+4}{3}\rfloor$. Of course, consider everything mod $3$. We first prove that $\lfloor \tfrac{2n+4}{3} \rfloor$ or less is always achievable. Let there be $x$ zeroes, $y$ ones, and $z$ twos. Also, for $i \in \{0,1,2\}$, let $r(i)$ equal $-1$ if both $x_1$ and $x_n$ equal $i$, $0$ if exactly one of $x_1$ and $x_n$ are $i$, and $1$ otherwise, so clearly $r(0)+r(1)+r(2)=1$. Now consider the following possible algorithms: Replace every $0$ with a $1$ (by adding $1$ to intervals of size $1$), which takes $x$ turns. Then consider each interval of $1$'s, of which there are $z+r(2)$, and turn them all to $2$. Finally, add $1$ to the entire interval of $n$ boxes. This takes $x+z+r(2)+1$ turns. Replace every $1$ with a $2$, which takes $y$ turns. Then consider each interval of $2$'s, of which there are $x+r(0)$, and turn them all to $0$. This takes $x+y+r(0)$ turns. Replace every $2$ with a $0$, which takes $z$ turns. Then consider each interval of $0$'s, of which there are $y+r(1)$, and turn them all to $1$. Finally, add one twice to the entire interval of $n$ boxes. This takes $y+z+r(1)+2$ turns. The sum of the number of turns taken across all three procedures is $2(x+y+z)+3+r(1)+r(2)+r(3)=2n+4$, so one of these procedures must take at most $\lfloor \tfrac{2n+4}{3} \rfloor$ moves. We now prove that if we take $x_1,\ldots,x_n$ equal to the first $n$ terms of the sequence $102102102\ldots$, then $f$ will in fact attain this value of $\lfloor \tfrac{2n+4}{3}\rfloor$. In fact, we will prove the stronger claim that if we make at least $3k$ moves (where $k$ is a nonnegative integer) which add a ball to box $n$, then we require at least $\lfloor \tfrac{2n+4}{3}\rfloor+k$ total moves. This is by induction on $n$ (with $k$ varying freely), with $n=1$ being obvious. There are three cases for the inductive step: $3m \to 3m+1$. Since $x_{3m+1}=1$, if we have at least $3k$ moves on box $3m+1$, then we actually need at least $3k+2$. If $a$ of these are only on box $3m+1$, then at least $3k+2-a$ will also contain box $3m$. The key idea here is that the number of total number of moves containing box $3m$ must be $1 \pmod{3}$. With this in mind, if $a=0$ then we need at least $3k+4$ boxes containing box $3m$, so inductive hypothesis on the first $3m$ boxes finishes since we need at least $3m+k+1$ moves. Otherwise, by inductive hypothesis on the $3m$ boxes we need at least $3m+k+\lfloor \tfrac{2-a}{3}\rfloor+a$, which is at least $3m+1+k$ as well, since $a\geq 1$. $3m+1 \to 3m+2$. This case is, of course, similar. Since $x_{3m+2}=0$, consider when we have at least $3k$ moves, $a$ of which are only on box $3m+2$. By breaking into the cases of $a=0$ and $a>0$ and using the inductive hypothesis we obtain the desired bound. $3m+2 \to 3m+3$. This case is also similar: since $x_{3m+3}=2$, consider when we have at least $3k+1$ moves, $a$ of which are only on box $3m+3$. By breaking into the cases of $a=0$ and $a>0$ and using the inductive hypothesis we also obtain the desired bound. The desired bound is just the case of $k=0$, so we are in fact done. $\blacksquare$ Remark: It feels like most of the time these types of problems (I don't know exactly what "these types" mean but I sort of know when I see them) are somewhat routine for the experienced contestant. In particular, some form of casework-based induction, perhaps combined with ad hoc "smoothing"-type arguments, usually solve the entire problem. Therefore, I was pleasantly surprised to find out that the bound was extremely clean and not based on induction at all. I found the proof of the construction somewhat routine, although the addition of the "$3k$ term" is something I don't specifically remember seeing that technique. I found it fairly well-motivated by considering how constructions for $n$ can be extended to constructions for $n+1$ (which goes the other way too, thus providing a bound), and realizing where the typical argument fails.