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:
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)
if is_not_in(new_t, n_plus1_ominoes):
for p in 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):
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:
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:
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.