Moving bricks into piles

Suppose we have $k$ piles, into which we would like to distribute $n$ bricks. Initially, all $n$ bricks are stacked in pile $1$. A move consists of moving one brick from pile $i$ to pile $j$, $1\le i,j\le k$. A move is valid only if $$|i| > |j|+1$$ where $|\cdot|$ denotes the number of bricks in the pile. So to put the validity condition another way, a move is valid only when pile $i$ has at least as many bricks as pile $j$, both before and after the move.

Let $\phi(n,k)$ be the maximum number of valid moves that can be made (before the piles "stabilize"). It is easy to code up a dynamic programming algorithm to compute $\phi(n,k)$. My question is if there is a more direct way to compute it.

Note that for $k>n$, $\phi(n,k) = \phi(n,n)$. So we can arrange the values $\phi(n,k)$ in a Pascal-like triangle, $$\begin{matrix} &&&&&1\\ &&&&1&&2\\ &&&2&&3&&4\\ &&2&&4&&5&&6\\ &3&&5&&6&&7&&8\\ 3&&6&&8&&9&&10&&11 \end{matrix}$$

Here, the value in row $u$ and column $v$ is $\phi(u+1, v+1)$. That is, from row $3$, column $2$, we see $\phi(4,3)=3$.

This triangle is interesting: The left-most major diagonal is just $\lfloor n/2\rfloor$, and the right-most major diagonal is this sequence. It also seems that each "diamond" $$\begin{matrix} &a&\\ b&&c\\ &d&\end{matrix}$$ almost satisfies the property $a+d=b+c$ (from what I've calculated, this is always exact, or one-off, but that's purely anecdotal).

Is there a direct formula for $\phi(n,k)$? Connections of this triangle to other identities are also most welcome.

EDIT: Algorithm for computing the triangle / $\phi(n,k)$:

def phi(bricks, piles, debug=False):

if piles <= 1:
return 0

moves = 0
counts =  * piles
counts = bricks

while max(counts) - min(counts) > 1:
# Remove brick from pile with most bricks.
current = 0
for idx, count in enumerate(counts):
if count > counts[current]:
current = idx
counts[current] -= 1
moves += 1
# Find leftmost pile that can take a brick from pile current.
i = next(i for i,count in enumerate(counts[current:])
if counts[current] > count)
i += current
if debug:
print('{}. Moved brick from pile {} to pile {}'.format(moves, current, i))
# Count how many consecutive moves we can make after that first move
# from pile current.
while i < piles-1 and counts[i] > counts[i+1]:
moves += 1
if debug:
print('{}. Moved brick from pile {} to pile {}'.format(moves, i, i+1))
i += 1
# Put brick in final resting place.
counts[min(piles-1, i)] += 1
if debug:
print(counts)

return moves

def print_triangle(rows):
for row, bricks in enumerate(range(1, rows+1)):
entries = [' {:2d} '.format(phi(bricks+1, piles+1))
for piles in range(1, bricks+1)]
row_string = ' ' * 2*(rows - row)
row_string += ''.join(entries)
print(row_string)

• Can you describe your algorithm for computing $\phi(n,k)$ so we don't have to derive it? – Ross Millikan Dec 14 '16 at 15:51
• @RossMillikan: Sure, I will edit it in tonight, after work. – Steve D Dec 14 '16 at 19:16
• @RossMillikan: Got sidetracked yesterday, but I just added the Python code for phi / generating the triangle. – Steve D Dec 15 '16 at 21:02
• I am not understanding the code correctly. If we want to compute $\phi(7,7)$ it seems to start by moving three bricks from pile 0,but I am not sure it leaves them all in pile 1 because of the remark about final resting place. If so, it still wants to take a brick out of pile 0 as that is the largest, but it can't go on 1 unless you take some out of 1 first. I agree with the final result of $11$, but don't know how the program gets there. My $11$ moves are $0-1,0-1,0-1,1-2,0-1,1-2,2-3,1-4,0-2,0-5,2-6$ though other orders work as well – Ross Millikan Dec 16 '16 at 13:20
• @RossMillikan: If you pass a debug=True argument to the phi function, it will print what moves it is making. [It is a little hard to go through it manually, because it is not actually placing the brick from one pile to another: it takes from the max pile, then adds it to the final resting place, which might account for more than one move.] – Steve D Dec 16 '16 at 16:39

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$).

• I also thought that $\phi(n,k) = k-1 + \phi(k-1,k-1) + \phi(n-k,k)$ for $k \le \lfloor n/2\rfloor$, but this is false: in most cases, $\phi(n,k)$ is bigger (it is always $\ge$, but this is not so interesting). – zhoraster Dec 14 '16 at 15:06