Towers of Hanoi Variation

Decision and strategy, simulations and probability models, card and board games, ...
Post Reply
User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Towers of Hanoi Variation

Post by elendiastarman » Thu Oct 08, 2009 4:26 am

I got an idea while looking at a child's toy and simplified it to represent the simplest non-trivial case.

You start with 3 poles in a row. The left one has triangles on it and the right has squares, there is nothing in the middle. Rules are exactly like the original for the triangles and the squares, but you can put a big square on top a small triangle, although you must move the big square off first. The objective is for the stacks to switch position.
How many moves will it take to switch stacks when both have 4 pieces?
How many moves will it take to switch stacks when both have 5 pieces?
How many moves will it take to switch stacks when both have 10 pieces?
If having only 3 poles makes it impossible, prove it and use 4 poles instead. I haven't actually tried it yet... :/
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

rmillika
Posts: 39
Joined: Thu Apr 05, 2007 3:37 pm

Re: Towers of Hanoi Variation

Post by rmillika » Sat Oct 17, 2009 12:00 am

If the rule is that any square can go on any triangle, we can just view this as a stage of the original game with the number of disks equal to the sum of the squares and triangles. So for 4 squares and 4 triangles we have eight disks with a linear order among them. If we started with all the disks on one peg and played the original game, we are now 15 moves in. Your target configuration is achieved 15 moves before completion of the original game. So the number of moves is 2^8-1-30=225. For five of each it is not so easy, as we are not on the way to stacking the triangles on the right side, but on the way to stacking the triangles in the middle. One choice is to move the squares back to the triangles, using 31 moves, go 31 moves short of moving the whole stack to the right (which has the squares in the middle), then use 31 moves to get the squares on the left. This is 31+2^10-1=1054. I am not sure that there isn't a faster way. For 10 we have 2^20-1-2*(2^10-1)=1046549.

I think.

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Towers of Hanoi Variation

Post by elendiastarman » Sat Oct 17, 2009 12:13 am

Well, the rule is that any square can go on any triangle and any triangle can go on any square. There is no relation between the two other than physically preventing the lower one from being removed before the higher one.
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

rmillika
Posts: 39
Joined: Thu Apr 05, 2007 3:37 pm

Re: Towers of Hanoi Variation

Post by rmillika » Tue Oct 20, 2009 8:56 am

In that case, I think the easiest is to move the squares to the center peg, the triangles to the left, and the squares to the right, using the standard solution.
You have to clear the largest square from the left peg, and putting it on the triangles is in the way. So for four of each we need 3*(2^4-1)=45 moves.
I can't think of a more efficient way.

User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 2:13 pm
Location: South Korea

Re: Towers of Hanoi Variation

Post by uws8505 » Fri Jan 01, 2010 3:29 am

I doubt that it is possible, but think of this:
Move the top(smallest) triangle to the middle. Then move the top square to the middle.
Repeat the process until you have only one square left on the right and nothing on the left.
Move the biggest square to the left. Then move all pieces on the middle to the corresponding position.
That makes only 4n-1 moves!
If you do not consider violation of "bigger under smaller" rule for pieces not touching each other, it makes sense :D
Math and Programming are complements

Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Towers of Hanoi Variation

Post by Alhazen » Sun Mar 18, 2012 11:22 pm

What about an abstract 2 game players based on towers of Hanoi?

Post Reply