Tower of Hanoi

I've been traveling for a few weeks, missing the Saturday math circles.  I'll try to get lesson plans from the other instructors to post here.  Meanwhile, here was this week's activity.

One idea from the following two games is to try to simplify a problem by first examining a simpler problem.

GAME 1: STANDING AND SITTING
 
I lined up four chairs in a row, all facing in one direction, and asked for four children to volunteer to help me out.  These children would be standing up and sitting down, following the rules below.


Game rules:
1. The person in front could stand and sit anytime.
2.  Everyone else could only stand or sit when the person right in front of them was standing, but everyone else in front of them was sitting down.

We ran through a few examples to help everyone understand the rules.

Example 1.  Everyone is sitting down.  Who can move?

Answer:  The person in front can stand up, but no one else can move.

Ok.  Now the person in front is standing.  Who can move?

Answer:  The 2nd person can stand up, or the person in front can sit down.  But that's all.

Example 2.  Suppose the first two people are standing up.  Who can move?

Answer:  Be careful!  Some of the children thought that the third person could stand up now, but they can't.  Although the person right in front of the 3rd person is standing, because the 1st person is also standing, the 3rd person can't stand now.

So the only options are the 2nd person can sit down, or the 1st person can sit down.

If the 1st person sits down, then the 3rd person can stand.

After we went through these examples, I had the children try to help me to get the last person, and only the last person, standing.

Goal:  Make the last person be the only one standing.  

A couple of the students caught onto the rules quickly and directed the sitting and standing of the others.  As you try this on your own, you'll notice that the person in front has to stand up and sit down a lot.

We successfully got the 4th person, and only the 4th person, standing with the four original volunteers.  Meanwhile, a lot of new students had come to the class.  I explained the rules again, went over the above examples again, and asked the students to break into groups of four and try it on their own for a few minutes.

(Note:  This was one of those times when I was very glad to have extra parents around.  The parents helped organize the children into three groups of four, and helped to get them started thinking about the problem -- who should be standing and who should be sitting?)

After several minutes, all three groups had been able to get the last person, and only the last person, standing.  I asked them to count how many steps it took them to get that person standing.  One of the groups had already counted, the others hadn't.  For the group that had done the counting, I asked them to figure out how many steps it would take to get the last person standing if there were five people in the row instead of just four.

Everyone worked for a while.  I handed out pencil and paper to those who wanted to use it to help them count.  After a few minutes, when all the groups seemed to have gotten mixed up somewhere, I stopped them.

"How many people are finding this hard?" I asked, and roughly 3/4 of the people in the room raised their hands -- including several parents. 

This seemed like a good time to review our rules of Math Circles, so I had the students help me remember them.  Here is the order in which the students gave the rules:

Rules of Math Circles
1.  Make mistakes.
2.  Have fun
3.  Help others have fun
4.  Ask questions.

I pointed out that a lot of us had already made mistakes, so we were doing the right thing.

Back to the problem:  Now that everyone had a good idea about what the standing and sitting game involved, I asked them to think about a simpler problem.

What if there was only one person in the row?  Was this an easier problem?

YES!

How many steps did it take to get one person in the row standing?

ONE!

And here it is:

What if there are two people in the row?  How many steps did it take to get two people standing?

This is a slightly harder problem, but a few of the children figured it out quickly.  We went over the answer together on the board.

3 steps to get only the last person standing when there are two people.

What about when there are three people?  What about four?  I gave everyone a sheet of paper, and had them try to figure out how many steps this would take.

While they worked, I walked around the room talking to the children and asking them to explain what they were getting.  Again it was really helpful to have parents around.  A couple of the parents were asking the children questions and helping them to figure out the answers.

After about five minutes, I called everyone together and asked for answers.  The children had figured out the following.

3 people in the row:  7 steps
4 people:  15 steps
5 people:  31 steps  (not all the groups had figured out this one)

A couple of the groups were trying to figure out a pattern.  I gave them a hint.

When there are five people in the row, what does the row have to look like before the last person can stand up?

Answer:  The 4th person, and only the 4th person, must be standing in order for the last person to be able to stand.

I put a picture like the one above on the board.  Then I put my hand over the 5th person in the row.

Ok.  Notice that in order to get the 5th person standing, you first need to get the 4th person, and only the 4th person standing.  But we just figured out how many steps it takes to get the 4th person, and only the 4th person standing.  Right?  How many steps?

Several of the children realized at this point that this was the solution to the previous problem.  It took 15 steps.  With that hint, I asked them to see if they could figure out a pattern, and if so, figure out how many steps when there were 6 people, 7 people, and 10 people.

Again I gave them about five minutes.

One little boy figured it out quickly on his own after I repeated my hint again.

"How many steps does it take to get the 4th person, and only the 4th person, standing?" I asked.

"15 steps," he said.

"And then when the 5th person stands up, how many steps is that?"

"One more," he said.

"And then are we done?" I asked.

"No," he said.  "You need to get everyone else sitting down."  And then he thought for a second.  "And that will take 15 more steps!" he concluded.

Meanwhile, a couple of groups had figured out a pattern:  double the last number and add one.  About 2/3 of the students were still following, having fun doubling numbers and adding one.  The others were lost or distracted.  I tried to help those who weren't following for a couple of minutes, but by now it was time to move onto a new game.  I asked those who had finished to give me the numbers of steps.  Here they are.

6 people:  63 steps
7 people:  127 steps
10 people:  1023 steps


GAME 2:  TOWER OF HANOI

You can read about the Tower of Hanoi on Wikipedia, for example.


Basically, you have a stack of disks, each of a different size, and three pegs.  You move the disks between the pegs, according to the following rules. 

Tower of Hanoi Rules:
1. You can move only one disk at a time.
2.  A disk can never be moved on top of a smaller disk. 

I gave each child four paper disks in four sizes, and had them make three X's on their paper for the pegs.  We went through an example on some legal moves on the board.

If all the disks are stacked up, what is the first move that we make?

We move the small one to one of the other X's.

Now we want to move the next smallest circle (red in the figure).  But it can't go on top of the smallest circle, so it has to go to the other X.

"Oh, this is easy!"  shouted one boy.

Goal:  Move all the disks from one X to another, following the rules.

I let them work on their own for a few minutes.  All the children were interested again and playing.  After walking around a bit, I noticed that a couple of students were moving more than one piece at a time, so I reminded them that they had to move only one disk at a time.

"Oh, that's hard!" said the same boy who had declared it was easy a moment ago.


Nevertheless, after a few minutes he and the girl next to him had finished.  After a few other children had finished, I asked everyone to count how many steps it took to move the whole stack of disks. 

A couple of students raised their hands to show me how they had solved the problem.  I watched one boy show me how to move the stack in 16 steps.  Another could do it in 17 steps.  One little girl was excited to show me how to move the stack in 14 steps, but it turned out that her solution really used 15 steps.

At this point, we were nearly out of time, so I called everyone together.

"What if we only had one circle?" I asked.  "How many steps to move that circle to another peg?"

ONE!

I wrote "One circle" on the board next to "One person" from the previous standing/sitting game.

One circle:  1 step.

"What if we had two circles?"

After a couple of seconds, a few children shouted out:

Three steps!

Two circles:  3 steps.

"What if there are three circles?"

There was silence for longer at this point, while some of the children tried to quickly figure it out.  One little boy in the corner was prompted by his mother to raise his hand, so I called on him.

7 steps.

Now the board looked something like this:

Standing/ Sitting game			Towers of Hanoi
1 person	1 step		1 circle	1 step
2 people	3 steps		2 circles	3 steps
3 people	7 steps		3 circles	7 steps
4 people	15 steps
5 people	31 steps

We were out of time, but I told the children to think about the patterns and see if they could figure out what happened at home, and why. 

As we distributed cookies, a couple children came to me and told me excitedly how many steps they had needed to move circles.  Over all, they seemed to have had fun and to have learned something.