Extra Crdit Math problem

Kania2k1 · January 31, 2002

OK, got this assigned the other day in my Classical Algebra class. Worked on it for about 5 hours at work the other night. Cook a few dinners, do homework, cooka few dinners, do homework, etc. Ther diagram is of 3 dowels on a 2X4 with n-disks on them. Anyway's here's the problem:

The puzzle consists of n-disks of decreasing diameters placed on a pole. There are two other poles. The problem is to move the entire pile to another pole by moving one disk at a time to any other pole, EXCEPT that no disk may be placed on top of a smaller disk. Find a formula for the least number of moves needed to move n-disks from one pole to another, and prove the formula by induction.

For those unfamiliar with "Proofs by induction" it involves proving that a formula works for a given, here it's n=1, and then proving it for n+1. It helps to write down all your moves and to label the poles (dowels) A, B, C. Just wanna say, good luck, we're all counting on you!

Jpshostr · January 31, 2002

He is pulling your leg. To do that would take longer than many lifetimes! I remember talking about that in math, the equation, #### if I know what it is.

chevy4x4trucks · February 1, 2002

I know it can be done, I saw it in math class and the teacher did it. Give me some time, I'll find you an answer, c'mon guys we've got the power of the internet, it's out there somewhere.

chevy4x4trucks · February 1, 2002

http://www.mts.net/~kolar/javascript/Hanoi/HTonWebE.html

Give this link a try, it may help you a bit.

siume99 · February 1, 2002

Hummm, how are the disks stacked? Starting off, are they stacked with the smallest dia on the bottom going larger on the way up? Also, do the disks start on the same pillar?

brmiller · February 1, 2002

Well, I shouldn't be doing other folks' math homework, but I gotta chime in. Finally something my math minor in college comes in useful for.

If I remember correctly (and I'm pretty sure about this), the formula is

number of moves = 2^n - 1

2^n is 2 raised to the nth power; n is the number of disks.

I think the typical Hanoi game has 7 discs on it, so it will take 127 moves. I can usually do all 127 moves in less than 90 seconds. I was working toward getting all 127 moves in less than 60 seconds, but that's just too fast. You'd think you could average two moves a second, but it takes longer than you'd think to move those things back and forth--even when you get a rythmn going.

Brendan

P.S. Here's hoping I didn't embarrass myself with a wrong answer.

NewbieZ71 · February 2, 2002

Mathematically it makes no difference how they are stacked as long as you are moving them to the opposite positions. I think that generally you startout with them small diameter at bottom and move them to the opposite with big at bottom small at top. The reason is that by the time you finish you will not want to touch them for about 10 years and they look neater and more orderly with big on the bottom.

Kania2k1 · February 2, 2002

Hey miller, That's what I came up with, but it also works for 2*M + 1, where M is equal to the number of moves in the prior attempt. For Example, it takes 7 moves to shift 3 disks. Therefor it will take 2(7) + 1 , or 15 moves to shift 4 disks. I think that 2^n -1 won't work for very large n. But we'll see when I hand it in!!! (fingers crossed)!