# Tower of Hanoi

### Task 142 ... Years 2 - 10

#### Summary

This classic logic task is a challenge at any level. The discs must be transferred from one spike to another without a larger disc every being on top of a smaller one. As students work with it however, they discover movement patterns and where there is a movement pattern, there will be a number pattern. Indeed, the powers of two pattern that appears out of the puzzle is what allows the task to be generalised as indicated in the story on the card.

This cameo has a From The Classroom section which shows how two teachers created a home made set of Tower of Hanoi puzzles from simple materials. Other teachers have also provided ideas for efficiently and effectively making the equipment. In addition it has the equivalent of an investigation guide in the form of free Windows software created by George Dimitriadis which challenges your students to move any number of discs from 2-20. You will find this in the whole class investigation section.

#### Materials

• Base board with three spikes
• A set of wooden discs in decreasing sizes

#### Content

• reasoning strategies such as breaking a problem in to smaller parts
• number patterns
• powers of two
• exponential growth
• graphing

#### Iceberg

A task is the tip of a learning iceberg. There is always more to a task than is recorded on the card.

One way to approach this task is to consider options at each step and look ahead one move to see which is the better one. Careful examination of each step in this way may lead to a solution.

On the other hand, the legend told on the card suggests that other numbers of discs could be used, so why not apply the problem solving strategy of Try a simpler problem to see if the key movement patterns can be discovered and then applied to the problem on the card. One student described such a pattern as:

If you have an odd number you put the piece first where you want it. Where you don't want the pile you put it if there is an even number.
This insight makes perfect sense once you have personal experience with attempting to solve the puzzle.

The number pattern that results from trying the simpler cases is 3, 7, 15, 31, 63 and so on which is very close to 4, 8, 16, 32, 64 and so on. The other experience resulting from this approach may be to see that the moves for any tower, relate to the moves for the previous tower as follows:

• Assume the previous tower has been solved.
• The next tower is the previous one atop a new base disc.
• Moving the discs above the base disc is the same as moving the previous tower.
• This reveals the new base which can be shifted in one move.
• Then the previous tower can be shifted onto the translated base disc in the same number of moves as before.
Consequently the students might interpret the sequence above as twice the previous number of moves plus one. This way of thinking is directly related to the sophisticated method of mathematical proof known as Mathematical Induction. Of course the pattern could also be interpreted as 2n - 1. What would be the physical explanation from which this formula evolved?

Uncovering the number of moves for 1, 2, 3, 4, ... discs produces a set of ordered pairs, ie: (No. of discs, No. of moves). The graph of these pairs demonstrates exponential growth; that is, growth governed by the exponent (or power) in the equation. In this case that exponent is the number of discs.

To further extend the task include the time element suggested by the historic story. Euro-centric history records this puzzle as being invented by the French mathematician Edouard Lucas and being first marketed as a toy in 1883. However, Lucas was no doubt influenced by an older Hindu legend usually know as the Tower of Brahma.

#### Whole Class Investigation

Tasks are an invitation for two students to work like a mathematician. Tasks can also be modified to become whole class investigations which model how a mathematician works.

To use this task as a whole class investigation you could make use of the many software applets available on the Web which simulate the puzzle. But you don't need to leap any further into the ether than right here.

George Dimitriadis, Montmorency Secondary College, has provided this Tower of Hanoi program (318Kb) for all to download, install and share. The link is to a zipped file. You will only need to unzip to reveal the Tower of Hanoi folder. Within that you will find hanoi.exe. Double click and you're away.

The program contains instructions and a link to open a folder that the user can store files for reference. The program can be run on the network. All that is required is that the folder resides in a location and a link to the hanoi.exe file is made available. The link opens the folder and allows any other file/folder/image to be placed there independently of the program. If the program is to be accessed on the network, the advantage of the link is that it can be a shared folder between all users.

Teachers who prefer real hands-on as opposed to simulated hands-on can easily make multiple versions of the puzzle with different size washers on nails banged into wood off-cuts. In co-operation with the craft faculty, students may be able to make the school's class set. Another alternative is shown in From The Classroom below.

The whole class investigation would be built around solving the puzzle, sharing strategies for doing so, building and exploring a table of pairs.

At this stage, Tower of Hanoi does not have a matching lesson on Maths300.

#### Is it in Maths With Attitude?

Maths With Attitude is a set of hands-on learning kits available from Years 3-10 which structure the use of tasks and whole class investigations into a week by week planner.

The Tower of Hanoi task is an integral part of:

• MWA Pattern & Algebra Years 5 & 6
• MWA Pattern & Algebra Years 9 & 10

This task is also included in the Secondary Library Kit. Solutions for tasks in the latter kit can be found here.

## From The Classroom

#### Riverina District, New South Wales

Karen Henry and Carolyn McGuigan
Karen and Carolyn designed and built this interesting class set of Towers of Hanoi.

Do you know of other easy ways to create enough equipment to explore the
whole class investigation life of this task?

Matt Skoss
Matt Skoss used Task 142, Tower of Hanoi, in a workshop he was leading. The best versions of the problem involve monks and spikes and discs made of gold, but Matt's equipment was a little more down market. Still it was good enough to cause Amie Albrecht, Uni S.A., to ask about the source of his small size class set of equipment. Apparently she had very large ones which are a pain to lug around.

Matt shot an email around to a few contacts who might want to join a bulk purchase to bring the cost down (sometimes things that don't glisten cost gold). Matt's email included this piece of workshop feedback:

My favourite experience with Towers of Hanoi was a workshop in Adelaide featuring them about 10 years ago (at an ex-monastery!) with about 80 teachers. I'd done probably my best session ever in the day-long workshop with primary & secondary teachers. Everything flowed all day, and the group was really enthusiastic about working on some Maths.

At the end of the day, a lady came up to me and asked for permission to take a photo of one of my home-made sets. She then said her hubby wasn't gonna get dinner that night until he had made her a class set!

About 7:45 pm that night, I received a photo of the class set, with her hubby getting stuck into his dinner in the background of the photo! It was a very literal response to 'The 12 Day Challenge' I offer teachers in professional learning settings - to put 2-3 ideas into practice inside the next 12 days, 'cos after 12 days, you never will!

Matt's email received a number of responses but this one from Damian Howison, St. Mary Mackillop College, Swan Hill, opens new doors.
I have literally just returned from the Swan Hill Woodworkers Club with 50 sets of algebra blocks. I rocked up at their shed just last week where there were several "old fellas" doing different projects. I showed them one set of the blocks and said that I'd love another 50 sets of these because our others were quite depleted. They were only too happy to help and exactly one week later (today) phoned to let me know I could come around and pick up the blocks and a very modest bill.

I'm only kicking myself I didn't go about it this way sooner.

Now there's a thought. Local Woodworkers Clubs and Men's Sheds could be approached to make one off, or class sets, of Tower of Hanoi and several other tasks. Scan your eye over the Task Library photos and see which ones could be crafted in this way. Schools would be supporting the community service these centres provide and the centres would be supporting the schools.