Obviously, for \(n\) even we can just tile everything with O tetrominos for free. Thus, the interesting cases are just the ones with \(n\) odd.
The smallest subproblem is solvable by hand. We already know how to tile the squares for \(n\) even, and with some casework we can conclude that the other three squares have no valid tiling at all.
The case \(n=7\) can be solved by any reasonable brute force, e.g., recursion with backtracking. Such a program can examine the whole solution space in a few seconds. We will find out that it is solvable, but only barely: the only valid solutions have just a single tetromino + 15 triminos. (That feels a bit weird, doesn’t it?)
One possible solution:
aabbaab
aabcabb
bbaccaa
bcaabac
ccdbbcc
addcaab
aaccabbIn order to fully examine the state space for \(n=9\) we’ll need to prune our search quite considerably, as the naive backtracking runs “forever”. Still, the optimal solutions (with 6 tetrominos and 19 triminos) are plentiful and our implementation could run into one of them almost instantly.
Once we have it, we always have the option to submit the solution to T2 and check that way whether what we found is already optimal.
Tiling problems are often solved by finding a suitable invariant, such as chessboard coloring or total area modulo some small number. For good measure we can check these traditional invariants, but – spoiler alert – they aren’t going to give us much useful information.
On an odd-sized board with chessboard coloring, the number of black cells is one greater than the number of white cells. Each S, Z, O covers two black and two white tiles, each L covers two of one type and one of the other. Thus, we need at least one L.
More precisely, we can conclude that the number of black-white-black L tiles will always be one greater than the number of white-black-white L tiles, but so far we don’t have any reason to expect those to appear. From this argument alone it might still be possible that there is a single L covering two black + one white cell, and the entire rest of the board is covered by four-cell tiles.
In terms of area, each odd-sized board has \(4k+1\) cells, for some \(k\). As each tetromino covers four, in order to get the correct remainder modulo 4, we need to have \(4\ell + 3\) triminos for some \(\ell\). Thus, there are at least 3 Ls in any valid tiling.
Finally, we can combine this with the previous observations and conclude that in any valid tiling there have to be \(2\ell+2\) black-white-black Ls and \(2\ell+1\) white-black-white Ls for some \(\ell\).
In my opinion, the nicest property of this problem is precisely the fact that these standard approaches don’t work – as we just saw on the solutions for \(n=7\) and \(n=9\), these lower bounds are nowhere near tight. For some reason we seem to be forced to use many more than three Ls in all valid tilings for these \(n\).
Our key argument will be based on the following observation. Consider the cells with both (0-based) coordinates even. In the figure below we have \(n=7\) and these cells are shown as X.
X.X.X.X
.......
X.X.X.X
.......
X.X.X.X
.......
X.X.X.XClearly, none of our tiles can cover more than one X. Thus, the total number of tiles needs to be at least equal to the number of Xs: for \(n=2k+1\) we need at least \((k+1)^2\) tiles.
If \(t\) (\(t\) as in “three”) is the total number of triminos in a tiling and \(f\) (\(f\) as in “four”) is the total number of tetrominos of any allowed shape, we now have two constraints:
From these constraints we can directly see that for \(n \in \{1,3,5\}\) there is no solution. E.g., for \(n=5\) we need at least 9 tiles, but then their total area is at least 27, which is more than the \(n^2 = 25\) cells we actually have.
The smallest solvable odd \(n\) is \(n=7\). From \(t+f\geq 16\) and \(3t+4f=49\) we get \(f\leq 1\) and the only valid solution is \(t=15\) and \(f=1\). Thus, each valid tiling of a \(7\times 7\) square must have fifteen Ls and just a single tetromino – which is much higher than what the trivial lower bound of three Ls was telling us.
From \(t + f \geq (k+1)^2\) we get \(3t + 3f \geq 3k^2 + 6k + 3\).
Together with \(3t + 4f = (2k+1)^2 = 4k^2 + 4k + 1\) that gives us \(f\leq k^2 - 2k - 2\).
As \(3t+4f\) is a constant, minimizing \(t\) (which is our goal) is the same as maximizing \(f\). Thus, if we can construct a tiling in which \(f\) is exactly equal to the shown upper bound, we can be certain that said tiling is the cheapest one possible.
And this will indeed be the case: We will show that for any solvable \(n=2k+1\) we can always construct a tiling with \(f\) being exactly equal to the upper bound we just proved.
We will show that all optimal tilings for odd \(n\) can be constructed incrementally from the optimal tiling for \(n=7\).
Suppose we already have an optimal tiling for \(n=2k+1\) that uses \(f=k^2 - 2k - 2\) tetrominos. For \(n'=2k+3\) we seek a tiling with \(f'=(k+1)^2 - 2(k+1) - 2\) tetrominos. I.e., the new tiling should have \(f'-f = 2k-1\) more tetrominos than the old one.
Observe, for example, the following tiling of a \(2 \times (2k+1)\) rectangle:
xxaabbccddy
xaabbccddyyClearly, this tiling contains \(k-1\) tetrominos and two triminos.
Thus, we can: