From: rhinoceros (rhinoceros@freemail.gr)
Date: Thu Feb 26 2004 - 22:45:57 MST
I knew it as "Towers of Hanoi". Nice problem. It is often found in computer programming textbooks, in the chapter about regression, because it is a rare clear case where regressive thought is the intuitive way to go. You know... things like "if I have solved it for n disks, how do I solve it for n+1 disks". Old plain sequential thought is at a disadvantage here.
Hmm... let's see.
Let's say I solved it for 3 disks and it took me n moves to move them, say, from pin A to pin B.
But... oops... I just noticed there was a 4th disk left at A. Now I need to move that 4th disk from A to C (1 move), and then repeat whatever I did at the beginning and move the other 3 disks on top of it, from B to C (n moves again).
So, if I need n moves to solve the problem for k disks, I need 2n+1 moves to solve it for k+1 disks.
So, let's say that for 4 disks we need n4 moves:
n4 = 2*n3+1 = 2*(2*n2+1)+1
= 2*(2*(2*1+1)+1)+1
= 2^3 + 3^2 + 2^1 + 2^0
Damn... we will still need to use a cookbook formula. This last result is a powerseries:
2^(n-1) + 2^(n-2) +...+ 2^1 + 2^0 = 2^n - 1
And the result is 2^n - 1. It is not hard to give a formal proof using mathematical induction, but I think the answer is better understood by using this "construction" method.
---- This message was posted by rhinoceros to the Virus 2004 board on Church of Virus BBS. <http://virus.lucifer.com/bbs/index.php?board=61;action=display;threadid=29971> --- To unsubscribe from the Virus list go to <http://www.lucifer.com/cgi-bin/virus-l>
This archive was generated by hypermail 2.1.5 : Thu Feb 26 2004 - 22:48:05 MST