MESSAGE
| DATE | 2015-02-27 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [NYLXS - HANGOUT] Read the FUCKING NOTES
|
The minimum number of moves required to solve the Towers of Hanoi puzzle
with n disks is ***2^n ? 1***.
Proof is by mathematical induction:
Basis: n = 1. Number of moves required is 2^1 ? 1 = 1.
Inductive step: Assume result true for n disks. Suppose now n + 1 disks are
given. In order to move the largest disk from its initial location at
the bottom
of pile 1 to the final location at the bottom of pile 3, we clearly need
to first
have moved all other disks to pile 2, which by inductive hypothesis
requires at
least 2^n ? 1 moves. Then one move is required to move the largest disk from
pile 1 to pile 3. Finally at least 2n ? 1 moves are required to move the
remaining
disks from pile 2 to pile 3. So the total number of moves required is at
least
(2^n ? 1) + 1 + (2^n ? 1) = ***2^(n+1) ? 1***.
What don't i understand hear
|
|
