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)

__________________

To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


"Democracy has proved only that the best way to gain power
over people is to assure the people that they are ruling
themselves. Once they believe that, they make wonderfully
submissive slaves." - Joseph Sobran

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

__________________
Got a Physics question? Come on over to
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.

To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


"I must not fear. Fear is the mind killer. Fear is the little death that brings total obliteration. I will face my fear. I will permit it to pass over me and through me. And when it has gone I will turn the inner eye to see its path. Where the fear has gone there will be nothing. Only I will remain." - The Litany Against Fear, "Dune" by Frank Herbert

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

__________________
Das Rätsel gibt es nicht.
Wenn sich eine Frage überhaupt stellen läßt, so kann sie beantwortet werden.

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

__________________
Vaiyo A-O
A Home Va Ya Ray
Vaiyo A-Rah
Jerhume Brunnen G
Vaiyo A-Rah
Jerhume Brunnen G

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.

__________________

To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


"Democracy has proved only that the best way to gain power
over people is to assure the people that they are ruling
themselves. Once they believe that, they make wonderfully
submissive slaves." - Joseph Sobran