On 5/25/06, David Wilson <davidwwilson@comcast.net> wrote:
In the n-plate Towers of Hanoi problem, consider the fixed base of each peg to be plate 0, and number the largest through smallest movable plates 1 through n. In the solution of the problem, how many times is plate p placed on top of plate q (0 <= p,q <= n)?
I shall adopt the more rational numbering system 0 = smallest, ..., n-1 = largest disc, n = lefthand, n+1 = central, n+2 = righthand pin. With this convention denote by f(p, q, n) the number of moves of disc/plate p onto q during transfer of n discs from pin n to n+2. By the classical ToH rule, f(p, q, n) = 0 for p >= q; and obviously, f(p, q, n) = 0 for p > n-1 or q > n+2. The well-known inductive, minimum time, and [barring repeated positions] unique, strategy transferring n discs from pin a to c via b is: (1) transfer n-1 discs from a to b via c; (2) shift disc n-1 from a to c (3) transfer n-1 discs from b to c via a. By examination with a = n, b = n+1, c = n+2: for n > 0, 0 <= p,q < n-1, f(p, q, n) = 2 f(p, q, n-1); f(p, n+2, n) = f(p, n, n-1); f(p, n+1, n) = f(p, n+1, n-1) + f(p, n-1, n-1); f(p, n, n) = f(p, n, n-1); f(p, n-1, n) = f(p, n-1, n-1) + f(p, n+1, n-1); and for n > 0, q >= 0, f(n-1,n+2,n) = 1; f(n-1,q,n) = 0 for q <> n+2; f(p, q, n) = 0 for p > n-1 or q > n+2. This gives f(p, q, n) inductively for natural p,q,n. DWW's original function may now be recovered via a simple linear transformation. Inspection of the table of results suggests the almost-tidy explicit (p-q odd): f(p, q, n) = [2^(nod-(p+q+3)/2)] for q <= n; = [2^(nod-(p+q+1)/2)] for q = n+1,n+2, and p <> n-1; = 1 for p = n-1 and q = n+2. Perhaps some Trojan can be bothered to verify that this satisfies the recursion; I'm afraid I haven't the time right now. Nice problem! Fred Lunnon