Results 1 to 6 of 6

Math Help - Problem 19

  1. #1
    Global Moderator

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Singular's Avatar
    Joined
    Dec 2006
    From
    Solo, Java
    Posts
    57
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Glaysher's Avatar
    Joined
    Aug 2006
    From
    Newton-le-Willows
    Posts
    224
    Good old Towers Of Hanoi. An old coursework problem when I was doing my A-levels
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779
    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.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    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.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum