18
$\begingroup$

Consider the following variant of the Towers of Hanoi puzzle. There are six pegs. One of the pegs has a stack of $n$ differently sized disks, sorted by size so the smallest disk is at the top. All other pegs are empty. The goal is to move this stack to a different peg.

You may only move one disk at a time. A disk may moved either to an empty peg or onto another disk which is exactly one size larger. Numbering the disks $1$ to $n$ in increasing order of size, this means disk $k$ can only be placed on an empty peg or on disk $k+1$.

What is the largest value of $n$ for which this puzzle is solvable?

Addendum: The source of the puzzle is http://skepticsplay.blogspot.com/2011/10/tower-of-hanoi-variant.html?m=1 . Amusingly, this puzzle is a simplification of FreeCell.

|improve this question
$\endgroup$
15
$\begingroup$

Here is a revised solution, for...

... n =  17  31 or, using letters to represent disks, abcdefghijklmnopqrstuvwxyzABCDE, ...

...which  (again) seems like the maximum to me.  has been 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 E.

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 E. This, in turn, raises the question of how many disks could subsequently be moved onto the increasing goal tower above E?

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
        moved

  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, which makes   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.

|improve this answer
$\endgroup$
  • $\begingroup$ Looks to me like you can join hijklm in the same manner as you joined abcdefg in the first step. $\endgroup$ – ffao Aug 31 '17 at 21:39
  • $\begingroup$ You were certainly on to something, @ffao, and proved it with your solution. In the meanwhile I found a mistake in my system and now the steps practically explain the approach but I'll still write it up. $\endgroup$ – humn Sep 1 '17 at 0:21
  • $\begingroup$ I found pretty much the same improvement on my own after I saw that you had found a better solution. I don't think we can do better than this, but I wouldn't be surprised by this point... $\endgroup$ – ffao Sep 1 '17 at 3:36
  • $\begingroup$ Funny, my first answer was the same 15 as was first posted by someone else, before I took this approach. Kept finding errors, though, from a seemingly endless supply. $\endgroup$ – humn Sep 1 '17 at 3:40
  • 1
    $\begingroup$ Nicely done! Once you've gotten the method, it's not too hard (but not too illuminating) to prove that it is optimal by induction. Sketch: letting F(k) be size of the largest stack that can be moved off an infinitely tall stack when k empty pegs are available, prove F(k) ≤ 1 + F(1) + F(2) + ... + F(k-1), by considering what pegs look like at the midpoint of the process. $\endgroup$ – Mike Earnest Sep 2 '17 at 20:19
6
$\begingroup$

I wrote a program to find the answer to this question. I indeed found that 31 was the maximum number of disks for a 6 peg board. I also ran the program with 3, 4, and 5 pegs. Interestingly, the maximum number of disks is 3, 7, and 15 respectively. The yields the sequence 3,7,15,31, which is 2^(p-1)-1 where p is the number of pegs. I'll try to get the number for 7 pegs, but it will take a while.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If you understood humn's solution, those numbers are not surprising at all. I'm guessing 63 for 7 pegs. $\endgroup$ – ffao Sep 1 '17 at 7:21
  • $\begingroup$ Well, my program failed to find a solution with 40 disks & 7 pegs. It took about 4 hours to run. So either the conjecture is false or my program is flawed. $\endgroup$ – Molhan Sep 1 '17 at 16:07
4
$\begingroup$

Here's a solution for...

n = 25

I believe this is maximal, though I can't really produce a formal proof as to why. humn outdid me again, so I'll leave this here just for historical reasons :)

I'll represent the disks by letters in a way very much inspired by humn's answer:

      Step                           1    2             3         4      5       6

        0    abcdefghijklmnopqrstuvwxy    |             |         |      |       |
        1        efghijklmnopqrstuvwxy    a             b         c      d       |
        2        efghijklmnopqrstuvwxy    |             |         |   abcd       |
        3           hijklmnopqrstuvwxy    e             f         g   abcd       |
        4           hijklmnopqrstuvwxy    |             |       efg   abcd       |
        5             jklmnopqrstuvwxy    |             i       efg   abcd       h
        6             jklmnopqrstuvwxy    |             |       efg   abcd      hi
        7               lmnopqrstuvwxy    j             k       efg   abcd      hi
        8               lmnopqrstuvwxy    |            jk       efg   abcd      hi
        9               lmnopqrstuvwxy    h            jk       efg   abcd       i
       10               lmnopqrstuvwxy    |          hijk       efg   abcd       |
       11               lmnopqrstuvwxy    e          hijk         g   abcd       f
       12               lmnopqrstuvwxy    |       efghijk         |   abcd       |
       13               lmnopqrstuvwxy    a       efghijk         b      d       c
       14               lmnopqrstuvwxy    |   abcdefghijk         |      |       |
       15                  opqrstuvwxy    l   abcdefghijk         m      n       |
       16                  opqrstuvwxy    |   abcdefghijk         |    lmn       |
       17                    qrstuvwxy    |   abcdefghijk         o    lmn       p
       18                    qrstuvwxy    |   abcdefghijk         |    lmn      op
       19                      stuvwxy    q   abcdefghijk         r    lmn      op

       20                      stuvwxy    |   abcdefghijk        qr    lmn      op

       21                      stuvwxy    o   abcdefghijk        qr    lmn       p

       22                      stuvwxy    |   abcdefghijk      opqr    lmn       |
       23                      stuvwxy    l   abcdefghijk      opqr      n       m
       24                      stuvwxy    |   abcdefghijk   lmnopqr      |       |
       25                        uvwxy    s   abcdefghijk   lmnopqr      t       |
       26                        uvwxy    |   abcdefghijk   lmnopqr     st       |
       27                          wxy    u   abcdefghijk   lmnopqr     st       v
       28                          wxy    |   abcdefghijk   lmnopqr     st      uv
       29                          wxy    s   abcdefghijk   lmnopqr      t      uv
       30                          wxy    |   abcdefghijk   lmnopqr      |    stuv
       31                            y    w   abcdefghijk   lmnopqr      x    stuv
       32                            y    |   abcdefghijk   lmnopqr     wx    stuv
       33                            |    y   abcdefghijk   lmnopqr     wx    stuv

These steps may be reversed, exchanging the roles of pegs 1 and 2, to complete moving the whole tower from peg 1 to peg 2.

|improve this answer
$\endgroup$
2
$\begingroup$

New solution

20 disks 

 1                        2    3           4            5         6
abcdefghijklmnopqrst                    
fghijklmnopqrst           a    b           c            d         e
fghijklmnopqrst                          abcde
hijklmnopqrst             f    g                                abcde
hijklmnopqrst             a    fg          b            c        de
hijklmnopqrst             e    f           g           abc        d
hijklmnopqrst             b               defg          c         a
klmnopqrst                h    i          abcdefg       j   
klmnopqrst                a    b           cdefg       hij  
klmnopqrst                d                efg         hij       abc
klmnopqrst                de               fg          hij       abc
klmnopqrst                 f   de                     ghij       abc
klmnopqrst                                          defghij      abc
klmnopqrst                 a    b                  cdefghij 
klmnopqrst                                         abcdefghij   
opqrst                     k     l           m      abcdefghij     n
opqrst                                              abcdefghij  klmn
rst                        o    p            q     abcdefghij   klmn
rst                                         opq    abcdefghij   klmn
t                          s    r           opq    abcdefghij   klmn
                           rs   t           opq    abcdefghij   klmn
r                           s   t           opq    abcdefghij   klmn
                               rst          opq    abcdefghij   klmn
o                          p    rst               abcdefghij    klmn
                               opqrst             abcdefghij    klmn
k                          l    opqrst       m     abcdefghij   n
                             klmnopqrst             abcdefghij  
a                         b   klmnopqrst     c      efghij      d   
e                         f   klmnopqrst     g       hij        abcd
h                         i    klmnopqrst   efg        j        abcd
                             hijklmnopqrst  efg     abcd
e                         f  ghijklmnopqrst         abcd
c                           efghijklmnopqrst    a    b            d
                         abcdefghijklmnopqrst

The largest value of n is:

You can have 15 disks maximum

There are only six pegs

One has 15 disks and 5 are empty

Differently sized disk

Start by moving one disk to each empty peg five and put it one over another largest to smallest in one peg (five disks in one peg and the others in another one)
Remain four empty pegs move four disks to it then put it one over another largest to smallest in one peg (four disks in one peg, five disks in another peg and the remaining in the third peg)
Remain three empty pegs move three disks to each one then put it one over another in one peg (5 disks in one peg (5,4,3,2,1), 4 disks in another peg (9,8,7,6), 3 disks in the third peg (12,11,10) and the remaining in the fourth peg)
Remain two empty pegs you can move 2 disks then put it one over another in one peg (14,13).
You can move the last disk (15) to the empty peg and reverse the method move the 2 disks (14,13) one to the initial peg (is now empty) and the other one (14) over the largest disk (15), then move the other disk (13) over the 2
Do the same with the peg with 3 disks (12,11,10), then with the 4 disks (9,8,7,6), then with the 5 disks (5,4,3,2,1) and now you moved all the 15 disks from one peg to another

|improve this answer
$\endgroup$
  • 4
    $\begingroup$ I'm fairly sure that's the right answer, but how do you know you can't do better? $\endgroup$ – user27014 Aug 31 '17 at 19:52

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.