WordGPT

The Tower of Hanoi: 7 disks need 127 moves

Exercise ยท Level 2 (Easy)

How many moves does the Tower of Hanoi need for n disks, and for 7 disks?

T(n)=2nโˆ’1T(n)=2^n-1

wordgptpro.com

Solution

  1. Moving nn disks: move the top nโˆ’1n-1 to the spare peg (T(nโˆ’1)T(n-1) moves), move the biggest disk (1 move), move the nโˆ’1n-1 disks on top of it (T(nโˆ’1)T(n-1) moves):

    T(n)=2โ€‰T(nโˆ’1)+1,T(1)=1\begin{aligned}&T(n)\\&=2\,T(n-1)+1,\qquad T(1)\\&=1\end{aligned}
    (1)
  2. The values are 1, 3, 7, 15, 31, 63, 127, โ€ฆ Each is one less than a power of 2, which follows by induction: 2(2nโˆ’1โˆ’1)+1=2nโˆ’12(2^{n-1}-1)+1=2^n-1:

    T(7)=27โˆ’1=127T(7)=2^7-1=127
    (2)
  3. The legend of 64 disks needs 264โˆ’12^{64}-1 moves: at one move per second that is about 585 billion years.

Answer2nโˆ’1ย ย (n=7:ย 127)2^n-1\ \ (n=7:\ 127)

wordgptpro.com

Need a hint?

To move n disks you must first move n โˆ’ 1 disks out of the way, move the biggest, and move n โˆ’ 1 disks back on top.

The Tower of Hanoi with n disks needs 2โฟ โˆ’ 1 moves: 127 for 7 disks.

How to work it out

  1. Moving nn disks: move the top nโˆ’1n-1 to the spare peg (T(nโˆ’1)T(n-1) moves), move the biggest disk (1 move), move the nโˆ’1n-1 disks on top of it (T(nโˆ’1)T(n-1) moves):

    T(n)=2โ€‰T(nโˆ’1)+1,T(1)=1\begin{aligned}&T(n)\\&=2\,T(n-1)+1,\qquad T(1)\\&=1\end{aligned}
    (1)
  2. The values are 1, 3, 7, 15, 31, 63, 127, โ€ฆ Each is one less than a power of 2, which follows by induction: 2(2nโˆ’1โˆ’1)+1=2nโˆ’12(2^{n-1}-1)+1=2^n-1:

    T(7)=27โˆ’1=127T(7)=2^7-1=127
    (2)
  3. The legend of 64 disks needs 264โˆ’12^{64}-1 moves: at one move per second that is about 585 billion years.

LaTeX source of the formulas on this page
\[ 2^n-1\ \ (n=7:\ 127) \]
\[ T(n)=2\,T(n-1)+1,\qquad T(1)=1 \]
\[ T(7)=2^7-1=127 \]

Questions

What is the answer to: The Tower of Hanoi: 7 disks need 127 moves?

The Tower of Hanoi with n disks needs 2โฟ โˆ’ 1 moves: 127 for 7 disks.

What is the key idea?

The problem for n disks contains two copies of the problem for n โˆ’ 1 disks.

Is there a hint?

To move n disks you must first move n โˆ’ 1 disks out of the way, move the biggest, and move n โˆ’ 1 disks back on top.

Related problems

More probability and puzzles

    The Tower of Hanoi: 7 disks need 127 moves: answer and solution | WordGPT