-2
$\begingroup$

There are $3$ saucers. And there are $5$ disks, say A,B,C,D,E, having respective areas $1,2,3,4,5$. That is, E is the largest disk and A is the smallest one.

They are placed in the order E,D,C,B,A in the leftmost saucer, that is, largest at the bottom, smallest at the top. The rest two saucers are empty.

You are supposed to transfer the entire stack in the same order in the rightmost saucer. That is, in the end, the first two saucers will remain empty and the third saucer will contain the disks in the order E,D,C,B,A, that is, largest disk at the bottom and the smallest one on the top.

You are allowed to use the middle saucer temporarily during the transfers, you can move only one disk at a time, you cannot place a bigger disk on a smaller one.

What is the least possible ways in which you can do this transfer? Can you devise an algorithm for any number of disks?

$\endgroup$
  • 1
    $\begingroup$ can we keep larger upside smaller? If yes then move D,C,B,A to 2nd saucer, then move E to 3rd saucer than move D,C,B,A to 3rd saucer. $\endgroup$ – Himanshu Feb 18 '15 at 12:08
  • $\begingroup$ @Himanshu , You'll find "you cannot place a bigger disk on a smaller one" if you read the post clearly and slowly. $\endgroup$ – Spikatrix Feb 18 '15 at 12:39
  • $\begingroup$ Should have added a cheeky little claim that it's possible in 30 moves. $\endgroup$ – No. 7892142 Feb 18 '15 at 13:17
5
$\begingroup$

This is the famous Tower of Hanoi problem. This describes the optimal algorithm:

For an even number of disks:

make the legal move between pegs A and B
make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete

For an odd number of disks:

make the legal move between pegs A and C
make the legal move between pegs A and B
make the legal move between pegs C and B
repeat until complete

In each case, a total of $2^n-1$ moves are made.

$\endgroup$
1
$\begingroup$

As has been stated, it's the Tower of Hanoi puzzle - but personally I didn't find that description of how to solve it particularly useful. I must be reading it wrong because 'repeat until complete' immediately fails on the second step (which attempts to move A to B, specifically disk C onto the middle saucer which already has BA on it and isn't a legal move).

So anyway, here is the long hand. Saucers are labelled 1,2,3 from left to right:

1: EDCBA
2:
3:

1: EDCB
2:
3: A

1: EDC
2: B
3: A

1: EDC
2: BA
3: 

1: ED
2: BA
3: C

1: EDA
2: B
3: C

1: EDA
2:
3: CB

1: ED
2: 
3: CBA

1: E
2: D
3: CBA

1: E
2: DA
3: CB

1: EB
2: DA
3: C

1: EBA
2: D
3: C

1: EBA
2: DC
3: 

1: EB
2: DC
3: A

1: E
2: DCB
3: A

1: E
2: DCBA
3: 

1: 
2: DCBA
3: E

1: A
2: DCB
3: E

1: A
2: DC
3: EB

1: 
2: DC
3: EBA

1: C
2: D
3: EBA

1: C
2: DA
3: EB

1: CB
2: DA
3: E

1: CBA
2: D
3: E

1: CBA
2: 
3: ED

1: CB
2: 
3: EDA

1: C
2: B
3: EDA

1: C
2: BA
3: ED

1: 
2: BA
3: EDC

1: A
2: B
3: EDC

1: A
2: 
3: EDCB

1: 
2: 
3: EDCBA
$\endgroup$
  • $\begingroup$ In the 'repeat until complete' the legal move between A and B means you'll move from B to A at the beginning of the second step. You move the smaller of the disks on A or B to the other peg. $\endgroup$ – Togashi Feb 19 '15 at 15:26
  • $\begingroup$ Ah ok gotcha. I was interpreting as 'from A to B', not 'between A and B' (even though it's written that way!) $\endgroup$ – Mashton Feb 19 '15 at 15:57

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.