Tuesday, March 30
More on the fourth dimension and the tower of Hanoi Puzzle.
Cards and the fourth dimension.
(clubs,diamonds,hearts,spades)
one card of a suit in your hand is indicated by a 1. 0 indicates that the card of that suit is on the table.
These also represent points on the hypercube.
(LeftRight, Back Front,Top Bottom,Inside Outside)
(1,1,1,1) (0,0,0,0)
(1,1,0,1) (0,0,1,0)
(0,1,0,1)
(1,0,1,0)
(0,0,0,1)
(1,1,1,0)
(0,0,0,0)
(1,1,1,1)
This sequence can be treated as a tour on the hypercube.
Hamiltonian Tour: move through each vertex once and only once.
A Hamiltonia Tour on the cube can be thought of as first going aroundthe
vertices on the bottom square and then moving to the top square and moving
through those vertices.
The Tower of Hanoi
(clubs,diamonds,hearts,spades)
(1,1,1,1) (0,0,0,0)
(1,1,0,1) (0,0,1,0)
(0,1,0,1)
(1,0,1,0)
(0,0,0,1)
(1,1,1,0)
(0,0,0,0)
(1,1,1,1)
Hamiltonian Tour: move through each vertex once and only once.
13 cards : (5,3,0,5) (4,2,6,1)
Other ways to think about the hypercube:
Other ways to use coordinates:
The Tower of /Hanoi (Click on this to go to Java website)
The general problem: (illustrated with three objects)
Move objects that have an order (size) from one place to another using only
a third place for "storage". No larger object can be placed on top of a smaller
object during the move. Move only one object at a time!
Get experience going over the solution for the 3,4 and 5 tower puzzles.
Elimination tournament for doing the puzzle fast. Prizes awarded!
A Solution for the 3 Tower of Hanoi Puzzle.
(Using playing cards 1,2,3)
Card- Post Changes to cards 0-1 Changes to
cards
0 for even numbers ,
1 for
odd numbers
(0, 0, 0)
(0, 0, 0)
1. 1 → B (1, 0, 0)
(1, 0, 0)
2. 2 → C (1, 1, 0)
(1, 1, 0)
3. 1 → C (2, 1, 0)
(0, 1, 0)
4. 3 → B (2, 1, 1)
(0, 1, 1)
5. 1 → A (3, 1, 1)
(1, 1, 1)
6. 2 → B (3, 2, 1)
(1, 0, 1)
7. 1 → B (4, 2, 1)
(0, 0, 1)
Notice the last column give a hamiltonian tour of the vertices of the cube.
Now try the same organization for the 4 tower puzzle.
Record your moves. Assume that 1 represents the ace and the posts are labelled
A, B and C.
[Use the seven moves below from the 3 tower puzzle as a start.] Record also
the coordinates in 4 dimensional space for the number of changes made to
the 4 cards and the 0-1 switches.
Solution of the 4 Tower of Hanoi Puzzle.
Card→Post Changes to cards
0-1 Switches to cards
(0, 0, 0, 0) (0,
0, 0, 0)
1. 1 → B (1, 0, 0, 0)
(1, 0, 0, 0)
2. 2 → C (1, 1, 0, 0)
(1, 1, 0, 0)
3. 1 → C (2, 1, 0, 0)
(0, 1, 0, 0)
4. 3 → B (2, 1, 1, 0)
(0, 1, 1, 0)
5. 1 → A (3, 1, 1, 0)
(1, 1, 1, 0)
6. 2 → B (3, 2, 1, 0)
(1, 0, 1, 0)
7. 1 → B (4, 2, 1, 0)
(0, 0, 1, 0)
8.
9.
10
11.
12.
13.
14.
15.
This finds a Hamiltonian tour on the hypercube!
2. Discuss how you would solve the 5-tower puzzle.
Move 4, then 1, then 4... so
How many moves would it take to solve the 5-tower puzzle?
15 + 1 + 15 =31 moves.
A 5 dimensional hypercube would use coordinates
( a,b,c,d,e) with a,b,c,d, or e either 0 or 1.... giving 2*2*2*2*2 = 32 vertices.
How many moves would it take to solve the 6-tower puzzle?
31 + 31 +1= 63
Based on the actual time it takes you now to do the 4-tower, how long do
you think it would take you to do the 8-tower puzzle? Discuss the reasoning
for your estimate briefly.
we used 10 seconds for 15 moves ( our fastest player's time!)
2 *2 *2* 2* 2* 2* 2* 2 -1=255 moves
255 *10/ 15 = about 170 second = about 3minute
Note: Dali use of the hypercube unfolded.
[connection w/ Banchoff}
What about a 5 dimensional cube? or a 6 dimensional cube.....