# Completing the Square

Imagine a 6 x 6 grid of 36 equal minisquares, or tiles. A "shape" consists of interconnected adjacent tiles on this grid. [Adjacent tiles must share an edge, not merely a vertex.]

Prove the number of discrete combinations of 4 congruent shapes (9 tiles each) that will complete the grid.

One obvious combination is 4 congruent "sub-squares" of 9 tiles each. But there are several other valid shapes which one can find graphically by experiment. Which method(s) of proof is best used to determine the precise number? How would this proof be constructed? Is this problem and its proof methodology generalizable to completing similar grids, matrices etc.?

Look forward to hearing your ideas on this,

Scott

You can find about 30 examples at Mike Reid's Rectifiable polyomino page. It would appear that for the 6x6 square there are two types of 9 cell tilers:

• Take the center edge of a 3X6 rectangle along with a path from one end of that edge to the boundary and the 180- degree rotation starting from the other end

and

• Take a path from the center of a 6x6 square and rotate it by 90,180 and 270 degrees.

So a method to do all this (which I have not done) would have these steps: Find all tiles of these two types. (One needs a path which does not intersect its 1 or 3 partner paths, there can only be so many so go about it systematically). Then show that a tiling must decompose into 2 3x6 rectangles or else have a 4-fold central rotational symmetry.

Most work I know starts with a tile and asks what rectangles it tiles. I would consider it pretty interesting to prove or disprove that any partition of a square into 4 congruent pieces is of one of these two types. Maybe that is already known one way or the other. I am not aware that anyone has looked systematically at dividing a checkerboard into 4 congruent pieces. Here is a decomposition of a 14x14 square into 16 7-cell tiles. It does have a 4-fold rotational symmetry.

further comments This is a fascinating field. Search the literature and you will find some contributions by well known names but you will also find that some of the best results come from "amateurs". I use the term only in the sense of someone who does it exclusively for the love of the subject. An easier problem than yours is: How many ways to split a $k$ by $2k$ rectangle into two congruent pieces? You would have to solve that to solve your problem. Already that is a difficult lattice path problem. For particular small $k$ you could do it but in general asymptotics might be the best one could expect.

• One can look at equivalence classes of squares under clockwise rotation around the center, pick one from each of the nine classes, and call the assemblage a 'shape'. The less trivial problem is to count how many such shapes are connected. Gerhard "Ask Me About System Design" Paseman, 2011.05.20 – Gerhard Paseman May 20 '11 at 22:08
• Indeed, this is not a trivial problem. I'm still looking for some rigorous expert commentary on how the number of valid combinations (according to my aforementioned criteria)for a specific size square can be proven. Thus far you've offered some interesting suggestions for counting, but nothing close to a method of systematic proof. It could be there's much work to be done here, but I have a feeling we just haven't been able to yet source this quality of work most likely performed in higher academic circles. – Scott S May 21 '11 at 4:09
• You will find that many problems like this are part of the combinatoric literature. Polyominoes, graphs, and other structures are not understood well enough to be easily counted, or even well-estimated. My approach would take advantage of certain symmetries and restrictions, but would still resemble brute force enumeration at some point. I think you will find that or a representation in terms of some other enumeration problem if you search the literature. A nice systematic proof with few cases is unlikely to be had. Gerhard "Ask Me About System Design" Paseman, 2011.05.20 – Gerhard Paseman May 21 '11 at 5:21
• I added a bit. You could ask Michael Reid. I think that he knows as much as anyone. – Aaron Meyerowitz May 21 '11 at 6:05

To underscore my comments posted under another answer, here is a start of an enumeration which would be pretty messy when completed.

I will cover the case of 4-fold rotational symmetry. I consider the lower left 3x3 squares which I label with coordinate pairs (1,1) through (3,3). (3,3) is a central square which by symetry I assume to be part of any shape I count. Since I am interested in connected shapes, one of (3,2) or (2,3) (squares below and/or to the left) must belong to the shape as well. Suppose both are: then there are 64 cases to consider, where each of the remaining 6 squares of the lower left 3x3 square is part of the included shape or not.

Suppose square (2,2) is not part of the shape. Then one of its three equivalent (under rotation) squares must be. Some thought will show that it is not the (5,5) square. Say it is the (5,2) square, then at least two more squares will be needed to connect it to the squares in the lower left corner. so at most 3 more squares are allowed in our shape from the lower left corner.

I could go on using words; it would be easier to list the allowed shapes that I discovered by trial and error, and submit that as a list. It is possible that an alternate categorization (counting those where (1,1) and/or (2,2) are part of the shape, for example) might lead to a more concise counting, but most people who would need the count would probably spend the time trying to derive it for themselves rather than read your derivation. Again, I do not see a solution to this problem that is quick and easy with few cases to consider.