0
$\begingroup$

I am reading the book "Concrete Mathematics: A Foundation for Computer Science"

and I am faced with the first problem. The book is introducing some notation to solve the Tower of Hanoi problem.

I'm stuck at the very first step, see quote from the book below:

enter image description here

How can T2 be 3, meaning, how is the minimum number of moves to the next peg will be 3 for 2 disks??

thanks

$\endgroup$
1
$\begingroup$
  • Move the top disk to the non-destination peg.
  • Move the bottom disk to the destination peg.
  • Move the top disk to the destination peg.
$\endgroup$
0
$\begingroup$

The minimum number of moves that will transfer $2$ disks from one peg to another is $3$, because you can solve the puzzle in $3$ moves (see other Answer), and you cannot solve it in less than $3$ moves.

A simple proof for the last part is this. With two disks, and being able to move only disk at a time, it obviously takes at least $2$ moves. But if we could solve it in $2$ moves, then each move would have to move a disk to the destination peg, given that at the start they are all not on the destination peg. But, after moving the top disk to the destination peg, you cannot move the bottom disk to the destination peg. So, solving the puzzle in $2$ moves is impossible.

$\endgroup$

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.