# Math for eight-year-olds: graph theory for kids!

This morning I had the pleasure to be a mathematical guest in my daughter’s third-grade class, full of inquisitive eight- and nine-year-old girls, and we had a wonderful interaction. Following up on my visit last year (math for seven-year-olds), I wanted to explore with them some elementary ideas in graph theory, which I view as mathematically rich, yet accessible to children.

My specific aim was for them to discover on their own the delightful surprise of the Euler characteristic for connected planar graphs.

We began with a simple example, counting together the number of vertices, edges and regions. For counting the regions, I emphasized that we count the “outside” region as one of the regions.

Then, I injected a little mystery by mentioning that Euler had discovered something peculiar about calculating $V-E+R$.  Could they find out what it was that he had noticed?

Each student had her own booklet and calculated the Euler characteristic for various small graphs, as I moved about the room helping out.

Eventually, the girls noticed the peculiar thing — they kept getting the number two as the outcome!  I heard them exclaim, why do we keep getting two?  They had found Euler’s delightful surprise!

The teachers also were very curious about it, and one of them said to me in amazement, “I really want to know why we always get two!”

With the students, I suggested that we try a few somewhat more unusual cases, to see how robust the always-two situation really was. But in these cases, we still got two as the result.

The girls made their own graphs and tested the hypothesis.

Eventually, of course, I managed to suggest some examples that do in fact test the always-two phenomenon, first by looking at disconnected graphs, and then by considering graphs drawn with crossing edges.

In this way, we were led to refine the $V-E+R=2$ hypothesis to the case of connected planar graphs.

Now, it was time for proof.  I was initially unsure whether I should actually give a proof, since these were just third-graders, after all, and I thought it might be too difficult for the students. But when the teachers had expressed their desire to know why, they had specifically encouraged me to give the argument, saying that even if some students didn’t follow it, there was still value merely in seeing that one can mount an argument like that.  Excellent teachers!

The idea of the proof is that $V-E+R=2$ is true at the start, in the case of a graph consisting of one vertex and no edges. Furthermore, it remains true when one adds one new vertex connected by one new edge, since the new vertex and new edge cancel out.  Also, it remains true when one carves out a new region from part of an old region with the addition of a single new edge, since in this case there is one new edge and one new region, and these also balance each other. Since any connected planar graph can be built up in this way by gradually adding new vertices and edges, this argument shows $V-E+R=2$ for any connected planar graph. This is a proof by mathematical induction on the size of the graph.

Next, we moved on to consider some three-dimensional solids and their surfaces.  With various polyhedra, and the girls were able to verify further instances of $V-E+R=2$.

The girls then drew their own solids and calculated the Euler characteristic.  I taught them how to draw a cube and several other solids pictured here; when the shape is more than just a simple cube, this can be a challenge for a child, but some of the children made some lovely solids:

In the end, each child had a nice little booklet to take home. The images above are taken from one of the students in the class.

What a great day!

You can find a kit of the booklet here:

See also the account of my previous visit: Math for seven-year-olds: graph coloring and Eulerian paths.

# The rule-making game

Let me tell you about a new game that we’ve been playing in our family, the rule-making game.  It is a talking game, requiring no pieces or objects of any kind, and it can easily be played whilst walking or traveling.  My children and I recently played several rounds of it walking around London on a recent visit there.

The game has no rules, initially, nor even any definite procedure — it is different every time — but things usually become clear soon enough.  It usually makes a better game to cooperate on the first several turns to lay the groundwork.

Let me explain how to play simply by example:

Papa:  The first rule is that the players shall take turns making rules, and that every rule shall have a rule number, which is incremented on each turn.

Horatio:  The second rule is that the players must state their rules in the form, “The first rule is…” or “the second rule is…” and so on, and that players are not allowed to ask what is the current rule number, or they lose.

Hypatia:  The third rule is that the other players must say, “thank you” after another player makes a rule.

(… “thank you”…. “thank you”….)

Papa: The fourth rule is that the rules must not contradict each other, and no rule is allowed that abrogates an earlier rule.

(… “thank you”…. “thank you”….)

Horatio:  The fifth rule is that after making an odd-numbered rule, the player must stomp on the ground.

(STOMP… “thank you”…. “thank you”….)

Hypatia: The sixth rule is that no player may win immediately after their own rule.

(… “thank you”…. “thank you”….)

Papa:  The seventh rule is that right after a player stomps according to rule five, the other two players must hop.

(STOMP … “thank you”…. “thank you”….HOP….HOP…)

Horatio:  The eighth rule is that if a player loses, then the game continues without that person.

(… “thank you”…. “thank you”….)

Hypatia: The ninth rule is that after stating a rule, the other two players must state a different color.

(STOMP … “thank you”…. “thank you”….HOP…HOP… “blue”… “green”…)

Papa:  The tenth rule is that furthermore, those colors must never repeat, and they must be stated simultaneously, on the count of 1-2-3.

(… “thank you”…. “thank you”…. “1-2-3: neon green / violet”)

Horatio: The eleventh rule is that if there is only one player left, then that player wins.

(STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: red/orange”)

Hypatia:  The twelfth rule is that every player must jump up and down (…jump…) while stating their rule. (….jump jump jump…)

(… “thank you”…. “thank you”…. “1-2-3: pink/turquoise”)

Papa: (jump jump…) The thirteenth rule is that (…jump…) in the case of dispute (…jump…), the question of whether or not someone has violated or followed a rule shall be decided by majority vote (…jump…).

(STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: yellow/brown”)

Horatio: (jump….) The fourteenth rule is that (…jump…) before stating their rule, the players must state a country, and that whoever repeats a country loses (…jump…)

(… “thank you”…. “thank you”…. “1-2-3: black/gray”)

Hypatia:  (jump…)  Germany.  The fifteenth rule is that (…jump…) there can be at most twenty-five rules.

(STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: sky blue / peach”)

Papa:  (jump…)  United States.  The sixteenth rule is that (…jump…) if all current players lose at the same time after a rule, then the player previous to that rule-maker is declared the “honorary winner”.  (…jump…)

(… “thank you”…. “thank you”…. “1-2-3: white / white”)

Oh no! Since both Horatio and Hypatia said “white”, they both lose.  And then Papa also loses in light of rule six. So we’ve all lost!  But then, in light of rule sixteen, Hypatia is declared the honorary winner! Hooray for Hypatia!

I hope you all get the idea.  Please enjoy!  And report your crazy or interesting rules in the comments below.

# Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits

As a guest today in my daughter’s second-grade classroom, full of math-enthusiastic seven-and-eight-year-old girls, I led a mathematical investigation of graph coloring, chromatic numbers, map coloring and Eulerian paths and circuits. I brought in a pile of sample graphs I had prepared, and all the girls made up their own graphs and maps to challenge each other. By the end each child had compiled a mathematical “coloring book” containing the results of their explorations.  Let me tell you a little about what we did.

We began with vertex coloring, where one colors the vertices of a graph in such a way that adjacent vertices get different colors. We started with some easy examples, and then moved on to more complicated graphs, which they attacked.

The aim is to use the fewest number of colors, and the chromatic number of a graph is the smallest number of colors that suffice for a coloring.  The girls colored the graphs, and indicated the number of colors they used, and we talked as a group in several instances about why one needed to use that many colors.

Next, the girls paired off, each making a challenge graph for her partner, who colored it, and vice versa.

Map coloring, where one colors the countries on a map in such a way that adjacent countries get different colors, is of course closely related to graph coloring.

The girls made their own maps to challenge each other, and then undertook to color those maps. We discussed the remarkable fact that four colors suffice to color any map.

Next, we considered Eulerian paths and circuits, where one traces through all the edges of a graph without lifting one’s pencil and without retracing any edge more than once. We started off with some easy examples, but then considered more difficult cases.

An Eulerian circuit starts and ends at the same vertex, but an Eulerian path can start and end at different vertices.

We discussed the fact that some graphs have no Eulerian path or circuit.  If there is a circuit, then every time you enter a vertex, you leave it on a fresh edge; and so there must be an even number of edges at each vertex.  With an Eulerian path, the starting and ending vertices (if distinct) will have odd degree, while all the other vertices will have even degree.

It is a remarkable fact that amongst connected finite graphs, those necessary conditions are also sufficient.  One can prove this by building up an Eulerian path or circuit (starting and ending at the two odd-degree nodes, if there are such);  every time one enters a new vertex, there will be an edge to leave on, and so one will not get stuck.  If some edges are missed, simply insert suitable detours to pick them up, and again it will all match up into a single path or circuit as desired.  (But we didn’t dwell much on this proof in the second-grade class.)

Meanwhile, this was an excellent opportunity to talk about The Seven Bridges of Königsberg.  Is it possible to tour the city, while crossing each bridge exactly once?

The final result: a booklet of fun graph problems!

The high point of the day occurred in the midst of our graph-coloring activity when one little girl came up to me and said, “I want to be a mathematician!”  What a delight!

Andrej Bauer has helped me to make available a kit of my original uncolored pages (see also post at Google+), if anyone should want to use them to make their own booklets.  Just print them out, copy double-sided (with correct orientation), and fold the pages to assemble into a booklet; a few staples can serve as a binding.

See also my followup question on MathOverflow, for the grown-ups, concerning the computational difficulty of producing hard-to-color maps and graphs.

Finally, check out my new book:

# Doubled, squared, cubed: a math game for kids or anyone

## The number that must not be named

Doubled, squared, cubed is a great math game to play with kids or anyone interested in math.  It is a talking game, requiring no pieces or physical objects, played by a group of two or more people at almost any level of mathematical difficulty, while sitting, walking, boating or whatever.  We play it in our family (two kids, ages 7 and 11) when we are sitting around a table or when walking somewhere or when traveling by train.  I fondly recall playing the game with my brothers and sisters in my own childhood.

The game proceeds by first agreeing on an allowed number range.  For youngsters, perhaps one wants to allow the integers from 0 to 100, inclusive, but one will want to have negative numbers soon enough, and of course much more sophisticated play is possible. Eventually, one lessens or even abandons the restriction altogether. The first player offers a number, and each subsequent player in turn offers a mathematical operation, which is to be applied to the current number, which must not be mentioned explicitly.  The resulting number must be in the allowed number range.

The goal of the game is successfully to keep track of the number as it changes, and to offer an operation that makes sense with that number, while staying within the range of allowed numbers.  The point is to have some style, to offer an operation that proves that you know what the number is, without stating the number explicitly.  Perhaps your operation makes the new number a nice round number, or perhaps your operation can seldom be legally applied, and so applying it indicates that you know it is allowed to do so.  You must offer only operations that you yourself can compute, and which do not rely on hidden information (for example, “times the number of grapes I ate at breakfast” is not really permissible).

A losing move is one that doesn’t make sense or that results in a number outside the allowed range. In this case, the game can continue without that person, and the last person left wins.  It is not allowed to offer an operation that can always be applied, such as “times zero” or “minus itself“, or which can always be applied immediately after the previous operation, such as saying “times two” right after someone said, “cut in half”.  But in truth, the main point is to have some fun, rather than to win. Part of the game is surely simply to talk about new mathematical operations, and we usually take time out to discuss or explain any mathematical issue that may come up.  So this is an enjoyable way for the kids to encounter new mathematical ideas.

Let me simply illustrate a typical progression of the game, as it might be played in my family:

Hypatia: one

Barbara: doubled

Horatio: squared

Joel: cubed

Hypatia: plus 36

Barbara: square root

Horatio: divided by 5

Joel: times 50

Hypatia: minus 100

Barbara: times 6 billion

Horatio: plus 99

Joel: divided by 11

Hypatia: plus 1

Barbara: to the power of two

Horatio: minus 99

Joel: times itself 6 billion times

Hypatia: minus one

Barbara: divided by ten thousand

Horatio: plus 50

Joel: plus half of itself

Hypatia: plus 25

Barbara: minus 99

Horatio: cube root

Joel: next prime number above

Hypatia: ten’s complement

Barbara: second square number above

Horatio: reverse the digits

Joel: plus 3 more than six squared

Hypatia: minus 100

and so on!

As the kids get older, we gradually incorporate more sophisticated elements into the game, and take a little time out to explain to young Hypatia, for example, what it means to cube a number, to take a number to the power two, or what a prime number is.  I remember playing the game with my math-savvy siblings when I was a kid, and the running number was sometimes something like $\sqrt{29}$ or $2+3i$, and a correspondingly full range of numbers and operations. It is fine to let the youngest drop out after a while, and continue with the older kids with more sophisticated operations; the youngsters will rejoin in the next round.  In my childhood, we had a “challenge” rule, used when someone suspects that someone else doesn’t know the number: when challenged, the person should say the number; if incorrect, they are out, and otherwise the challenger is out.

Last weekend, I played the game with Horatio and Hypatia as we walked through Central Park to the Natural History Museum, and they conspired in whispering tones to mess me up, until finally I lost track of the number and they won…

# More math for six-year-olds: Win at Nim!

The latest installment of math for six-year-olds

Win at Nim!
Fold up the bottom flap to prevent parents from learning the super-secret strategy.

This morning once again I went into my daughter’s first-grade classroom, full of inquisitive six-and-seven-year-old girls, and made a mathematical presentation on the game of Nim.

Win at Nim!

The game of Nim, I explained, begins with one player setting up a number of stacks of blocks,while the opponent chooses whether to go first or second.  Taking turns, each player removes one or more blocks from a stack of their choosing. (It is fine to take a whole stack on your turn.) The player who takes the last block wins.

We demonstrated the game by playing a number of exhibition rounds, and then the girls divided into pairs to play each other and also me.  They were surprised that I was able to win against them every single time.  In explanation, I told them that this was because in the game of Nim, there is a super-secret mathematical strategy!  Did they want to learn?  Yes!  I took as my goal that they would all learn the Nim strategy, so that they could go home and confound their parents by beating them again and again at the game.

Since this was a first-grade class, we concentrated at first on games with stacks of heights 1, 2 and 3 only, a special case of the game which can still challenge adults, but for which six-year-olds can easily learn the winning strategy.

Two balanced stacks

After gaining some familiarity with the game by playing several rounds amongst each other, we gathered again for the secret strategy session. We began by thinking about the case of a game of Nim with only two stacks. They had noticed that sometimes when I played them, I had made copying moves; and indeed I had purposely said, “I copy you,” each time this had occurred.  The copying idea is surely appealing when there are only two stacks.  After some discussion, the girls realized that with just two stacks, if one played so as to equalize them, then one would always be able to copy the opponent’s move.  In particular, this copying strategy would ensure that one had a move to make whenever the opponent did, and so one would win the game.

A balanced position

In short order, the girls also realized that if one had any number of pairs of such balanced stacks—so that every stack had a partner—then the whole position was also winning (for one to give to the other player), since one could copy a move on any stack by making the corresponding move on the partner stack.  Thus, we deduced that if we could match up stacks of equal height in pairs, then we had a winning strategy, the strategy to copy any move on a partner stack.

In particular, this balancing idea provides a complete winning strategy in the case of Nim games for which all stacks have height one or two.  One should play so as to give a balanced position to one’s opponent, namely, a position with an even number of stacks of height one and an even number of stacks of height two.  Any unbalanced position can always be balanced in this way, and any move on a balanced position will unbalance it.

1+2+3 counts as balanced

To handle positions with stacks of height three, the super-secret trick is that one can balance a stack of height three either with another stack of height three, of course, but also with two stacks:  one of height one and one of height two.   Thus, one should regard a stack of height three as consisting of two sub-stacks, one of height one and one of height two, for the purposes of balancing. Thus, the Nim position 1+2+3 counts as balanced, since the 3 counts as 2+1, which balances the other stacks.  The 1+2+3 position has two stacks of height two and two of height one, when one regards the stack of height three as having a substack of height two and a substack of height one.

In this way, one arrives at a complete winning strategy for Nim positions involving stacks of height at most three, and furthermore, this is a strategy that can be mastered by first-graders. The strategy is to strive to balance the position.  If you always give your opponent a balanced position, then  you will win!  Faced with an unbalanced position, you can always find a balancing move, and any move on an balanced position will unbalance it.  If the game is just starting, and you are deciding whether to go first or second, you should determine whether it is balanced yet or not.  If it unbalanced, then you should go first and make the balancing move; if it is already balanced, then you should go second and adopt the copying strategy, in which you re-balance the position with each move.

More advanced players will want to consider Nim positions with taller stacks than three, and we talked about this a little in the classroom.  Some of the girls realized that the copying strategy and the idea of balanced positions still worked with taller stacks.  One can balanced stacks of height four against other stacks of height four, and so one, but the trick for these taller stacks is that one may balance 5 with 4+1; balance 6 with 4+2; and 7 with 4+2+1. Mathematicians will recognize here the powers of two.

To teach the strategy to children, it is a great opportunity to talk about the powers of two. Any child knows how to count 1, 2, 3, 4 and so on, and most can count by twos 2, 4, 6, 8, 10, …; by fives 5, 10, 15, 20, …; by tens, by threes; by sevens; and so on.  , The powers of two are the numbers 1, 2, 4, 8, 16, 32, 64, 128, and so on, doubling each time.  Climbing this exponential growth, children are often amazed at how quickly one reaches very large numbers:

One plus one is two;

two plus two is four;

four plus four is eight;

eight plus eight is sixteen;

sixteen plus sixteen is thirty-two;

thirty-two plus thirty-two is sixty-four;

sixty-four plus sixty-four is one hundred twenty-eight.

For Nim, we don’t in practice need such big powers of two, since one doesn’t usually encounter stacks of height eight or larger, and usually just 1s, 2s and 4s suffice. The relevant fact for us here is that every natural number is uniquely expressible as a sum of distinct powers of two, which of course is just another way of talking about binary representation of a number in base two.  We regard a Nim stack as consisting of its power-of-two substacks.  Thus, a stack of height 3 counts as 2+1; a stack of height 5 counts as 4+1; a stack of height 6 counts as 4+2; and a stack of height 7 counts as 4+2+1.

Ultimately, the winning general strategy for Nim is always to play so as to balance the position, where one regards every stack as being composed of its power-of-two sub-stacks, and a position counts as balanced when these stacks and sub-stacks can be matched up in pairs. This is a winning strategy, since every unbalanced position can be balanced, and any move on a balanced position will unbalance it.  To balance an unbalanced stack, play on any stack containing the largest size unbalanced power of two substack, and reduce it so as to balance the parity of all the stacks.  If one thinks about it, at bottom what we are doing is ensuring that if we represent the stack heights in their binary representation, then we should play so as to ensure that the position has a even number of one digits in each place.

# Math for six-year-olds

Today I went into my daughter’s first-grade classroom, full of six-year-old girls, and gave a presentation about Möbius bands.

We cut strips of paper and at first curled them into simple bands, cylinders, which we proved had two sides by coloring them one color on the outside and another color on the inside.  Next, we cut strips and curled them around, but added a twist, to make a true Möbius band.

A Möbius band

These, of course, have only one side, a fact that the children proved by coloring it one color all the way around. And we observed that a Möbius band has only one edge.

A Möbius-like band, with two twists

We explored what happens with two twists, or more twists, and also what happens when you cut a Möbius band down the center, all the way around.

Möbius band cut down the center

It is very interesting to cut a Möbius band on a line that is one-third of the way in from an edge, all the way around. What happens? Make your prediction before unraveling the pieces–how many pieces will there be? Will they be all the same size? How many twists will they have?

Overall, the whole presentation was a lot of fun. The girls were extremely curious about everything, and experimented with additional twists and additional ways of cutting.  It seemed to be just the right amount of mathematical thinking, cutting and coloring for a first-grade class.  To be sure, without prompting the girls made various Möbius earrings, headbands and bracelets, which I had to admit were fairly cool. One girl asked, “is this really mathematics?”

It seems I may be back in the first-grade classroom this spring, and I have in mind to teach them all how to beat their parents at Nim.