Moving bricks into piles

Question

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
  # Start with all bricks in pile 0.
  counts = [0] * piles
  counts[0] = 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)

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