Hanoi wants more Towers
The
Tower of Hanoi
is a traditional game where there are 3 pegs and
n
discs arranged as seen in picture. All discs are to be moved from
1
s
t
peg
P
1
to
3
r
d
peg
P
3
such that only one disc is moved at once. But no disc should be kept on one smaller than it during the process. So the minimum number of moves required to transfer all discs to
P
3
(say
a
n
) is counted by
a
n
=
2
a
n
−
1
+
1
and
a
1
=
1
i.e. after solving becomes
a
n
=
2
n
−
1
.
If we have a Tower of Hanoi with 42 pegs, and we have an additional rule that no disc can be moved more than twice, what is the maximum number of discs such that all discs can be moved to pegs other than the first peg P 1 ?
The answer is 861.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
You have only shown that 861 can be achieved. How do you know that this is indeed the maximum?
@Calvin Lin The following may answer your question.
We have 42 pegs and 1st peg is occupied by d discs. We put 1 disc on the 2nd peg, now whatever discs is on 1st peg, we can not put it on second peg because they are bigger. They have to go to one of the empty pegs. Let's say we put the second disc on 3rd peg.
Now if we move the 1st disc from 2nd peg on top of 2nd disc from 3rd peg, we'll have 2 discs on 3rd peg. But as they are smallest discs, if there is a possibility where we can put it on a larger disc we'll achieve 3 discs on a peg which is larger than the previously counted 2 discs. It turns out we can put the 3 smallest discs of all on a single peg with the given rule. We put 3 discs on 2nd, 3rd, 4th peg respectively. Put the 2nd disc from 3rd peg on top of 3rd disc on 4th peg, similarly from 2nd peg on 4th peg. In a similar way we can put 41 discs on a single peg, let's say 42nd peg.
Now we'll prove that maximum of 41 discs can be placed on 42nd peg while ( d − 4 1 ) discs are on 1st peg.
Let's say we can put 42 discs on 42nd peg while ( d − 4 2 ) discs are on 1st peg. So initially when ( d − 4 2 ) discs are on 1st peg, all 41 pegs are having 1 disc each except 1 peg which has 2 discs. Let's say the 2nd peg has 2 discs and all remaining pegs(3rd, 4th, ... , 42nd) are having 1 disc each. let's call the top disc on 2nd peg as d 1 . d 1 can not come from 1st peg because the bottom disc on 2nd peg has to be larger than d 1 , so it has to come from any of 3rd, 4th, ... , 42nd peg at some point there by making that peg empty. That means d 1 already moved 2 times, so we can not move any disc from 2nd peg. So we can not place 42 or more discs on a peg while there are ( d − 4 2 ) or less discs on 1st peg.
In a similar way we can put maximum of 40, 39, 38, ... discs on 41st, 40th, 39th, ... pegs.
So the solution is 4 1 + 4 0 + . . . + 1 = 8 6 1
Log in to reply
Close, but not quite. Your argument currently still relies on "I have chosen the way that things are moved". It is not independent of the strategy that is employed.
Log in to reply
@Calvin Lin - I'm not able to go further from this, Can you help a little bit here ?
41+40+...............+1 = 861
We have 41 pegs Empty
We can transfer top 4 1 discs one to each empty peg,then we transfer those 41 all on the last peg.
Now 4 0 pegs remain empty, we put 1 disc each in all those 4 0 pegs and finally transfer them all to Second last peg
Now 3 9 pegs remain empty, we put 1 disc each in all those 3 9 pegs and finally transfer them all to Third last peg
So on
We get a series of discs from 4 2 n d peg to 2 n d peg as 4 1 , 4 0 , … , 3 , 2 , 1 and hence the total discs moved away from 1 s t peg are 4 1 + 4 0 + ⋯ + 3 + 2 + 1 = 2 4 1 ( 4 2 ) = 4 1 × 2 1 = 8 6 1