# What the L are they trying to prove?

Seems some L t rominoes have developed a punk attitude and feel they have something to prove because people always play with dominoes instead.   They are even jealous of I trominoes, who can try to pass for tall dominoes.

One L of a tromino has devised a caper that might at last gain some notoriety, or at least draw some attention, as long as enough Ls gang up to pull it off.   No problem recruiting, with this persuasive floor plan of the target. Just what are these Ls out to prove by this?

Will they succeed?

They are trying to prove that

any rectangular grid with side-lengths congruent to each other and not to zero modulo 3, with a single cell removed in the middle, can be covered by L-trominoes.

How are they doing it?

By induction: starting with the $(3M\pm1)\times(3N\pm1)$ rectangle shown on the left, reducing it to the cases of four smaller rectangles, and continuing to apply the same reduction multiple times until they end up with a $2\times(3z-1)$ rectangle, which can be covered as shown on the right.

Will they succeed?

Unknown. The proof doesn't guarantee that they'll always end up with a collection of $2\times(3z-1)$ rectangles without involving any $1\times(3z+1)$ rectangles (which clearly aren't coverable by trominoes). In fact, it appears that the general statement being considered is an open problem.

A special case of the result being considered may be found at Maths SE (spoilers, obviously). The L-ish proof here uses the same underlying idea, but with the difference that

we can't always split the board into four equally sized rectangles each time.

They try to prove

Every rectangle of unit squares with a corner square removed can be tiled by L triominoes unless there is an obvious reason to fail.

Note that

"the number of squares to cover is not a multiple of 3"

and

"one side length is 1"

are obvious reasons to fail.

The proof can be elaborated like this:

Suppose we have an $a\times b$ rectangle. As $ab-1$ must be a multiple of $3$ (see reasons to fail), we conclude $0\not\equiv a\equiv b\pmod 3$. Wlog. $a\le b$. We may assume $a>1$ (see reasons to fail). If $a=2$, we must have $b=3k+2$, $k\ge 0$. Cover the missing corner with an L to be left with a $2\times 3k$ rectangle that can easily be tiled by several $2\times 3$ rects, each of which is tiled by two L. If $a>2$, we can partition $a=a_1+a_2$ with $a_1\equiv a_2\equiv -a\pmod 3$ and $a_1,a_2>1$. Likewise $b=b_1+b_2$ with $b_1\equiv b_2\equiv -b\pmod 3$ and $b_1,b_2>1$. It follows that $a_ib_j\equiv 1\pmod 3$. By induction hypothesis, we may assume that $a_i\times b_j$ with one corner removed can be tiled. By placing an L next to the line intersection defined by the two partitions to overlap the three sub-rects not yet missing a corner square, we obtain a tiling of the original $a\times b-1$ situation. -- Note that the "proof without words" shown has a typo in it as the gap on the left should be in the to right instead of at the intersection. (Or if we insist on the image being as intended, the proof does not work out for all positions of the gap)

• But the initial $(3M\pm1)\times(3N\pm1)$ rectangle doesn't have a corner square removed. – Rand al'Thor Jan 15 '17 at 22:07
• ^vote with a note: "(...the proof does not work out for all positions of the gap)" is more to the point than "... has a typo ..." – humn Jan 15 '17 at 22:49