Dominoes!

Dr Pace Nielsen led today's math circle. The topic was dominoes. A domino is a rectangle made of two squares (see below).

Dr Nielsen:  How many different ways are there to arrange dominoes?
The students came up with four ways, shown below.

Rules:  No leaning a domino on its side, turning it upside down, cutting it in half.

Dr Nielsen:  Today's problems have levels!

Level 1.

Question: Can you fill up a 1x1 chessboard with dominoes?

Children:  No!  Because a domino doesn't fit!

Level 2.
Question:  Can you fill up a 2x2 chessboard with dominoes?

How many think you can? (Many hands).

OK you have a piece of paper and a pencil. Try it.

After a minute or two, a girl volunteered to show how to cover a 2x2 chessboard with dominoes.

Notation: draw a line through two squares to represent a domino.

Level 3.  Can you fill a 3x3 chessboard with dominoes?

The children worked for a minute.  After a while, several raised their hands to say no.

Why not?

Because dominoes have two squares each, so they cover an even number of squares.  But there are nine squares in a 3x3 chessboard, which is odd.

Level 4.  4x4.  Can you do it?

Again after a couple of minutes, a student came up and showed one solution on the board.

Dr Nielsen:  Have you figured out a pattern?

The students decided that you could always fill a chessboard with an even number of squares, but you could never fill a chessboard with an odd number of squares.


Level II.

Dr Nielsen:  Can you cover a 2x2 chessboard with dominoes if one of the corners of the board is cut out?

The children thought for a minute, and then answered no.

One child had a suggestion:  You can do it if you let the dominoes overlap.

Dr Nielsen:  Very good!  New rule.  No overlapping dominoes.

Then the children could see that there were an odd number of squares, so they couldn't cover this board with dominoes.

Next level:  What about a 3x3 board with one corner missing?

One child figured out a solution and showed it on the board.

Next level:  What about 4x4 board with a corner missing?


Immediate answer. NO!

Why not?

Because there are an odd number of squares.

One of the children who knew how to multiply explained that an even number times an even number is even, and if you take away one, you'll get odd.

Those children who didn't know how to multiply could just count:  15 squares.  Odd, so you can't cover it with dominoes.

Next level:  What about a 5x5 board with a corner missing?

 After a minute, one child finished and raised his hand.  Dr Nielsen asked that child to try the 7x7 board while the others finished.

After a few more minutes, when many hands were raised, Dr Nielsen had the children give him the answer.

Can you cover a 5x5 board with a corner missing?  YES!

Can you do 6x6?  (Immediate answer)  NO!

What’s the pattern?

The children decided you could always do odd sided squares with a corner missing (3x3, 5x5, 7x7), but you could never do even sided squares with a corner missing (2x2, 4x4, 6x6).


LEVEL III

Level 1.  Can you fill a 3x3 chessboard with dominoes when there are two opposite corners missing?

Children:  No.  Because there are seven squares left over.  (They seemed to be figuring out a way to solve these problems!)

Level 2.  What about a 4x4 board with opposite corners missing?

One child:  Yes!  I just need to figure it out.

Dr Nielsen:  Ok.  Figure it out.

After a few minutes, the children changed their minds.  No!  You can't do it!

Dr Nielsen:  Are you sure?

After a couple more minutes, with still no children who had found a solution, Dr Nielsen asked, How many squares are left?

Children:  14.

Dr Nielsen:  14 is even.  It’s even!  So you can do it right?

Children:  No.

Dr Nielsen:  Why not?

One child suggested that the board had been "cut up too much."

So Dr Nielsen tried:

 Dr Nielsen:  Well, that didn't work.  But maybe I just chose poorly.  Maybe I can do it if I'm more careful.

(The children were skeptical, but without a good answer as to why not, he moved on.)

Dr Nielsen:  We know we can’t do a 5x5 chessboard, because when we remove 2 corners there will be 23 squares, which is odd.  Let’s try 6x6. 

The children worked on it for several minutes, with Dr Nielsen asking every now and then how many people needed more time?  Since no one had quite finished, he let them keep working.

After a while, he brought the group together to talk about the chessboard.  

Dr Nielsen:  Let's color the 6x6 chessboard black and white.

How many squares are there total?  36

How many black squares?  18

How many white squares?  18

If we remove the top left corner and the bottom right corner, how many black squares and how many white?

18 black, 16 white!

What does a domino cover?  1 black square, and one white square.

So can you cover a 6x6 chessboard with opposite corners removed?

No!  There aren't enough white squares!

A student noticed that for an odd number, like a 5x5 chessboard, opposite corners had different colors.  They asked, could you cover a 5x5 chessboard with opposite squares removed?

Dr Nielsen:  Good question.  Let's try it!

After a minute, the students realized that they had already figured this problem out -- there were an odd number of squares, so no, they couldn't cover this chessboard with dominoes.

One last thing.

With the remaining time (not much of it), Dr Nielsen had the students create an addition table on the board, adding numbers from 1 to 5.

After they had finished the table, he pointed out that they could make an addition table for even and odd numbers.

And for those who knew multiplication, they could do a multiplication table for even and odd numbers.

And then we broke for cookies.

Checkerboard problems

For today's math circle, I adapted a couple of activities from James Tanton's book Solve This: Math Activities for Students and Clubs. 


The above book, by the way, is a great book that describes activities that Tanton used while running a math club for college-aged students.  Unfortunately, my students are aged 5 through 8, so not everything in his book will work in our class.  Some of the activities are a little too mathematically sophisticated for children who can't yet multiply.  And other activities require a bit more attention span than that of your typical kindergartener.  But all that said, in fact a surprising number of the activities in the book work even for this age group, especially with some minor modification.  Today's activity was one of those. 

Specifically, we were looking at problems adapted from Chapter 13 of the book.  If you're following along with your own copy of Tanton's book, you'll see that to the activities he gave, I added a couple of easier cases to work through first (to warm up the younger children), and I simplified one activity slightly (reduced from a 5x5 grid to a 3x3 grid).  Also, I stuck with just two activities rather than try to do all three or more activities listed in there.  But otherwise, my activities were pretty similar to his.

Preparation:
1.  Prepare one copy of "easy" grid puzzles below for each child, and at least three copies of the "hard" grid puzzles for each child. 
2.  Bring enough pencils for each child.
3.  Just before class, I used masking tape to mark nine x's on the floor for the people-shuffling activity (2nd activity below).

Grid Puzzles.

I learned from last week that any activity I start right at 9:00am (when our math circle starts) will have to have its rules repeated as kids come a little late.  So today, I started with an activity with paper and pencil that was easy to explain to late arrivals.

As the children arrived, I handed out pencils and a paper with the following squares printed on them:

The rules of the game are the following.  Start with your pencil in the square marked with the X.  Draw a path through the grid that meets each square in the grid exactly one time.  The path may leave a square through any of its sides, but it can't run diagonally out of a square.  (Examples are below if that explanation doesn't make sense.)

Most of the children figured out paths that worked for the above four puzzles quickly, especially the older ones.  As the children finished, I handed them a harder puzzle.  Here is what the harder puzzle looked like. 

Puzzle #5 was difficult, but the students were having particular trouble with puzzle #6.  I brought several extra copies of the puzzle so that when they had erased too many times, they could get a fresh puzzle and try again.

I let them work on this for about 15 minutes.  Then I polled them to see who had finished their puzzles.

Everyone had finished puzzles #1 through 4.  I let the children raise their hands and describe different solutions to puzzle #1.  Here are three that they came up with.

I asked for a show of hands on who had finished puzzle #6.  No one had.  Same for #7.  ("We didn't get to #7 because we couldn't finish #6!" explained one child.)

Rather than talk more about these puzzles, I told the children we were going to take a break from the puzzles and do the next activity.

People shuffling.

I asked for four volunteers to come play the next game.  They stood on X's marked with masking tape on the floor in a 2x2 grid. 

The rules of the game are the following.  Every student must move exactly one space.  They can move side to side, but not diagonally.  The goal is to get every person to move to a different space in the 2x2 grid.

I had my four volunteers run through an example.  They switched places in pairs, which worked!  I then asked all the students to get into groups of four and see if they could figure out different ways of solving the problem. 

We took about five minutes, then put some solutions on the board. 

The children could switch places in pairs in two different ways, or they could move in a cycle of four two different ways. 

I then asked for nine new volunteers, and asked the children to stand on a 3x3 grid.  The rules were the same, the objective the same:  Everyone has to move exactly once, with no diagonal moving allowed. Ready set go.

Their first attempt didn't work -- someone on the corner got stuck. 

One eager and clever little girl had an idea then.  Have the middle person move first, then everyone else switch around them.  But unfortunately, that didn't work either.

Another equally clever girl suggested a new alternative.  But hers didn't work either!

I then suggested we try moving one person at a time, counting how many moves were made before someone stepped back into an empty space.  A sequence of legal moves of people that ended with someone taking the empty space was called a cycle.  We worked through a few cycles, and found that they all had to have an even number of steps.

Why was the number even?

This is where things got a little tricky for the younger kids.  I showed them that every time someone moved left in a cycle, someone else had to move right.  Every time someone moved up, someone else had to move down.  That meant moves in the cycle happened in pairs -- so there were an even number of moves!

A couple of the older children seemed to get it now.  Because there were nine children, but cycles had an even length, the only way to get everyone to move would involve an even number of children.  So one of the nine would be left out.

(I don't know if they really got it, but at that point, the littler ones were getting restless, so I had them all sit down again.)

I had a couple other moving puzzles prepared, but the students voted to go back to the grid puzzles.

Grid Puzzle Solutions.

One of the girls who had been helping with the 3x3 people-shuffling game raised her hand and said she thought that solving puzzle #6 (grid puzzle above) was impossible, just like moving nine people around in a 3x3 grid was impossible.

I announced to the class that she was right!  Puzzle #6 was impossible.  And our new goal was to figure out why. 

Someone suggested that maybe it was because there were 25 squares -- an odd number.  But another child pointed out that puzzles #4 and #5 also had an odd number of squares, but we were able to solve them.

Then a boy noticed that in puzzle #6, there were only 3 ways to begin, but in puzzle #5 there were 4 choices for how to begin.  That was a good idea.  But then someone realized that in puzzle #4, there were only 2 choices for how to begin, but everyone had solved puzzle #4. 

I told them I would give them a hint.  I drew the 5x5 grid on the board, and started coloring the squares in a checkerboard pattern. 

I then let them think for a while and talk about the problem with the others at their table. 

They noticed that #4 and #5, which were solvable, started on shaded squares.  But #6 and #7, which were not, started on white squares. 

Was starting on white squares the problem?  Maybe, but puzzle #3 also started on a white square in the 4x4 grid. 

By then the children realized the problem was with the 5x5 grid -- something different was happening with that grid than with the 4x4 grid.  But what?

After another minute or two, a girl raised her hand and told me she had counted white and shaded squares.  (This was the right idea!)

With all the children, we counted 13 shaded squares, but only 12 white squares.

After another minute, I asked the children to tell me what colored squares my path stepped through.  If I started on a shaded square, where would I go next? 

To a white square.

Why not a shaded square? 

Because you can't move diagonally.

So then we realized that if your path started on a shaded square, it would proceed as follows:
Shaded - white - shaded - white -shaded - white - ... through 25 squares (in the 5x5 grid case).

If you started on a shaded square, where would it end?

After a minute or so, they figured out that it would end on a shaded square if there were 25 squares.

Then we counted.  That meant it would run through 13 shaded squares, and 12 white ones.  Hey!  That's how many we had!

Then I talked about a path that started on a white square.  Where would it end?

We stepped through the path, and it looked like this:
White - shaded - white - shaded - ... - shaded - White!

It ended on a white square.

"But that's impossible!" shouted one little boy.  "You would have to have 13 white squares!"

Exactly.

We all counted together.  A path that started on a white square would have to go through 13 white squares and 12 black.  But we didn't have 13 white squares, we only had 12 white squares!  That meant that the puzzle I gave the students was impossible!

It was time for cookies then.  But before I let them get a cookie, I told them conspiratorially that they ought to take a copy of the puzzle home and give it to their parents to try. 

They thought that was a hilarious idea, and every one of them came up to get an extra copy of the puzzle.

And to get cookies.

Summary.

I think this activity worked very well for kids this age.  Because there were different puzzles of different difficulty level, it engaged all the students regardless of age.  Although not all the children seemed to understand all the explanations (especially cycles of even length), they seemed to be having fun and learning something.  I would do this activity again for this age group.   

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.