Moving bricks into piles

Solution 1:

These are some partial results, not fitting into a comment.

For any $n\ge 3$, $\phi(n,3) = n-1$.

Proof Let us show first that $\phi(n,3)\le n-1$.

Suppose at some stage we have piles containing $a_1,a_2,a_3$ bricks (let us denote this position by $(a_1,a_2,a_3)$), $0\le a_1\le a_2\le a_3$ bricks. I claim that there were no more than $2a_1+a_2$ moves. I argue by backward induction on $a_2$ and $a_3$, using $(0,0,n)$ as a base. The previous position was one of $(a_1-1,a_2+1,a_3)$, $(a_1-1,a_2,a_3+1)$, or $(a_1,a_2-1,a_3+1)$. By induction assumption, in the first two cases there were at most $2(a_1-1)+a_2+1 = 2 a_1 + a_2 -1$ prior moves, in the third, at most $2a_1+a_2 -1$ prior moves, yielding the claim.

Now if $3\nmid n$, then the finishing position is $(a_1,a_2,a_3)$, with $a_1<a_3$. Therefore, there were at most $2a_1 + a_2\le a_1+a_2+a_3-1 =n-1$ moves.

If $n=3k$, then the finishing position is either $(a_1,a_2,a_3)$ with $a_1\le a_3 -1$, and we can use the above argument, or $(k,k,k)$. In the latter case, the position before the last move was $(k-1,k,k+1)$, so there were at most $2(k-1) + k = 3k-2$ moves prior the last one.

Now $n-1$ moves can be realized in the following way: $$ (0,0,n)\to (0,1,n-1) \to (0,2,n-2)\to (1,1,n-2) \to (1,2,n-3)\\ \to (1,3,n-4)\to (2,2,n-4)\to (2,3,n-5)\to\dots \to(k,k+1,n-(2k+1)) $$ repeating this until $k= \lfloor n/3\rfloor-1$. So far we have made $$3k+1 = 3(\lfloor n/3\rfloor-1)+1 = 3\lfloor n/3\rfloor-2$$ moves. Now if $n = 3(k+1)$, the position is $(k,k+1,k+2)$, and can make another move. If $n = 3(k+1)+1$, the position is $(k,k+1,k+3)$, so we can make two moves: to $(k,k+2,k+2)$ and $(k+1,k+1,k+2)$. If $n = 3(k+1)+2$, the position is $(k,k+1,k+4)$, so we can make three moves: to $(k,k+2,k+3)$, $(k+1,k+1,k+3)$ and $(k+1,k+2,k+2)$. This finishes the proof.

For $k\ge \lfloor n/2\rfloor$, $\phi(n,k) = \phi(n,n) -(n-k)$.

Proof This follows that from the fact (which I have yet to check) that there is a longest sequence passing through $(0,0,\dots,0,2,2,\dots,2)$ or $(0,0,\dots,0,1,2,2,\dots,2)$ (depending on the parity of $n$).