Abby’s Puzzles

abbys_puzzles

My ten-year-old daughter asked me for help doing a mathematical STEM-fair project. We had a lot of funny doing the project together. Here is a brief description of what we did.

We decided on the following question: “How many decominoes can be filled in (tiled) with a pair of pentominoes in more than one way?”

There are 12 pentominoes. I had Abby figure out the number of pairs of pentominoes. She reasoned that since you have 12 choices for the first pentomino in a pair, and 11 choices for the second (but switching first and second you’ve counted each pair twice) there are 12×11/2 = 66 pairs. There are 4,655 decominoes. So we had 66 x 4,655 = 307,230 trials (trying each pair against each decomino). Abby wasn’t going to be able to do this by hand. Instead I taught her the Python she would need to program our computer to do it.

We couldn’t find an explicit list of all 4,655 decominoes anywhere, so the first order of business was to write a program to generate those. Actually, before that we had two prerequisites to understand. First I had to introduce her to the very basics of programming: what is a variable and how do they work? What are loops? How do they work? How about lists? Functions? There was some frustration on both our parts, but we got it hammered out. Second we had to decide how we would represent polyominoes in the computer and how we could manipulate them. I had already done some Python projects with polyominoes, and was representing polyominoes as lists of cartesian coordinates of each square. Abby understood the representation immediately, saying “oh! It’s like a coordinate grid!” I had Abby figure out (and write functions for) how to flip and rotate polyominoes.

Abby largely wrote the code to generate the decominoes herself*. Here is a snippet:

def poly_change(n_ominoes):

    n_plus1_ominoes = []
    for p in n_ominoes:
        for square in find_adjacent(p):
            new_t = p + [square]
            new_t = slide_to_zero(new_t)
            new_t.sort()
            if is_not_in(new_t, n_plus1_ominoes):
                n_plus1_ominoes.append(new_t)

    for p in n_plus1_ominoes:
        fancy_print_board(p)
        print p
    print len(n_plus1_ominoes)
    return n_plus1_ominoes

Here’s how she bootstrapped from tetrominoes to decominoes. I suggested using a for-loop, but she preferred this way:

S1 = [(0, 0), (0, 1), (0, 2)]
B1 = [(0,0), (0,1), (1,0)]
trominoes   = [B1,S1]
tetrominoes = poly_change(trominoes)
pentominoes = poly_change(tetrominoes)
hexominoes  = poly_change(pentominoes)
septominoes = poly_change(hexominoes)
octominoes  = poly_change(septominoes)
nonominoes  = poly_change(octominoes)
decominoes  = poly_change(nonominoes)

At each step from n-ominoes to (n+1)-ominoes she ran the code and checked that the number of polyominoes found by her program was the same as what we could find reported online.

We stole code for finding all tilings of a given shape (our decominoes) with a given set of tiles (our pairs of pentominoes). I had also written some wrapper code for it previously. Here’s (a bit of a simplification of) the main loop Abby wrote to do each of her trials:

for d in decominoes:
    for pop in combinations(Pentominoes, 2):
        tile_pair(d, pop)

Of the 307,230 trials only 3,486 (about 1%) had any tilings at all. Of those 3,486 trials that could be tiled, only 41 (again, about 1%) could be tiled in more than one way. Each of those 41 could be tiled in exactly two ways (none could be tiled in three or more ways). Of the 41, 39 had a reflection symmetry (and this symmetry was what caused there to be two tilings). Here’s an example of one of those 39:

symm_pair

The other two trials that could be tiled in two ways, but have no symmetry are the ones that I think are most interesting. These two are shown at the top of the post. Here they are again:

nosymm

I call them Abby’s puzzles, thinking of them as a board to fill in with a pair of pieces. We had tons of fun! I hope that Abby continues learning math and programming.


*I had written find_adjacent() and fancy_print_board() for a previous project. is_not_in() took some thinking, but again, it was largely Abby who did it.

About these ads
This entry was posted in computers and tagged , , , , , , , , , , , , . Bookmark the permalink.

11 Responses to Abby’s Puzzles

  1. Evelyn Lamb says:

    That is such a neat project! To me, it’s shocking that a 4-year-old can learn to program so well and keep her focus, but it turns out she hasn’t aged nearly as much in my mind as in real life. :)

  2. Evelyn Lamb says:

    Oh, I forgot the math content of my comment! I find it interesting that the two with two tilings use the same shape pieces. To me, it’s not obvious that this has to be the case.

    • toomai says:

      Ha! Yeah, they grow up fast!

    • toomai says:

      Oh, I didn’t explain the math very well. We were specifically looking for cases where given both the decomino *and* the pair of pentominoes you could tile it in two ways. So there are lots of decominoes with multiple tilings, but we were restricting ourselves to multiple tilings without changing the pieces.

      • Evelyn Lamb says:

        Oh, now I see my comment was kind of silly. Of course, if you split a decomino into two connected subsets of 5 tiles, those are both pentominoes. Each possible arrangement of 5 connected squares is a pentomino, so you can definitely tile it. I’d guess that for most decominoes, you can split them into two connected subsets of 5 squares in multiple ways, so there’s no reason to think it would be hard to tile them in multiple ways.

      • toomai says:

        Evelyn: Right, only now you’re going a bit far the other way. Turns out that there are lots of decominoes that any way you split it into two sets of 5 squares at least one of them is disconnected. I tried to get Abby to gather some data also on the decominoes themselves (which decomino has the most tilings, that sort of thing) but once she had answered her original question she decided she was done.

  3. in the event that you part a decomino into two associated subsets of 5 tiles, those are both pantomimes. Every conceivable course of action of 5 associated squares is a pentomino, so you can without a doubt tile it. I’d figure that for most decominoes, you can part them into two associated subsets of 5 squares in various courses, so there’s no motivation to think it might be difficult to tile them in numerous ways.

    • toomai says:

      True that parting a decomino into two sets of 5 is a pentomino so long as you are counting disconnected sets of tiles as pentominoes, which is non standard. So therein lies the crux of the matter.

  4. TeacherStudent says:

    Hi! Is it possible to have the script for the whole project? It looks fUntastic! :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s