A Case of Accidental Symmetry

The other day I was thinking about putting dominoes onto a 4-by-4 grid without any of the dominoes contacting each others’ sides. I wanted to know how many dominoes you could fit onto the 4-by-4 grid in this way, and what the different configurations looked like. I was pretty sure that the answer to the first question was that four dominoes could be fit onto the grid. I was less sure that I had found all of the configurations allowed. (I had three configurations.)

So, I started from square one: I found all of the ways (up to symmetry) of putting one domino on the grid (there are four). Then combining those I found all of the ways of putting two dominoes on (there are 20). Then by taking all of my configurations of two dominoes and adding one I found all of the ways of putting three dominoes on (there are 20). Finally I used my 3-domino configurations and found all of the 4-domino configurations by adding one to the ones that allowed it. I discovered that I had missed a 4-domino configuration! So there are four 4-domino configurations. And since I couldn’t legally add a domino to any of those, I knew there were no 5-domino configurations. Cool.

But wait…4, 20, 20, 4. There’s symmetry there! Could it be that this is a general thing? Is there a way to transform the four 1-domino configurations into the four 4-domino configurations? Likewise, did the same (or a similar) transformation change the 20 2-domino configurations into the 20 3-domino configurations? It might be something like the binomial coefficients: the number of ways to choose two people out of a group of five is the same as the number of ways to choose three people out of a group of five.

Then, my heart sank…I thought of this fact: there is exactly one configuration with no dominoes (just an empty grid), but there are zero 5-domino configurations. The symmetry is broken. There apparently is no such transformation.

Still, the 4, 20, 20, 4 pattern is fascinating (even if the pattern is really 1, 4, 20, 20, 4). I shared this with Jason Lee, a mathematical friend. Jason thought (as I had originally) that there was some transformation that we were missing. He suggested we look at larger grids to see if we see similar patterns. I bet him a bottle of rootbeer that we wouldn’t. He accepted the bet, and proceeded to code up an algorithm for enumerating domino configurations with grid-size as a parameter. The algorithm didn’t find any such nice symmetries for larger grids. I wish I could be more specific about the details, but I don’t have them in front of me right now. In the next couple of days I’ll talk to Jason about sharing his Python code here on my blog, along with specifics of numbers of configurations for larger grids. In any case, I got my rootbeer!

Above I’ve posted a drawing of the 4, 20, 20, 4 configurations mentioned (click on it to see it enlarged). Do you see a reason for the symmetry? Is there some transformation we’re missing? In any case, I think it makes for a nice picture.

By the way, the original impetus for thinking about this was the December 2012 IBM Ponder This puzzle. There we are asked to place numbers in a 6-by-6 grid. The highest numbers that we can place are fives, and the rules given there imply that any fives come as dominoes of four-five pairs lying in the central 4-by-4 grid with our no-contact constraint.

Radix sort with index cards

I showed my kids the radix sort.

Benzene Flexagons

My wife is taking an organic chemistry class. I don’t know much about organic chemsitry, but I did learn from her that benzene rings are hexagons. So I got thinking, what about benzene hexaflexagons? These are the result of those thoughts.

I’ve included my templates as PDFs:

benzene_flexagon_1
benzene_flexagon_2
benzene_flexagon_3
benzene_flexagon_4
benzene_flexagon_5
benzene_flexagon_6

These are based on the templates that can be found at the excellent website The Flexagon Portal. They are pretty easy to fold, simply cut them out. pre-crease along all lines. then fold along the long center line and glue. This leaves two triangles that are not double-thiknesses of paper. Finally fold into a hexagon shape, making sure the benzene ring comes together appropriately and glue those final two single-thickness triangles together on top of each other.

See the instructions on The Flexagon Portal templates, or Vi Hart’s videos if you are still confused.

Kid Snippets: Math Class

If you’re a math teacher, is this ever what class feels like?

Counting

My five-year-old has been able to rattle off the numbers in order into the teens for a while, but when you ask her to count a set of objects, she can only get up to three consistently. “One, two, three–um–five?”

I have an idea of what might be going on in her head. It is pretty clear that she knows that four comes after three. I suspect that she has also figured out that when counting objects you are announcing at each step how many you have pointed to so far. When she points to the first object she knows that she has pointed to one object and announces “one.” Upon pointing to the second object she knows that she has pointed to two objects and announces “two.” When she points to the third things go similarly, but when she gets to the fourth she runs into trouble, because she doesn’t have any good idea how many have been pointed to.

I hear you saying “Whoa, if she knows that four comes after three then of course she knows that after pointing to one more than three things she has pointed to four things.” Not so, because she hasn’t learned that yet. Sure, you know what counting is all about, but kids don’t until they’ve been taught. What my daughter is doing when pointing to the first three objects is subitizing the number of objects pointed to so far. Subitizing is the act of being aware immediately of how many objects are in a collection without counting them. We humans can easily subitize collections of one, two, or three objects.

Up to this point my suspicion is merely that: a suspicion. My hypothesis has to be tested. We need to isolate the pieces of counting. The elements of counting are: 1) reciting the names of the numbers in order; 2) pointing to objects one-by-one; 3) doing 1 and 2 simultaneously; and 4) coordinating actions 1 and 2, saying exactly one number for each object pointed to. We isolate these elements in the case of my daughter by asking ourselves a series of questions:

First, can she recite the numbers aloud, in order consistently? Yes. She has no problem with this up to at least ten.

Second, can she point to objects one-by-one, in sequence? Yes. No problems there.

Third, can she point to objects one-by-one, in sequence while reciting the numbers aloud? Initially we aren’t sure, and we decide that we need to distance this skill from counting itself, so we ask ourselves:

a. Can she recite aloud a sequence of words other than the counting numbers? Sure, she knows the alphabet, as well as many songs.

b. Can she point to objects one-by-one, in sequence while reciting aloud a predefined sequence of words in order? We don’t know initially, but my wife tries it with her and she is successful (for instance, with the alphabet).

Fourth, can she coordinate the two actions above? That is, as she points to objects in sequence and recites words, can she match them up, pointing to exactly one object for each word she says? Again, we aren’t sure initially, but my wife tries it with her and she is in fact able to do it.

This last one is the complete skill of counting. Once she can do that she can count, right? So what’s tripping her up? Well, counting is two separate things: it’s a process as just described, and it’s a way to ascertain the number of objects in a collection. These are distinct facets of counting, but they are intimately connected. You do the process and the last number that you say is the number of objects in the collection. These two facets of counting are usually learned by children separately. It is my understanding that most children first learn the process of counting and only later learn that this process gives you information about how many things are in a collection. A young child who has “learned to count” may count the cookies on a plate “one, two three, four, five, six, seven,” but then when asked “how many are there?” reply with “I don’t know.”

I think that my five-year-old learned things opposite the usual order. I’m pretty sure that she has figured out that counting is all about determining the size of a collection, but initially she is unclear on how the process works. Only by divorcing the counting process from numbers were we able to make any progress. In the last several months she has progressed well, and is on her way to being a proficient counter.

See also: Wikipedia article on counting

Latin Squares, Squared Squares, and Legoed Squares

I introduced my kids to Latin Squares the other day. If you know Sudoku then you have seen examples of Latin squares. The idea is to fill in a grid of squares with colors or numbers or some other symbols, such that each symbol appears exactly once in each row and each column. (see also the Wikipedia Latin square entry). I handed them graph paper and let them loose. This is what my eight-year-old produced:
Note that she produced some Latin squares, but also explored other ideas.

I wasn’t sure initially how long my kids would be content to explore Latin squares, so I also planned to tell them about squared squares. A squared square is just a square made up of smaller squares (this is easy to accomplish). A perfect squared square is much more difficult, consisting of squares each of different sizes. For a long time it was thought that perfect squared squares didn’t exist, but they do! Here is the smallest (in some sense) one:
We got excited about it and decided to make one for our wall:

Next, the ten-year-old wanted to produce some squared squares of his own, but found the perfect ones difficult (they were thought to be completely non-existent for a long time after all). He settled for producing imperfect ones. After making an imperfect squared square on graph paper, he decided to reproduce it with Legos. Here is the result: This led us to considered perfect Legoed squares. That is to say, squares made up of some number of Lego pieces, each piece having a unique size. Here is one of our first examples: It’s a 3×3 made up of a 1×1, a 1×2, and a 2×3. Here’s another, somewhat larger: We found a bunch more (maybe ten or so total). I’m not sure that we got all of them. How many can you find?

Look for up-coming posts on: 1) further progress in building our marble computer, and 2) teaching my five-year-old to count (which required some deep thought about just what counting is).

Dots and Boxes

Tonight we had a friend’s kids over as well as ours, so our place was kind of a mad house. A colleague had recently shown me the book The Dots and Boxes Game by Elwyn Berlekamp I had read about the first chapter and was intrigued, so I wanted to introduce the game to my kids. as the night was about to descend into total chaos I called everyone to the table and gave them the run-down on how to play the dots and boxes game: start with a grid of dots. On your turn connect any two adjacent dots. If you complete one or more little squares (a box) initial the box and go again. The three-year-olds basically scribbled. The five- through eight-year-olds played a few games and moved on to something else, but my ten-year-old eventually decided to challenge me. I played against him enough times for him to see me use, and then learn to use himself the double-cross tactic (which is explained in the dots and boxes Wikipedia article).

Anyway, we’ll probably continue to have fun with dots and boxes. Something else that I wanted to set them loose on is the following game that I first heard of from Singing Banana:

But we didn’t get around to it tonight…

The Math Games–One: Block Towers

We had some time today, so I suggested a little competition: try to build the tallest tower with our wooden blocks. My nine-year-old and I were the only ones to compete, and the nine-year-old got bored pretty quickly and essentially gave up. Below is his tower.

The rules that I laid out are as follows:
1) Build a tower by stacking the wooden blocks as you wish.
2) The tower is measured from base to tip. Your final score is calculated by taking the height of your tower in inches and subtracting an inch for each year of your age.
My son’s tower was 29.5 inches, so his calculated score was 19.5
My tower was 79.25 inches, so my calculated score was *****. Let’s just say that I won by a wide margin.

Of course the crux of designing these towers is managing your block resources. You want the base to be wide and sturdy enough to give good support to the tower, but you don’t want to waste too many blocks on any single layer.

Here are some more shots of my tower:

Math Camp II: Eternity

This is the second installment describing my experiences teaching at a math camp for high-schoolers. More about the computers class later, right now I just wanted to mention an evening talk that I gave to the entire camp. It was on the Eternity Puzzle and its solution by a pair of mathematicians. Here is a link to a good article describing the weaknesses accidentally built into the puzzle by the designer (because he didn’t do the math!) and how two Cambridge mathematicians were able to successfully attack it (because they did do the math!).

Take home message is: Do the math!

I also have in mind a slightly more philosophical message. Though, we all know that math is fun and beautiful–We all know that, right?–it is also useful. For instance, given some problem in the real world, it is often productive to model it mathematically. The hope is that, even though the model is not perfect, working with it will give insight into the real problem. What may come as a surprise is that this also works for problems in the mathematical world. That is, given some mathematical problem, it may be productive to model it with a simpler mathematical problem. The simpler problem will not model the more complicated one perfectly. However, working with the simpler model may give useful insights to the original problem. This sort of paradigm plays out for the solution of the Eternity Puzzle. I will forbear giving further details and instead recommend that you read the article linked previously, as well as this more detailed article, and if those leave you wanting more a few additional details can be found at this third article.

One final thing: it turns out that I also gave this talk in Portuguese to some camp students from Mozambique. Do I speak Portuguese? Well, I did 13 years ago. This was my first attempt at giving a technical talk in Portuguese. It was exhausting, but an experience I’m glad I had. A reminder that I really should keep current with my Portuguese skills…

Math Camp I: Recursion and such

The past two years I’ve taught at a summer math camp for high school students. In 2010 I assisted with a class on chaos and fractals. This year I assisted with a computers class. I’m planning to do a couple of posts about the class. This is the first of those posts.

The computer class that I helped teach focused on hardware, but also included some software topics. My main role was teaching programming. I should point out that I am not really a programmer. I’m a mathematician who uses some programming in his work. I’ve never had a programming class. Nevertheless, I hope that I was able to get some of the basics across to the students.

I first introduced programming to the students by describing a simple language for manipulating a cube, the goal being to get the cube in a prescribed orientation. More on that in a later post.

We did our programming in two languages: Python (which you can try in your browser at: Try Python) and Alice. Both are freely available. In Python we did some simple procedural programming (I had them code up a function that computes the factorial of a number and another that runs the Collatz algorithm). One of the students was able to produce a factorial algorithm very quickly. Here is his python code:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

It surprised me that he used recursion, though I think he has had some programming experience in the past. Most of the other students had had no prior programming experience and were having a hard time producing a factorial function. This also surprised me. This was my first time teaching programming, so I had little intuition for where the students might get hung up.

Alice is a drag-and-drop object-oriented language for manipulating characters in a 3-D virtual world. We mostly let the students explore Alice on their own as their interests dictated. One student wrote a very simple first-person shooter game.

In any case it was hard to get any of the kids very interested in programming. If I go back next year and assist with this same class, then I think I would like to have some compelling problems or mini-projects that would grab the kids attention and require them to do some programming. Suggestions anyone?