Thread: Problem 19

1)You are given 3 disks A,B,C and 3 stands X,Y,Z. The biggest disk is C, then B then A. And A lies on top B which lies on top C all on the same stand, say X. The rule is that the smaller disks must remain on the larger disks.
The following moves will moves these disks together to a new stand.
a)Take A and place it on Y.
b)Take B and place it on Z.
c)Take A and place it on top of B on Z.
d)Take C and place it on Y.
e)Take A and place it on X.
f)Take B and place it on top of C on Y.
g)Take A place it on top of B on top of C on Y.

Now assume you have 64 disks, how long will it take you move them on top a new stand if each move you do is 1 second.

2)Show that if a number is large enough it can be expressed exactly as a sum of 5 postive integral squares.
(Hint: Use 4 Square Theorem)

I know the first problem as the "Towers of Brahmin" or the "Towers of Hanoi." It's actually fun to make the disks and play with. (I was amused at least. But I'm a "Ooooh! Something shiny!" kind of guy.)

-Dan

for n disk require (2^n)-1 steps

so for 64 =(2^64)-1 steps=18.446.744.073.709.551.615 steps

since 1 step requires 1 second so it will take 580 billion years

assume that we do it 24 hours a day, 365 days a year

Good old Towers Of Hanoi. An old coursework problem when I was doing my A-levels

Hello, everyone!

Spoler warning . . . Spoiler warning . . . Spoiler warning

If you enjoy the challenge of the "Towers" puzzle,
. . do not highlight the region below.


There are n disks on the leftmost stand.

[1] Move the smallest disk to the stand at its immediate right.

[2] Make another move . . . (There will be exactly one legal move!)

Repeat steps [1] and [2] until the puzzle is solved.

Note
If step [1] causes the smallest disk to go off the right end,
it "re-enters" at the left end.

1)The first problem is a classic. It is called Tower's of Hanoi. We can show by induction that the number of moves to solve the puzzle is 2^n-1.
Proof.
It is trivially true for n=1.
Assume it is true for n=k.
We want to show it is true for n=k+1.
Assume we have k+1 disks.
We know, by hypothesis that we can move the top k disks in that order onto another stand after 2^k-1 moves. Thus, the situation is that the original top k disks where moved and the bottom disk remains in its original position. We now move that disk, another move, and again by induction we know we can move the k disks onto it using 2^k-1 moves.
Thus, in total we wasted: (2^k-1)+1+(2^k-1)=2*2^k-1=2^{k+1}-1 moves.
Proof complete. The rest of the solution is trivial, I just wanted people to see how big exponentials really are.

2)The second problem is not mine, I first saw it several years ago from my number theory textbook. The question is stated a little more simply in it, i.e. by giving that lower bound. Thus, I decided to make it a little more challenging.

The idea is as follows, let N be the number that determines sufficiently large integers. Then say that n>N is an integer bigger than this number. We can therefore write n=N+k where k is an integer. Now, by Lagrange's four square theorem k is expressible as a square, sum of two squares, sum of three squares or sum of all four squares. The trick is to chose such an N which is simultaneously a square, two square, three square and four square sums. Because if k is a square we can write N as four squares. If k is a two square sum we can write N as three squares. If k is a three square sum we can write N as two square sum. And if k is a four square sum we can write N as a square. Thus, in all cases we have exactly 5 squares expressing n. Now the rest is trial and error. Just find what that N, lower bound, is what determines that point. Well, it has to be a square, so that rules out a lot of integers, and by just looking we soon find that N=169 is that lower bound which we need. Because it is a square, sum of two squares, sum of three and four squares. Thus, anything above this number is expressible as a sum of exactly five squares.