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

Results 1 to 6 of 6

- Feb 12th 2007, 11:49 AM #1

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10

## 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)

- Feb 12th 2007, 11:56 AM #2

- Feb 12th 2007, 04:10 PM #3

- Feb 13th 2007, 12:28 AM #4

- Feb 14th 2007, 02:53 PM #5

- Joined
- May 2006
- From
- Lexington, MA (USA)
- Posts
- 12,028
- Thanks
- 846

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.

- Feb 19th 2007, 09:03 AM #6

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10

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.