Fall 2016, problem 27

m is the number of rows and n is the number of columns

First off, if a subset of the board is 3a x b, it can be filled using ab 3 x 1 pieces arranged in b rows (or columns) of a pieces lined up end to end. (referred to as "line 2" later on)

I will start by showing that any board with m,n greater than or equal to 8 can be totally covered.

Let's take a look at linear combinations of 3 and 5 (only positive multiples). 3x, 3x+5, and 3x+10 are all obviously linear combinations of 3 and 5.

3x+5 = 3(x+1)+2 and 3x+10 = 3(x+3)+1

3x covers all multiples of 3, 3x+10 covers all numbers 1 more than a multiple of 3 that are greater than 10, and 3x+5 covers all number 2 more than a multiple of 3 which are greater than 5. The only natural numbers this leaves which cannot be formed with a linear combination of 3 and 5 are 1, 2, 4, and 7.

Now, set y0 = m mod 3, and z0 = n mod 3 if either y0 = 0 or z0 = 0, the entire board can be covered using 3 x 1 pieces using line 2. If y0 does not equal 0 and z0 also does not equal 0, divide the board into four zones.

Zone 1 is in the bottom left corner of the board and will contain only 5 x 2 pieces which have the same orientation Zone 2 is directly above Zone 1 extending to the top of the board Zone 3 is directly to the right of Zone 1 extending to the right edge of the board Zone 4 is the rest of the board

y1, y2, y3, and y4 are the number of rows in zones 1 through 4 mod 3 z1, z2, z3, and z4 are the number of columns in zones 1 through 4 mod 3

If zones 2, 3, and 4 all have either a y value of 0 or a z value of 0, all three of these zones can be filled using line 2

For clarification on the zones, y1 = y3, y2 = y4. z1 = z2, z3 = z4. y1 + y2 = y0, z1 + z3 = z0.

Now, if y0 and z0 both equal 2, Zone 1 will consist of one 5 x 2 piece, so y1 and z1 will both equal 2. This means y2 and z3 are both 0, and zones 2 through 4 can all be filled using line 2 If y0 = 1 and z0 = 1, Zone 1 will consist of four 5 x 2 pieces in a 2x2 configuration (all four have the same orientation), so y1 and z1 will both equal 1. Again, this means y2 and z3 are both 0, and zones 2 through 4 can be filled. If y0 = 2 and z0 = 1, Zone 1 will consist of two 5 x 2 pieces. One in the very bottom left and immediately adjacent and to the right (again, same orientation), so y1 = 2 and z1 = 1. Again, this means y2 and z3 are both 0, and zones 2 through 4 can be filled. If y0 = 1 and z0 = 2, Zone 1 will consist of two 5 x 2 pieces. One in the very bottom left and immediately aabove the first (again, same orientation), so y1 = 1 and z1 = 2. Again, this means y2 and z3 are both 0, and zones 2 through 4 can be filled.

This proves that any board with at least 8 rows and at least 8 columns can be covered, so now we just need to look at smaller boards.

A board with m=1 must have n be a multiple of 3 A board with m=2 must have n be a linear combination of 3 and 5 (n not 1, 2, 4, or 7) if z0 = 0 use only 3x1 pieces using line 2, if z0 = 2 place a 5 x 2 piece in the corner and fill the rest using 3x1 pieces using line 2, and if z0 = 1 place two 5 x 2 pieces starting in the corner and fill the rest using 3x1 pieces using line 2 A board with m=3 can always be coverd using line 2 A board with m=4 can be covered if n is either 7 or a linear combination of 3 and 5 (n not 1, 2, or 4). If n is not 7, you can create two 2xn boards and stack them on top of one another. If you have a 4x7 board, place a 5x2 piece in very center and surround it with 1 layer of 3x1 pieces (start in the corner and line them up around the 5x2 piece) A board with m=5 can be covered if n is not 1. if z0 = 0 use only 3x1 pieces using line 2, if z0 = 2 place a 5 x 2 piece in the corner with the long side along the left edge and fill the rest using 3x1 pieces using line 2, and if z0 = 1 place two 5 x 2 pieces starting in the corner with the long sides along the left edge and fill the rest using 3x1 pieces using line 2. A board with m=6 can be covered using 3x1 pieces using line 2 A board with m=7 can be covered if n is a linear combination of 3, 4, and 5 (n not 1 or 2). a 7x3 board can be covered using only 3x1 pieces using line 2. A 7x4 board is identical to a 4x7 board, see above. A 7x5 board is identical to a 5x7 board, see above. If z0 = 0, place 7x3 boards next to each other until the board is covered. If z0 = 1, place a 7x4 board in the corner with 7x3 boards immediately to the right until the board is covered, and if z0 = 2, place a 7x5 board in the corner with 7x3 boards immediately to the right until the board is covered.

In summary, A board with m or n equal to one must have the other be a multiple of 3. The only other boards which can't be covered are a 2x1, 2x2, 2x4, 2x7, or 4x4. Sorry for having such a long answer, just trying to be thorough.

The authors are not 100% clear on that, but naturally I assume that the $1 \times 3$ and $2 \times 5$ pieces can be oriented horizontally or vertically as you like, like dominoes.

If an $m \times n$ board can be covered in the required way, we say, that the pair $(m,n)$ is good. Otherwise call it bad.

There is an infinite class of bad pairs: If $n = 1$ and $m \equiv \pm 1 \textrm{ mod } 3$, then $(m, n)$ is bad.

There are four more bad pairs: (2,2), (4, 2), (4,4), (7, 2) ( edit: had (7,4) in this list. But this one is good. see cliff_o's answer ). Up to interchanging $(m,n) \leftrightarrow (n,m)$ the bad pairs given above are already all the bad pairs.

Proof:

Technical detail: When I write $\mathbb{N}$ I always mean the nonnegative integers, that is including zero.

We think about an $m \times n$ board as being $m$ units wide and $n$ units high.

You can easily check , that:

• All $s \in \mathbb{N}$, $s>= 2$ can be written in the form $s = 3 a + 2 b$, where $a,b \in \mathbb{N}$.
• All $s \in \mathbb{N}$, $s >= 8$ can be written in the form $s = 5 a + 3 b$, where $a,b \in \mathbb{N}$.

It's a simple matter, to check, that the pairs given at the beginning of the text are indeed bad. Now let's exhaust the possibly bad pairs: Choose $(m,n)$, $m>=n$ arbitrary. If $n = 1$, then $(m, n)$ is bad if and only if $m \equiv \pm 1 \textrm{ mod } 3$, so nothing new. So assume $n >=2$. Write $n = 3 a + 2 b$ and divide the $m \times n$ board into an $m \times 3 a$ board and an $m \times 2 b$ board. The $m \times 3 a$ board is always good, since you can cover it with $1 \times 3$ pieces only. If $m >= 8$, then the $m \times 2b$ board is also good, since you can cover it by placing horizontally next to each other $5 \times 2$ pieces and pairs of $3 \times 1$ pieces stacked on top of each other thus making a $3 \times 2$ piece. It is the representation $m = 5 c + 3 d$, that allows you to do that.

Up to now what we have shown is that if there are any bad pairs, we haven't already mentioned, then they are in the rather small set $\{(m, n): 2 \leq n \leq m \leq 7\}$. You can quickly convice yourself with pen and paper that $(2,2), (4,2),(4,4),(7,2)$ are indeed all bad examples in this set.