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.

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…

How to Eat an Equilateral Cheeseburger

My friend Sean worked out an elegant and practical solution to the Cheeseburger problem of my previous post.  I will try to summarize it here.

There are fifteen toppings.  To make things simpler we’ll represent them with the numbers one through fifteen.

1 = Mayo
2 = Relish
3 = Onions
4 = Lettuce
5 = Pickles
6 =Tomatoes
7 = Grilled Onions
8 = Grilled Mushrooms
9 = Ketchup
10 = Mustard
11 = Jalapeno Peppers
12 = Green Peppers
13 = A-1 Sauce
14 = Bar-B-Q Sauce
15 = Hot Sauce

Arrange these numbers around a circle at equal intervals, like the hours of a clock with fifteen rather than twelve hours.  Each cheeseburger can be represented on this circle as three points.  Think of these three points as the vertices (corners) of a triangle.  As has been shown in the comments of the previous post, there are 455 cheeseburgers total.  So the totality of cheeseburgers are represented by 455 triangles inscribed in the circle, which is a tangled, nasty mess (but not as big a mess as all 455 cheeseburgers sitting on your kitchen table).

Let’s get a handle on the mess.  We need some notation to make it easier to talk about these triangles.  If a triangle has vertices at points marked x, y and z, we’ll denote it by (x,y,z).  Some of the triangles will have the same shape as each other.  Others will be differently shaped.  For instance, (1,2,3) has the same shape as (2,3,4), but (1,2,4) has a different shape than (1,2,3).

In fact there are fifteen triangles with the same shape as (1,2,3) (including (1,2,3) itself).  They are: (1,2,3), (2,3,4), (3,4,5), (4,5,6), (5,6,7), (6,7,8), (7,8,9), (8,9,10), (9,10,11), (10,11,12), (11,12,13), (12,13,14), (13,14,15), (1,14,15) and (1,2,15).  Each of these triangles can be obtained from (1,2,3) by rotating it around the circle.  These fifteen triangles together form an equivalence class.

Likewise there are fifteen triangles with the same shape as (1,2,4).  Said another way (1,2,4) has fifteen triangles in its equivalence class (but we need to be careful here to emphasize that we are considering (1,2,4) and say (1,3,4) to have different shapes: they are mirror images of each other, but not rotations of each other).

In all, the 455 triangles fall into 31 equivalence classes.  30 of these classes have fifteen triangles.  The final equivalence class consists of five triangles.  More on that in a moment.

The strategy is this:  Pick an equivalence class.  Rotate through all of the cheeseburgers in that class.  Next move on to another equivalence class.

Let’s list the equivalence classes by writing down a single triangle in each class.  OK, I’m not actually going to write all of them out, but I will do the next best thing.  You’ll see.

First we have twelve equivalence classes with triangles of the form (1,2,n), where n=3,4,5,…,14.  We don’t allow n=15 (i.e. (1,2,15) because that is the same class as (1,2,3).  That gives us 180 cheeseburgers.

Then there are nine classes of the form (1,3,n), where n=5,6,7,…,13. (n=15 would give the same class as (1,2,4) and n=14 the same class as (1,3,5)).  That’s another 135 cheeseburgers.

Next we get six classes of the form (1,4,n), with n=7,8,9,…,12.  Another 90 cheeseburgers.

Similarly there are three classes of the form (1,5,n), with n=9,10,11.  45 more cheeseburgers.

Finally, we have our one strange class with only five cheeseburgers in it.  This class is represented by (1,6,11).   Let’s list all of the triangles in this class: (1,6,11), (2,7,12), (3,8,13), (4,9,14), (5,10,15).  These are the five equilateral triangles in the set.  Just for fun let’s list the five cheeseburgers that these triangles represent.

The equilateral cheeseburgers are:

Mayo, Tomatoes, Jalapeno Peppers

Relish, Grilled Onions, Green Peppers

Onions, Grilled Mushrooms, A-1 Sauce

Lettuce, Ketchup, Bar-B-Q Sauce

Pickles, Mustard, Hot Sauce

So go into a burger joint.  Ask for an equilateral cheeseburger.  See what kind of look you get.  Then just tell them you want mayo, tomatoes and jalapeno peppers on it.

OK, seriously, back to the math for a minute.  Sean also realised that you can rotate through the classes such that no two burgers in a row have any of the same toppings.  Great!  That’s what I was asking for in the first place.  Let’s use our first equivalence class as an example.  We start with the triangle (1,2,3).  Now we can rotate one slot by adding one to each number in this triple to get (2,3,4).  But that’s not what we want: we would have two burgers in a row where only one topping changed.  So instead let’s rotate three slots so that none of the toppings are the same twice in a row.  We get (1,2,3) then (4,5,6).  Keep going to get: (7,8,9), (10,11,12), (13,14,15).  Now when we do the next addition: (13+3,14+3,15+3) we have to be careful to do clock arithmetic on a 15-hour clock.  That is, counting up one from 15 gives one, rather than 16 (we mathematicians call this modular arithmetic).  So (13+3,14+3,15+3)=(1,2,3).  That’s a problem because we’ve already visited the triangle (1,2,3), but there are still ten triangles that we haven’t visited in this class.  Our problem was moving three slots at a time.  15 is divisible by 3.  In fact, what we should do is pick a number that is relatively prime to 15, which means a number that is not divisible by three or five (the prime factors of 15).  Four will work.  So start with (1,2,3).  Add four to each slot: (5,6,7).  Add four again: (9,10,11).  And again: (13,14,15).  Again: (2,3,4).  Continue in this manner.  Here is the list we get for this whole equivalence class:

(1,2,3)

(5,6,7)

(9,10,11)

(13,14,15)

(2,3,4)

(6,7,8)

(10,11,12)

(14,15,1)

(3,4,5)

(7,8,9)

(11,12,13)

(15,1,2)

(4,5,6)

(8,9,10)

(12,13,14)

and we’re done with this class.  We will now move on to the next class starting with (1,2,4).  For this class rotating four slots will also work:

(1,2,4)

(5,6,8)

(9,10,12)

(13,14,1)

(2,3,5)

(6,7,9)

(10,11,13)

(14,15,2)

(3,4,6)

(7,8,10)

(11,12,14)

(15,1,3)

(4,5,7)

(8,9,11)

(12,13,15)

Done with that class.  The next one in line starts with (1,2,5).  Now if we rotate by four we will get overlap between successive triangles.  Instead, we could choose to rotate by two:

(1,2,5)

(3,4,7)

(5,6,9)

(7,8,11)

(9,10,13)

(11,12,15)

(13,14,2)

(15,1,4)

(2,3,6)

(4,5,8)

(6,7,10)

(8,9,12)

(10,11,14)

(12,13,1)

(14,15,3)

And we’re done with that class.  And so the process continues through all 455 cheeseburgers.  So the amount we rotate depends on the equivalence class we’re working in, but we can always pick a rotation that is both relatively prime to 15 and doesn’t result in any overlap between consecutive triangles.  In fact, it turns out that we can always choose our rotations from the set {1,2,4}.

Notice that my first 15 cheeseburgers will be isoceles.  Then I will be eating scalene burgers for quite some time.  Not until the very end do I get to the equilateral cheeseburgers.  I have decided that I am going to try to do two per month.  That way it will take me just under 19 years to finish.  Read Mayo, Relish Onions: A Cheeseburger Review for an account of the first trial of this experiment.  Bon Appetit!

Math with Balloons

In demonstrating what a mathematical knot is, balloons are the best medium that I’ve found.  They have enough stiffness to keep the knot from collapsing so that you can’t see its structure (a string or rope would either be floppy and hard to work with, or you would have to pull the knot tight, which would make it hard to see it’s structure).  They have enough give to allow knots to be tied in them.  They are very visisble and the ends can be twisted together to complete the loop.

Here I am with not a knot, but a link: the Borromean rings.  It has beautiful symetries that have been recognized for centuries and is important to low dimensional topology (in fact, an early incarnation of my dissertation featured the Borromean rings).

Knot Tying Schema

I’ve noticed that whenever my two-year-old wants to tie a knot, she takes the two strands that she’s interested in and repeatedly twists them around each other.  Of course this doesn’t produce any kind of knot at all (or I should say it only produces the unknot).  But this twisting appears to be the only basic move that she knows (and she learned it herself) for producing knots.

It made me wonder what the basic moves are that we use to tie knots.  Every knot theorist knows that there are three basic moves for transforming one picture of a mathematical knot into another (possibly quite different looking) picture of the same knot.  These moves are called the Reidemeister moves.  Any two pictures of the same knot can be made to look like each other using just these moves (and “plane isotopies”).  Similarly it seems to me that mathematically you really only need two moves to tie any knot, or what I mean to say is to go from a picture of a straight string to a picture of any knot.  Here is an illustration of those two moves:

Of course after doing several of these moves, you will want to glue the two ends of the string together if you wnat to get a picture of a mathematical knot.

When people tie knots, it does seem like there is some finite set of moves they use, but the catalogue of moves seems to be bigger than these two moves I illustrated above.  For instance there are moves like “wrap one end around a loop” or “put one end through a hole” or “follow one strand through a whole series of moves.”  Of course each of these can be broken up into a sequence of the two basic moves, but it is not always useful to break things down into the simplest possible moves in practice.  It makes me wonder what the catalogue of moves is that people use.

Baseball

Happy Ruth-Aaron days!

Sequences and Creative Math for Kindergartners

I visited my kids’ classes for career day in May. I have a son in Kindergarten and a daughter in pre-K. I also visited two other kindergarten classes. I told the kids that I am a research mathematician: mathematician means I do math. Research means I do math that nobody has ever seen before, math that I make up.

I mentioned that math is lots of things: It’s thinking about shapes and numbers and patterns, and other stuff. This day we were going to do numbers and patterns.

I showed them a board covered with three lines of (blank) sticky notes. Under each note was a number.The point is to try to guess which number is coming next.

We started with the blue line of numbers.

Once I had uncovered the 1 and 2 almost everyone expected the next number to be 3.

When I showed them that it was a 1, they caught on pretty quickly.

They had fun shouting out the 1-2-1-2-1-2 pattern as I frantically tried to keep up with them on the board.

Next, the pink ones.

I started by showing the 1-2-1 with a warning that I was being tricky. A 2 should come next, right? Wrong! But I didn’t tell them what it was yet. I put the sticky notes back on and explained that I was going to pull them off in a different order to see if it gave them a hint. (At this, some kids suggested I pull them off starting at the right instead of the left.)

I pulled off every other sticky: 1-skip a sticky-1-skip a sticky-1-skip… Okay, done with the ones. Next we have:

2-skip a sticky-2-skip a sticky-2-skip… (pulling off every other sticky that is left after the first pass). Okay, done with the twos. So the next one should be (the one that everyone thought should be a 2):

It’s a 3! And most of the students guessed that it was a 3!

And so it goes: 3-skip a sticky-3-skip a sticky-3 skip…

Next we have the fours: 4-skip a sticky (at this point we hit the end of the board, but if the board were longer…we would continue 4-skip a sticky-4-skip a sticky-4-skip…

Only one pink number left…

Everyone knows it’s a 5 by now! If we had a long enough board we would have 5-skip a sticky-5-skip a sticky-5-skip…

The pink numbers are:

1-2-1-3-1-2-1-4-1-2-1-3-1-2-1-5-1

Some interesting things (I think) about these pink numbers: Once you’ve done the ones and twos the row looks exactly like it would if you had pulled off the same patterns on the blue row! Nevertheless, most kids pick up on the fact that 3 should come next (well…I did give a big clue “done with the ones! . . . Done with the twos!”)

These pink numbers are called the ruler sequence, which comes up in the towers of Hanoi problem.

Now for the greens (the stickies look yellow in these pictures, but they are really green (yellowish-green)).

What do you think I will start with? Most kids had figured that I am into ones by now. So naturally, I start with a one again.

This row is really sneaky (but usually the kids understand it before their teachers! A testament to the freedom that young minds who haven’t had mathphobia drilled into them are capable of!), so I give a big hint. What do we have so far (on the green row)? One. How many ones? One one.

So that is what comes next. You start with a 1 then you say “look, it’s 1 one,” and that’s what you put next 1-1.

Now what do you have? 1-1-1. You have 3 ones. So next comes:

3-1.

Now you have 1-1-1-3-1. Four ones and one three. So next is:

4-1-1-3.

Now you have:

1-1-1-3-1-4-1-1-3. That is, six ones, two threes, and one four. So next will be:

6-1-2-3-1-4.

And now you have:

1-1-1-3-1-4-1-1-3-6-1-2-3-1-4. That is eight ones, one two, three threes, two fours and one six.

There is only room on the board to put 8-1. But if we had more room we would keep going. If we had paper going all the way around the school… I asked the kids if they thought we would ever get a 5. We haven’t so far! (At this someone always pointed out that we got a 5 on the pink line. A good observation! But we are just looking at the green line now.) What about 10? If we kept going would we get a 10? Would we ever get a 20? Or 100? Would we ever get a thousand or a million or a billion?

I’m pretty sure that you do get a 5 and a 10. I don’t know about 20, 100, 1,000, 1,000,000 or 1,000,000,000. I’m guessing that you do get them… Why? well, my reasoning is this: in some sense you have infinitely many chances to hit those numbers. Maybe at one point you will have 20 ones. If not, maybe you will get 20 twos. Of course maybe you will skip right over 20 twos. So maybe you will get 20 threes or 20 fours or 20 fives or…, you get the idea.

I told the kids that I didn’t know if you ever get 20 or 100 or 1,000. All I know is that you keep getting bigger and bigger numbers (can you see why?). I pointed out to the kids that this is a math question that I don’t know the answer to, and (as far as I know) neither does anybody else. This is math research, and it’s math research that they can do! They can figure out if we ever get a 5 or a 10. A million…probably they won’t figure that out until they learn some computer programming…

The kids were perfectly willing to accept that this is a math question that has an answer, but nobody knows that answer yet.

As for me, I’m conjecturing (conjecture=educated guess) that if you continue with the blue numbers, you will eventually hit any positive, whole number that you might care about. I already told you my reasons for making this conjecture. Can you prove it? Can you prove me wrong? If you’re a teacher, give the problem to your students. Maybe they’ll have an idea about it. Then let me know.

Finally, I wanted to let the kids make up their own number sequences. I handed out sheets of paper with five slots for numbers and five sticky notes. I told them that they could write any numbers they want in the blanks. They could be tricky, or they could be easy (like 1-1-1-1-1). Then, cover them up, and see if someone can guess the numbers.

Do they have to be able to articulate some reasoning for the patterns behind their numbers? No. But if they can, that’s great. There doesn’t have to be any reasoning at all. The point of this exercise was for the kids to do some free-form creative math. Just release your inhibitions (actually the kindergartners don’t have many inhibitions. The grown-ups on the other hand…) and write down some silly or crazy or boring or weird or hard-to-guess or happy, or sad pattern. The kids loved this part. They especially loved seeing if I could guess their numbers.

Let me know what you think about these sequences and this activity!

How to Remember Multiplication Tables

wordpress.com has a “stats” feature that allows you, among other things, to see what search terms people have used to find your blog. It turns out that most hits that I get from search engines are by people wanting to know how to memorize their multiplication tables (they find the post Multiplication Tables, which doesn’t actually give any advice on memorizing them). I’ve started to feel so guilty about this that I decided I should write a post giving tips on memorizing multiplication tables (or times tables) hoping that it would be helpful to some of those folks searching for help. Then maybe they will read some of the other posts and get hooked on math

So here goes:

We start with something that sounds totally unrelated (but stick with me): James A. Michener’s Novel Texas. In that book there is a character named Miss Barlow, who is a school teacher. Michener has her: “Standing before a massive map of Texas that showed all the counties in outline only, she said softly ‘Your Texas has two-hundred and fifty four counties.’” Miss Barlow goes on to challenge the students to be able to name, from memory, every county when pointed out on the map. One big obstacle to achieving this feat (besides the shear immensity of the number of counties) is that many of the counties in West Texas and the Panhandle are nearly-identical little rectangles. But never fear! This teacher has a method to cut this memorization down to size. First you select any five counties that you wish. The only criterion for the selection of your counties that must be met is that each must be in a different region of Texas. In other words, you can’t group them all together. You have to pick counties scattered around Texas. Once you have those five counties nailed down and committed to memory you “could build upon them the relationships required in Texas history,” and continue to learn the names of the surrounding counties, until you have all 254 memorized.

Now let’s look at the multiplication table and see what it is like. Here it is, the 0 – 12 multiplication table in all its glory:

The only thing that I’ve left off are the numbers! But don’t worry about those! We’ll get to them soon enough. (By the way, why do we ever ask kids to memorize the 0 – 12 multiplication table? We use a base ten system. Memorizing 0 – 9 should be perfectly sufficient). And here is Texas:

Almost eerie how similar they are isn’t it? Look at all of those identical little squares in the multiplication table and those counties stacked one on top of another in Texas. Let’s try to approach the multiplication table from Miss Barlow’s view point. Actually the multiplication table is much easier than the map of Texas. Texas has 254 counties, but our multiplication table has entries to remember.

Here’s how I remember them.

Also, let’s face the fact that there are some really easy ones: The zero-times-blank-row and the blank-times-zero-column are a piece of cake, so is the one-times-blank-row and blank-times-one-column, and let’s face the fact that the ten-times-blank-row and blank-times-ten-column are just as easy. So already we have knocked out a big chunk of the table:

Of course everyone knows that 3 times 7 is the same thing as 7 times 3. We can get rid of almost half of our squares:

Looking more like Texas all the time. Now 5′s are easy, at least if you are multiplying by an even number, just chop it in half and throw on a zero. There’s also a handy trick for 9′s. For instance 9 times 7 is 63. The 6 is one less than 7 and the 3 is 9-6. It works with all of the single digit numbers, for instance 9 times 3 is 27.

Multiplying a single digit number by 11 is also easy, just write it twice, for instance 8 times 11 is 88. Now maybe it’s not exactly easy, but I think that everybody should be able to memorize the double of every number from 2 to 12:

Once you know those, it is pretty easy to multiply 12 by any number less than 5. Just write the number and then its double:

and

We don’t have much left to memorize! Finally, I think that it is worth while to memorize all of the squares. Here are the ones that we haven’t dealt with so far:

But maybe you don’t want to do that much work. So how about you just memorize and . Then if you memorize one more fact: , and look at the table, you might notice something:

Every square left blank is directly adjacent to (above, below, to the right or the left) a filled in square. Now build upon these the relationships required in arithmetic: For instance, let’s say that you want to know , well you know , so . You want to know ? Well, you know , so . Voila! Multiplication is a snap. Of course it’s going to take a lot of practice, but good luck! I hope it helps.