10
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Can you describe your algorithm for computing $\phi(n,k)$ so we don't have to derive it? $\endgroup$ – Ross Millikan Dec 14 '16 at 15:51
  • $\begingroup$ @RossMillikan: Sure, I will edit it in tonight, after work. $\endgroup$ – Steve D Dec 14 '16 at 19:16
  • $\begingroup$ @RossMillikan: Got sidetracked yesterday, but I just added the Python code for phi / generating the triangle. $\endgroup$ – Steve D Dec 15 '16 at 21:02
  • $\begingroup$ 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 $\endgroup$ – Ross Millikan Dec 16 '16 at 13:20
  • $\begingroup$ @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.] $\endgroup$ – Steve D Dec 16 '16 at 16:39
3
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – zhoraster Dec 14 '16 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.