Suppose you have infinitely many 3-by-3 cm tiles and infinitely many 5-by-5 cm tiles. You want to use some of these tiles to precisely cover a square whose side length is a whole number of centimeters. Tiles may not overlap, and they must completely cover the larger square, without jutting beyond its borders. What is the smallest side length this larger square can have, such that it can be precisely covered using at least one 3-by-3 tile and at least one 5-by-5 tile?
Extra credit:
This time, you have an infinite supply of square tiles for each odd whole number side length (as measured in centimeters) greater than 1 cm. In other words, you have infinitely many 3-by-3 cm tiles, infinitely many 5-by-5 cm tiles, infinitely many 7-by-7 cm tiles, and so on. You want to use one or more of these tiles to precisely cover a square whose side length is $N$ cm, where $N$ is an integer. Once again, tiles may not overlap, and they must completely cover the larger square without jutting beyond its borders. What is the largest integer N for which this task is not possible?
This problem is about tiling squares with smaller squares, which is a famous problem known as “squaring the square”. There is a nice wikipedia article about it, and also a website I found with a comprehensive database of different tilings. There are certain properties of interest when it comes to squaring the square:
- simple tiling: it contains no sub-tilings
- perfect tiling: all sub-squares are of different size
- symmetric: there are certain rotational or reflection symmetries present in the final shape.
However, none of this is going to help us, since we don’t care about these properties for the purpose of this problem!
In our case, we can can repeat tiles (not perfect), we can have sub-tilings (not simple) and we do not enforce any special symmetry. Moreover, we are restricted in the kinds of tiles we can use. To tackle this problem, I formulated the problem as a mixed integer program using a column enumeration approach. This is the same approach I used to solve a similar past Riddler problem from 2017, so if you’re interested in how I did the modeling, be sure to read that previous post!
First problem: minimum size
I re-used the code from the 2017 post linked above and made two changes:
- restricted the available tiles to 3×3 and 5×5 only.
- added a constraint that requires using at least one of each type of tile.
I looped through possible total sizes starting from 4×4 and stopped once the integer program found a tiling. The smallest size is $N=18$ and one possible tiling is shown below.
The code made short work of this problem, testing all $N\leq 18$ in a couple seconds.
Second problem: maximum size
The second problem is a bit trickier, since we are asked for the largest square that cannot be tiled. So we’ll need to do a bit of deductive work before we turn to computation. If there exists a tiling of an $N\times N$ square using only odd-sized square tiles, I will say that $N$ is “tileable”. Now some observations:
- Any odd $N$ is tileable (use a single large tile of size $N\times N$).
- If $M$ is tileable, then $N = k M$ is tileable for any $k$. We can simply start with the tiling for the $M\times M$ square, and then repeat it in a $k\times k$ pattern to obtain the $N\times N$ tiling.
- By items 1 and 2, if $N$ is not tileable, it must be a power of $2$.
- By item 2, if $N = 2^k$ is tileable, so is any larger power of $2$.
In other words, it suffices to find the smallest tileable power of $2$, and all larger $N$ will also be tileable. Using the code again, this time allowing for tiles of all odd sizes, I was able to verify that $2$, $4$, $8$, and $16$ are not tileable, but $32$ is tileable!!! Here is one possible tiling, which uses tiles of size $3$, $5$, $7$, and $11$.
Therefore, we conclude that $N=16$ is the largest integer for which an $N\times N$ square cannot be tiled using smaller squares with odd sidelengths greater than $1$.
Computational note: I used the Gurobi solver to solve this problem, and it took about 16 seconds on my laptop. I also tried Mosek, but it was slower, coming in at about 40 seconds.
A contradiction
How is it possible that the smallest tileable $N$ is $18$ but the largest non-tileable $N$ is 16?
These are actually different problems! For the first problem, we were only allowed to use tiles of size 3×3 and 5×5. In this case, 18 is the smallest tileable number, but not all subsequent numbers are tileable! It turns out 19, 22, 23, 26, 28, 29 (and more…) are not tileable. In the second problem, we had more tiles at our disposal, so naturally there must be fewer non-tileable $N$’s in this case.