A $15×15$ chessboard was covered by $3×3$ and $2×2$ plates in such a way that the plates don't stick out of the chessboard, they don't overlap each other and every field of the chessboard is covered. Find the smallest number of $3×3$ plates used, for which it is possible.
While analyzing this problem i came to the conclusion that the number of nine $3×3$ plates is enough for this to work, but I have no idea how to prove it correctly
On
Very fun question! I was not satisfied with any of the solutions so far, because they do not generalize to larger boards. But together with a friend I found the general solution to the question of how many $3\times3$ tiles are necessary for an $n\times m$ board with $n,m\geq2$.
First of all, if $n$ and $m$ are even, then we can tile the board with $2\times2$ tiles only. So let us assume without loss of generality that $n$ is odd from now on.
Lemma: For all $i\geq0$ with $3i<m$ we need a $3\times3$ tile with its top on row $3i$. (Use zero-based indexing from top to bottom.)
Proof of lemma: Let $t_j$ denote the number of $3\times3$ tiles with their top on row $j$. First note that $t_j=0$ holds for $j<0$ and for $j>m-3$, because plates are not allowed to stick out of the chessboard. Furthermore, the total number of $3\times3$ tiles on row $j$ is $t_j+t_{j-1}+t_{j-2}$. We only have $2\times2$ and $3\times3$ tiles and a $2\times2$ tile has an even width and a $3\times3$ tile has an odd with. Since all rows $0\leq j<m$ are $n$ wide and since $n$ is odd, we need to have an odd number of $3\times3$ tiles in all rows. So $t_j+t_{j-1}+t_{j-2}$ is odd for all $0\leq j<m$.
By induction we will use this to prove that $t_{3i}$ is odd for all $i\geq0$ with $3i<m$. The base case follows from the case $j=0$. Assume $t_{3i}$ is odd for some $i\geq0$ with $3i+3<m$. Using the cases $j=3i+2$ and $j=3i+3$, we find that both $t_{3i}+t_{3i+1}+t_{3i+2}$ and $t_{3i+1}+t_{3i+2}+t_{3i+3}$ are odd. From this, we get $t_{3i}\equiv t_{3i+3}\ (\mbox{mod}\ 2)$, so $t_{3i+3}$ is odd.
Since $t_{3i}$ is odd for all $i\geq0$ with $3i<m$, we certainly have $t_{3i}\geq1$. This proves the lemma.
Corollary: We need $m$ to be divisible by $3$. This is, again, because plates are not allowed to stick out of the chessboard.
There are two cases to consider. Either $m\equiv0\ (\mbox{mod}\ 6)$ or $m\equiv3\ (\mbox{mod}\ 6)$.
Case $m\equiv0\ (\mbox{mod}\ 6)$: Write $m=6\ell$. From the lemma, we know the amount of $3\times3$ tiles needed is at least $2\ell$. But this can also easily be achieved. We fill the left $3$ columns with $3\times3$ tiles and the rest can be filled with $2\times2$ tiles. This is possible, because $n-3$ and $m$ are both even.
Case $m\equiv3\ (\mbox{mod}\ 6)$: This is the interesting case. We write $m=6\ell+3$. By symmetry, from the corollary we find that $n$ is also a multiple of $3$, so we write $n=6k+3$. First note that $2k+2\ell+1$ is an upper bound on the necessary amount of $3\times3$ tiles, because we can fill the top $3$ rows and left $3$ columns with $3\times3$ tiles and then fill the rest with $2\times2$ tiles. This is possible because $n-3$ and $m-3$ are both even. The claim is that this is optimal.
We colour the tiles of the chessboard with the colours $1$, $2$, $3$ and $4$. Rows $0,2,...$ will alternate $1,2,1,2,...$ and rows $1,3,...$ will alternate $3,4,3,4,...$. Note that any $2\times2$ tile covers every colour exactly once. Also note that there are $(3k+2)(3\ell+2)$, $(3k+1)(3\ell+2)$, $(3k+2)(3\ell+1)$ and $(3k+1)(3\ell+1)$ tiles of the colours $1$, $2$, $3$ and $4$ respectively.
Let $a$, $b$, $c$ and $d$ denote the numbers of $3\times3$ tiles with their center on a tile with colour $1$, $2$, $3$ and $4$ respectively. By counting the amount of tiles a $3\times3$ tile covers of every colour, and using the fact that $2\times2$ tiles cover every colour exactly once, we find the following equations. \begin{align*} 3(d-a)&=(3k+2)(3\ell+2)-(3k+1)(3\ell+1)=3k+3\ell+3 \\3(c-b)&=(3k+1)(3\ell+2)-(3k+2)(3\ell+1)=3k-3\ell \end{align*} So $d=a+k+\ell+1$ and $c=b+k-\ell$. Note that we can assume without loss of generality that $k\geq\ell$.
By applying the lemma to all odd $i$, we find that $a+b\geq\ell$. Using this, we also get $c+d=a+b+2k+1\geq2k+\ell+1$. Combining the two, we finally get $a+b+c+d\geq2k+2\ell+1$, which proves the claim.
On
This is a modification to the lemma in SmileyCraft's answer which is a bit more general, and a stepping stone in finding a more general result for the complete problem.
Lemma: Suppose $x$ and $y$ are relatively prime. Suppose $r$ is the smallest positive integer such that $yr \equiv m \pmod x$. In a tiling of $m \times n$ by two squares $x\times x$ and $y \times y$, we need at least $r\lceil\frac{n}{y}\rceil$ of the $y\times y$ squares.
Proof: In each row, we must have $px + qy = m$ for some integers $p$ and $q$. This implies $qy \equiv m \pmod x$. Thus $q \geq r$, and so in each row we need at least r squares of type $y \times y$. Each of these squares can cover at most $y$ rows, so we need $r\lceil\frac{n}{y}\rceil$ of them in total.
Some ideas on generalizing the complete result.
There is a theorem that states the following:
If a $m \times n$ rectangle is tileable by two squares $x \times x$ and $y \times y$, then one of the following hold:
(This is one of many variations on de Bruijn's famous rectangle tiling theorem, by Fricke. See for example When Can You Tile a Box With Translates of Two Given Rectangular Bricks?, Corollary 7.)
In case 1, there is a tiling by $x \times x$ alone, and we don't need any of the $y \times y$ tiles.
Case 2 is more difficult, and it probably requires some version of the argument in SmileyCraft's answer. This requires more tiles than we can determine from the lemma.
Case 4 can be treated by splitting the rectangle into two rectangles: $ry \times n$ and $(m-ry) \times n$. The first can be tiled by $y \times y$, and requires $n/y$ such tiles, which is the minimum of the lemma. The second rectangle is tileable by $x\times x$.
Case 3 can be handled by symmetry similarly to case 4. (This also made me realize the lemma can be applied to columns instead of rows, giving another lower bound, and the actual number must be at least as high as both.)
Along a row, the squares occupied by $3\times 3$ plates have to be such that the intervals between them (and between the borders and them) are made by an even number of squares. It follows that every row (and column) meets an odd number of $3\times 3$ plates.
Assuming that five $3\times 3$ plates are sufficient, they have to be placed like the non-zero entries in a $5\times 5$ permutation matrix. But this implies that, along some row, exactly three squares occur before meeting the $3\times 3$ plate, and these squares cannot be covered by an integer number of $2\times 2$ plates.
Now, let us assume that that seven $3\times 3$ plates are sufficient. The only way to partition $7$ into an odd ($\leq 5$) number of odd ($\leq 5$) parts is $3+3+1$, but this gives that along some row/column there is no $3\times 3$ plate.
It follows that nine $3\times 3$ plates are necessary, and they have already been proved to be sufficient.
The previous criteria also give that there are very few (just nine) ways to tile a $15\times 15$ board with nine $3\times 3$ plates and thirty-six $2\times 2$ plates.