[math-fun] Tower of Hanoi problem
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)?
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
Oops --- final paragraph should have read Inspection of the table of results suggests the almost-tidy explicit formula: for p-q odd, f(p, q, n) = [2^(n-(p+q+3)/2)] for q <= n; = [2^(n-(p+q+1)/2)] for q = n+1,n+2, and p <> n-1; = 1 for p = n-1 and q = n+2. WFL
Heigh-ho, still incomplete: trying again, the (conjectured) explicit formula is for p-q even, f(p, q, n) = 0; for p-q odd, f(p, q, n) = [2^(n-(p+q+3)/2)] for q <= n; = [2^(n-(p+q+1)/2)] for q = n+1,n+2, and p <> n-1; = 1 for p = n-1 and q = n+2. The recursion can be short-circuited to some extent by employing a less well-known "bottom-up" algorithm to transfer n discs from pin n to n+2: on odd moves, shift disc 0 to the next pin in cyclic order; on even moves 2i, make move i in the solution for n-1 discs, but with diameters p and q increased by 1. The cyclic order is rightwards for n even, leftwards for odd; and the even moves are the only shifts possible without moving (the smallest) disc 0 again. Hence the number of variables may be reduced from 3 to 2 via f(p, q, n) = f(p-1, q-1, n-1) = f(0, q-p, n-p); and as before, for n > 0, f(0, q, n) = 2 f(0, q, n-1) for 0 <= q <= n-1, q = n+1; the cases q = n-1, n+1 may be included above, since by f(0, q, n) = f(0, n, n-1) for q = n, n+2 we have f(p, n-1, n-1) = f(p, n+1, n-1) for n > 2. This leaves cases for 0 <= n <= 2 to be initialised by hand. Maple code is available to anybody who hasn't already dozed off ... WFL
I was not very satisfied with my earlier solution to DWW's ToH problem, and undertook a thorough investigation, hoping to explain more directly just why the answers come out as they do. I shan't take up bandwidth here with the results --- anybody wanting more detail is free to email for the relevant page of acrobat --- but a couple of things emerged which might interest people. Let the discs be indexed from 1 to n in order of decreasing diameter [apologies to DWW for previously dismissing this convention], and the pins 0, -1, -2 in order initial, intermediate, final. Given the move number in binary notation, there is an efficient algorithm to determine the index k of the disc/pin being shifted, l where it came off from, m where it goes on to. This can be reversed to enumerate all such moves, and in particular to evaluate their cardinal h(k,l,m). The construction hinges on an unexpected property of configurations along the solution path, novel to me, and apparently lacking any obvious combinatorial reason: For disc k to move to/from j < k-1, it is necessary that discs j+2, ..., k-2 occur in consecutive pairs sharing the same pin. [It can be easily established that the move must be from/to k-1.] Example: after move 28468 of the solution for n = 16 discs, the configuration is pin -0 discs 1 4 9 10 13 pin -1 discs 2 3 14 pin -2 discs 5 6 7 8 11 12 15 16 Disc k = 14 has just shifted from l = 13 to m = 3 = j; discs (5,6), (7,8), (9,10), (11,12) occur paired on pin -2,-2,0,-2 resp. By counting all configurations in which these are paired and later discs are on the unused pin, after a little tinkering with indices neighbouring k and j, we can further calculate that the number of moves with these values of k,l,m equals 2^((k+j-3)/2) = 128. Fred Lunnon [10/06/06]
participants (2)
-
David Wilson -
Fred lunnon