Home > Uncategorized > Putnam 2016 – A4

## Putnam 2016 – A4

Problem A4. Consider a ${(2m-1)\times(2n-1)}$ rectangular region, where ${m}$ and ${n}$ are integers such that ${m,n\geq 4}$. The region is to be tiled using tiles of the two types shown below

(The dotted lines divide the tiles into ${1\times 1}$ squares.) The tiles may be rotated and reflected, as long as their sides are parallel to the sides of the rectangular region. They must all fit within the region, and they must cover it completely without overlapping.

What is the minimum number of tiles required to tile the region?

Solution: For simplicity I’ll call the ${3}$ square piece a corner and the ${4}$ square piece a zig-zag.

As in the classical problem where we are asked if we can tile the ${8\times 8}$ checkerboard with two opposites corners removed with ${2 \times 1}$ dominos, the first idea that comes to mind is to color the tiling domain in a way that might help the reasoning. We’re not going to use the checkerboard coloring since it is not clear how many colored squares of each kind a piece will contain once we put it on the board…

So let’s decide what’s the best coloring. Ideally we’d like that every piece contains one colored square. That means that if we color a square, those immediately near it horizontally, vertically or diagonnally should not be coloured. Thus we can try to color every second square in each direction starting from a corner. This leaves us with a board with every square which has odd coordinates coloured. See the figure for one example.

Now is this coloring any good? A bit of analysis says yes, since any zig-zag covers exactly one coloured square and every corner covers at most one coloured square. Thus we need at least as many pieces on the board as coloured squares. On a ${(2m-1)\times (2n-1)}$ board this means ${mn}$ pieces at least.

Now we have a lower bound and we want to see if it can be reached. For this we look at what patterns we can create using the corner and the zigzag. It is not difficult to see that a succession of ${k-2}$ zigzags and two corners can be arranged to make a ${2 \times (2k-1)}$ rectangle. This means that if we can prove that the bound ${mn}$ is attained for the smallest case, the ${7 \times 7}$ square then we can complete with rectangles of width ${2}$ in order to reach any rectangles with odd dimensions greater than ${7}$.
First we need a tiling with ${16}$ pieces of the ${7 \times 7}$ square. One such tiling is presented in the picture. It is easy to find one such tiling once we realize that we can only use one zig-zag since ${49 = 3\cdot 15+4}$. Now we can reach the ${mn}$ bound on each rectangle by starting from the smallest case and adding rectangles of width ${2}$ until we reach the desired size.