Question

Discrete Math.

An old folktale says that in a faraway monastery there is a platform with three large posts on it and when the world began there were 64 golden disks stacked on one of the posts. The disks are all of different sizes arranged in order from largest at the bottom to smallest at the top. The disks are being moved from the original post to another according to the following rules:

1. One disk at a time is moved from one post to another.

2. A larger disk may never rest on top of a smaller disk.

3. A disk is either on a post or in motion from one post to another.

When the monks have finished moving the disks from the original post to one of the others, the world will end. How long will the world exist? A useful strategy is to try out smaller cases and look for patterns. Let Nk be the minimum number of moves that are needed to move k disks from one post to another. Then N1 is 1 and N2 is 3. (Verify this.)

1. By experimenting, find N3, N4, N5.

2. Describearecursiveprocessfortransferringkdisksfrompost1topost3.Write an algorithm to carry out your process.

3. Use the recursive process in Question 2 to develop a recurrence relation for Nk .

4. SolvetherecurrencerelationinQuestion3andverifythesolutionbycomparing the results produced by the solution and the values found in Question 1.

5. From Question 4 you have an explicit formula for Nk. Use mathematical in- duction to prove that this statement is true.

6. If the monks move one disk per second and never make a mistake, how long (to the nearest year) will the world exist?

Answer 1

Rules given:

1. One disk at a time is moved from one post to another.

2. A larger disk may never rest on top of a smaller disk.

3. A disk is either on a post or in motion from one post to another.

Let Nk be the minimum number of moves that are needed to move k disks from one post to another. Then:

To answer how long it will take our friendly monks to destroy the world, we write a recurrence (let's call it M(n)) for the number of moves MoveTower takes for an n-disk tower.

The base case - when n is 1: The monks just move the single disk directly, therefore:

N (1) = 1

In the other cases, the monks follow our three-step procedure.

1. First, they move the (n-1)-disk tower to the spare Tower; this takes N(n-1) moves.

2. Then the monks move the nth disk, taking 1 move.

3. And finally, they move the (n-1)-disk tower again, this time on top of the nth disk, taking N(n-1) Noves.

This gives us our recurrence relation,

N(n) = 2 N(n-1) + 1         …(a)

N (2) = 2 N (1) + 1

N(2) = 2.1 + 1                  (as N(1) is 1)

N(2) = 3                           Hence, verified

1) Find N3, N4, N5

Using the above eqn: (a)

N(k) = 2N(k-1) + 1

N(3) = 2N(3-1) + 1 = 2N(2) + 1 = 2.3 + 1 = 7

N(4) = 2N(4-1) + 1 = 2N(3) + 1 = 2.7 + 1 = 15

N(5) = 2N(5-1) + 1 = 2N(4) + 1 = 2.15 + 1 = 31

2) To move n discs from Source Tower to Destination Tower, we can derive an algo like the following steps:

a. Move n−1 discs from A to B. This leaves nth disc alone on Source Tower.

b. Move nth disc from A to C.

c. Move n−1 discs from B to C, so they sit on nth disc.

For E.g., If we take n=3

1. Move 2 discs from A to B (using C) à This is a recursive call.

2. Move a disc from A to C directly.

3. Move 2 discs from B to C (using A) à This is a recursive call.

So, the algorithm (Considering “C” as Base Language)

void TOH(int n, int A, int B, int C)

{

          if (n>0)

          {       

                    TOH(n-1, A, C, B);

                    printf(“Move a disc from %d to %d”, A, C);

                    TOH(n-1, B, A, C);

}

}

3) By looking at Question 2 of solutions, we can guess that

N(n) = 2ⁿ - 1

4) Verifying the solution by comparing the results produced by the solution in Question 3 and the values found in Question 1.

N(3) = 2³ - 1= 8 - 1= 7

N(4) = 2⁴ - 1= 16 - 1= 15

N(5) = 2⁵ - 1= 32 - 1= 31

5) The Explicit formula N(k) = 2^k – 1

We can verify this easily by plugging it into our recurrence.

N(1) = 1 = 2¹ - 1
N(n) = 2 N(n - 1) + 1 = 2 (2^{n - 1} + 1) - 1 = 2ⁿ + 1

Since our expression 2ⁿ+1 is consistent with all the recurrence's cases.

6) If the monks move one disk per second and never make a mistake, then

the monks will move 2⁶⁴+1 (about 18.45x10¹⁸) disks. If they are really good and can move one disk a millisecond, then they'll have to work for 584.6 million years. It looks like we're safe.