Once again (as a C++/Data Structures student) my mind has been forced to
accept the premise that
"Given 3 pegs, n disks, and the rules governing the Tower of Babel problem
that the problem can be solved, recursively."
I'm tentatively willing to accept that if an omnipotent being can
successfully transfer n-1 disks from peg A to peg B, that he/she should
therefore be able to successfully transfer (n-1)-1 pegs, and so on till
the problem is reduced to the tiny tower I constructed (from nails and
washers) on which I can demonstrate the successful transfer of n=4,3,2
and n=1 (the base class) disks.
But isn't there an incredible leap of faith going on here? What's to say
that given a 100 disk transfer that, at say disk 39, the process doesn't
break down because there aren't enough pegs? (and therefore the problem
breaks down at this point)
So I was wondering...
Given the original Tower problem, and assuming 100 disks, but given p
pegs, can it be proven:
- that the problem can be solved in less steps for p = 4, 5, 6,...?
- how many steps it'll take to solve the problem given these conditions?
- that the problem can be solved recursively?
1) Does the restatement of the problem elucidate matters?
2) Is the solution to the Son of Tower as intuitively obvious as the
original tower seems to be to some?
3) Is Son of Tower solvable recursively?
4) Does understanding/solving Son of Tower help one understand the
original problem more clearly?
Thanks
------------------------------------------
please also reply as email...
: Once again (as a C++/Data Structures student) my mind has been forced to
: accept the premise that
: "Given 3 pegs, n disks, and the rules governing the Tower of Babel problem
: that the problem can be solved, recursively."
The proble you are referring to is called the Tower of Hanoi. The
Tower of Babel is the problem otherwise known as The Internet (or the
programming language community).
Cheers,
'Jeff
·····@sirius.com (Joost Romeu) wrote:
>Once again (as a C++/Data Structures student) my mind has been forced to
>accept the premise that
>"Given 3 pegs, n disks, and the rules governing the Tower of Babel problem
>that the problem can be solved, recursively."
>
>I'm tentatively willing to accept that if an omnipotent being can
>successfully transfer n-1 disks from peg A to peg B, that he/she should
>therefore be able to successfully transfer (n-1)-1 pegs, and so on till
>the problem is reduced to the tiny tower I constructed (from nails and
>washers) on which I can demonstrate the successful transfer of n=4,3,2
>and n=1 (the base class) disks.
>
>But isn't there an incredible leap of faith going on here? What's to say
>that given a 100 disk transfer that, at say disk 39, the process doesn't
>break down because there aren't enough pegs? (and therefore the problem
>breaks down at this point)
>
>So I was wondering...
>Given the original Tower problem, and assuming 100 disks, but given p
>pegs, can it be proven:
> - that the problem can be solved in less steps for p = 4, 5, 6,...?
> - how many steps it'll take to solve the problem given these conditions?
> - that the problem can be solved recursively?
>
>
>1) Does the restatement of the problem elucidate matters?
>2) Is the solution to the Son of Tower as intuitively obvious as the
>original tower seems to be to some?
>3) Is Son of Tower solvable recursively?
>4) Does understanding/solving Son of Tower help one understand the
>original problem more clearly?
>
>Thanks
>
>------------------------------------------
>please also reply as email...
The principal involved with this solution is call Mathematical Induction.
You are trying to prove a theorem true for all positive integers. We say
a theorem is true by induction if:
a) It is true for 1, (the smallest positive integer)
and b) if it is true for any given positive integer n, then it must be
true for n+1.
Given these 2 facts, we can say since it is true for 1, by b) it is true
for 2. Then since it is true for 2 it must be true for 3, and so on
ad infinitum.
So, in the case of the towers of Hanoi problem, for moving one disk we
just move it, satisfying a). Now suppose we can move n disks. In order to
move n + 1 disks, we move the top n disks to the third peg, move the
bottom (n+1'st) disk to the destination peg, and move the top n disks
from the third peg to the second peg.
Hope this helps
Joe Gottman
From: J.J.A. Koot
Subject: Re: Son of Tower of Babel
Date:
Message-ID: <322543B0.167E@sara.nl>
Joost Romeu wrote:
> Once again (as a C++/Data Structures student) my mind has been forced to
> accept the premise that
> "Given 3 pegs, n disks, and the rules governing the Tower of Babel problem
> that the problem can be solved, recursively."
Is this the same problem as the Tower of Hanoi?
> But isn't there an incredible leap of faith going on here?
I don't think so. May be you are not too familiar with recursive proofs.
Look at it this way.
1: You know for sure that you can solve the problem for p=3 and n=1.
2: You know for sure that IF you know how to move the disks for p=3 and n=m,
THEN you can construct a method for moving m+1 disks.
3: Hence knowing a method for n=1, you can construct a method for n=2.
4: Knowing a method for n=2, you can construct a method for n=3.
5: Knowing a method for n=3, you can constrcut a method for n=4, etc,
p being 3 in all cases.
6: If you are certain of the proof of item 2, then there is no doubt about
the etc of item 5.
> 1) Does the restatement of the problem elucidate matters?
No, I don't think so, although it may be interesting to compute
the minimal number of moves for p>3 and n>p. The maximum number of moves
without repeating disk distributions is interesting too. For p=3 there
is a simple recursive solution (Try it). A similar problem is that of moving
along all feasible distributions of disks starting from a tower at one peg
and ending with a tower at the same peg (Hamilton path).
> 2) Is the solution to the Son of Tower as intuitively obvious as the
> original tower seems to be to some?
Having a solution for p=3, we already have solutions for all p>3.
> 3) Is Son of Tower solvable recursively?
Yes, having a method for p=3, we already have a method for all p>3.
> 4) Does understanding/solving Son of Tower help one understand the
> original problem more clearly?
I don't know, but it may be revealing that there are simple methods
that in the jargon of programmers would be called "non recursive"
(although I don't know what that would mean mathematically,).
First method:
Every single move is computed as follows until all disks are at the
destination peg, say peg DEST.
Given an arbitrary distribution of n disks over 3 pegs assuming
no disk rests on a smaller one.
THERE:=DEST
Loop for DISK running from largest to smallest disk:
if DISK is at peg HERE and HERE not equals DEST, then
MOVE:="DISK must be moved from HERE to THERE" (record current values)
THERE:=neither HERE not THERE (but remaining third peg)
end of loop
Has a move been recorded?
If yes, then make the last recorded MOVE.
If no, then all disks are on peg DEST
Mark that the above method can be used also if the distribution of disks
is not located on the shortest way of moving the tower from one peg to another one.
In simpler words, the method also works after making legal but false moves.
Second method:
program hanoi ! Fortran 90 program
!*********!*********!*********!*********!*********!*********!*********!
! this program prints a specified part of the list of moves of the
! shortest way of moving a full hanoian tower of specified height from
! a specified starting needle onto a specified destination needle.
! every move and its resulting situation is computed without using any
! previously known data.
! the piles are identified by the integer numbers 0, 1 and 2.
! the disks are identifid by the ordinals 1 to n in order of increasing
! size.
! n : the total number of disks
! f : the starting needle
! t : the destination needle
! method
! let f, t and p be the three needles. there are 6 feasable moves. we
! devide them in two groups:
! even group: from f to t or from t to p or from p to f
! odd group: from f to p or from p to t or from t to f
! the code below is based on the following two observations
! 1: that disk d always is moved in even fashion if n-d is even and in
! odd fashion if n-d is odd.
! 2: that the ordinal of the disk being moved is equal to one plus the
! number of times the move-number can be devided by 2.
implicit integer (a-z)
character(*), parameter :: mfm = &
'("'' move-number disk from onto pass rota positions''/'// &
'(1x,i11,1x,5(i3,2x),",i2,"i1))")'
character(len(mfm)) :: fmt
! statement functions
modk(x,k)=mod(x+k*abs(x),k) ! true circular modulus
mod2(x )=modk(x,2)
mod3(x )=modk(x,3)
log2(x )=nint(log(real(x))/log(2.0))! log base 2 rounded to an integer
div2(x )=(ieor(i,i-1)-1)/2+1 ! 2**(# times x devisible by 2)
exp2(x )=log2(div2(i)) ! # times x can be devided by 2
nmov(n )=2**n-1 ! total number of moves required
sens(d, f,t,n)=2*mod2(mod3(t-f)+n-d)-1 ! sense of rotation of disk d
disk( i )=exp2(i)+1 ! disk being moved during move i
move(d,i )=(i+2**(d-1))/2**d ! # moves disk d made after total
! of i moves
posi(d,i,f,t,n)=mod3(f+move(d,i)*sens(d,f,t,n)) ! position of disk d
! after a total of i moves
rota( i,f,t,n)=sens(disk(i),f,t,n) ! sens of rotation of the disk
! being moved during move i
onto( i,f,t,n)=posi(disk(i),i,f,t,n)! needle onto which a disk is
! being moved during move i
from( i,f,t,n)=mod3(onto(i,f,t,n)-rota(i,f,t,n)) ! needle from which
! a disk is taken during move i
pass( i,f,t,n)=mod3(onto(i,f,t,n)+rota(i,f,t,n)) ! needle not being
! used during move i
! request, accept and check data from user
m=int(log(real(huge(0)))/log(2.0))-1
write(*,*)' Give number of disks, needle of origin and '//&
'needle of destination'
write(*,*)' 0 < number of disks <',m,' and 0 <= needle <= 2'
read (*,*)n,f,t
if(n.le.0.or.n.gt.m.or.f.lt.0.or.f.gt.2.or.t.lt.0.or.t.gt.2.or.f.eq.t)&
stop 'illegal input data'
write(*,*)' the full list consists of ',nmov(n),' moves'
write(*,*)' give first and last number of moves to be listed'
read(*,*)b,e
! adapt format
write(fmt,mfm)n
! print selected part of list
write(*,fmt)(i,disk(i),from(i,f,t,n),onto(i,f,t,n),pass(i,f,t,n), &
rota(i,f,t,n),(posi(d,i,f,t,n),d=1,n),i=max(1,b),min(nmov(n),e))
!*********!*********!*********!*********!*********!*********!*********!
end program hanoi
Of course both methods can be proven by mathematical
induction (very similar to recursive programming).
Have fun, Jacob
"Is science just another religion? I am not sure!"
Greetings, J. J. A. Koot, Stichting Academisch Rekencentrum Amsterdam
Tel: +31 20 5923019 Postbus 94613, 1090 GP, Amsterdam, Netherlands
Fax: +31 20 6683167 http://www.sara.nl/koot ···········@sara.nl