Here is a revised solution, for...
... n =
or, using letters to represent disks,
(again) seems like the maximum to me.
verified by Molhan
as being maximal.
Trivial steps have been condensed.
Step 1 2 3 4 5 6
abcdefghijklmnopqrstuvwxyzABCDE | | | | |
1 efghijklmnopqrstuvwxyzABCDE | | abcd | |
2 ijklmnopqrstuvwxyzABCDE | efgh abcd | |
3 ijklmnopqrstuvwxyzABCDE | abcdefgh | | |
4 mnopqrstuvwxyzABCDE | abcdefgh ijkl | |
5 opqrstuvwxyzABCDE | abcdefgh ijkl mn |
6 qrstuvwxyzABCDE op abcdefgh ijkl mn |
7 qrstuvwxyzABCDE mnop abcdefgh ijkl | |
8 qrstuvwxyzABCDE mnop abcdefgh kl ij |
9 qrstuvwxyzABCDE klmnop abcdefgh | ij |
10 qrstuvwxyzABCDE ijklmnop abcdefgh | | |
11 qrstuvwxyzABCDE ijklmnop cdefgh | ab |
12 qrstuvwxyzABCDE ijklmnop efgh cd ab |
13 qrstuvwxyzABCDE ijklmnop efgh abcd | |
14 qrstuvwxyzABCDE ijklmnop gh abcd ef |
15 qrstuvwxyzABCDE ghijklmnop | abcd ef |
16 qrstuvwxyzABCDE efghijklmnop | abcd | |
17 qrstuvwxyzABCDE abcdefghijklmnop | | | |
18 uvwxyzABCDE abcdefghijklmnop | qrst | |
19 wxyzABCDE abcdefghijklmnop | qrst uv |
20 yzABCDE abcdefghijklmnop wx qrst uv |
21 yzABCDE abcdefghijklmnop uvwx qrst | |
22 yzABCDE abcdefghijklmnop uvwx st qr |
23 yzABCDE abcdefghijklmnop stuvwx | qr |
24 yzABCDE abcdefghijklmnop qrstuvwx | | |
25 ABCDE abcdefghijklmnop qrstuvwx | yz |
26 CDE abcdefghijklmnop qrstuvwx AB yz |
27 CDE abcdefghijklmnop qrstuvwx yzAB | |
28 E abcdefghijklmnop qrstuvwx yzAB CD |
29 | abcdefghijklmnop qrstuvwx yzAB CD E
These steps may be reversed,
exchanging the roles of pegs 1 and 6,
to complete moving the whole tower from peg 1 to peg 6.
This approach was derived by mulling over
what happens after the symmetric midpoint,
step 29 above. At that stage...
... the last disk,
E, moves to a new peg, leaving peg 1 empty.
No other pegs should be empty, or else we didn't find the maximum n
because we would have the opportunity to move another disk
that could have been under
So, how tall a stack can be moved atop
E when one peg is free?
After moving that stack, two pegs will be free,
as the bottom of the moved stack
would have been the
D that winds up resting on
This, in turn, raises the question of
how many disks could subsequently be moved
onto the increasing goal tower above
This is repeated to reveal the following recursive pattern.
| - | - | - - - - - pegs - - - - - - - - |
1 2-tall Step +0. | CD (..........other occupied pegs..........) E
free stack Step +1. C D (..........other occupied pegs..........) E
peg may be Step +2. | | (..........other occupied pegs..........) CDE
2 4-tall Step +0. | | yzAB (.........occupied pegs.........) CDE
free stack Step +1. | yz AB (.........occupied pegs.........) CDE
pegs may be . . . Seen in reverse, step +1 was just .
moved . . . like asking how tall a stack can .
. . . go onto AB when 1 peg is empty. .
. . . Answer = 2 tall (yz). .
. . . And now we have an instance of .
. . . 1 free peg, which allows the .
. . . 2-tall stack AB to go atop CDE. .
Step +2. | yz | (.........occupied pegs.........) ABCDE
Step +3. | | | (.........occupied pegs.........) yzABCDE
3 8-tall Step +0. | | | qrstuvwx (..occupied pegs..) yzABCDE
free stack Step +1. | | qrst uvwx (..occupied pegs..) yzABCDE
pegs may be . . . . Seen in reverse, step +1 .
moved . . . . was just like asking how tall .
. . . . a stack can go on uvwx when .
. . . . 2 pegs are empty. Answer = .
. . . . 4 tall (qrst). Similar .
. . . . recursion on 2 free pegs .
. . . . puts uvwx on yzABCDE. .
Step +2. | | qrst | (..occupied pegs..) uvwxyzABCDE
Step +3. | | | | (..occupied pegs..) qrstuvwxyzABCDE
4 16-tall This 16 is derived similarly, completing the total 1+2+4+8+16 = 31
free stack may disks because the last stack-move begins with 4 empty pegs and ends
pegs be moved ends with 5 empty pegs along with the moved tower on the 6th peg.
Sketch of a proof that this is optimal,
thanks to Mike Earnest:
Let F(k) be size of the largest stack
that can be moved off an infinitely tall stack
when k empty pegs are available,
F(3) = 8
similar, in the method chart above, to
an "8-tall stack may be moved"
with "3 free pegs."
It can be shown that
F(k) ≤ 1 + F(1) + F(2) + ... + F(k−1)
by considering what pegs look like at midpoints of the process.