Find all positive integers $m,n$ such that the $m \times n$ grid can be tiled with figures formed by deleting one of the corners of a $2 \times 3$ grid. usjl, ST
Problem
Source: IMOC 2021 C8
Tags: combinatorics, Tiling, IMOC
CrazyInMath
25.08.2021 13:07
You can construct a $2\times5$, a $7\times10$, and a $7\times15$. Then you can build grids using these blocks (sorry for not putting the construction, I don’t know how to do it)
mathematics2004
25.08.2021 16:22
Thanks to above's hint. I was convincing myself that $mn$ should be even, and I got stuck trying to prove this until seeing #2. Here is a complete solution, hopefully. The answer is $5 \mid mn$, excluding the following: One of $m,n$ is $1$ or $3$. One of $m,n$ is $5$ and the other is an odd integer. Proof: First, the area of the tile is $5$, hence $5 \mid mn$. The problem is basically how to exclude the invalid ones. One of $m,n$ is $1$, which is clearly impossible. One of $m,n$ is $3$. Consider the leftmost part of grid, up to symmetry, there are three ways of tiling, which can be seen impossible as it produced a $1 \times 2$ part which cannot be tiled. [asy][asy] size(8cm); pen border = black+1.2; pen marker = red+1.6; picture p; filldraw(p, shift(0,2)*unitsquare, lightgreen, border); filldraw(p, shift(0,1)*unitsquare, lightgreen, border); filldraw(p, shift(0,0)*unitsquare, lightgreen, border); filldraw(p, shift(1,2)*unitsquare, pink, border); filldraw(p, shift(1,1)*unitsquare, lightgreen, border); filldraw(p, shift(1,0)*unitsquare, lightgreen, border); filldraw(p, shift(2,2)*unitsquare, pink, border); filldraw(p, shift(2,1)*unitsquare, pink, border); filldraw(p, shift(2,0)*unitsquare, white, border); filldraw(p, shift(3,2)*unitsquare, pink, border); filldraw(p, shift(3,1)*unitsquare, pink, border); filldraw(p, shift(3,0)*unitsquare, white, border); filldraw(p, shift(4,2)*unitsquare, white, border); filldraw(p, shift(4,1)*unitsquare, white, border); filldraw(p, shift(4,0)*unitsquare, white, border); add(shift(0,0)*p); picture q; filldraw(q, shift(0,2)*unitsquare, lightgreen, border); filldraw(q, shift(0,1)*unitsquare, lightgreen, border); filldraw(q, shift(0,0)*unitsquare, white, border); filldraw(q, shift(1,2)*unitsquare, lightgreen, border); filldraw(q, shift(1,1)*unitsquare, lightgreen, border); filldraw(q, shift(1,0)*unitsquare, white, border); filldraw(q, shift(2,2)*unitsquare, lightgreen, border); filldraw(q, shift(2,1)*unitsquare, white, border); filldraw(q, shift(2,0)*unitsquare, white, border); filldraw(q, shift(3,2)*unitsquare, white, border); filldraw(q, shift(3,1)*unitsquare, white, border); filldraw(q, shift(3,0)*unitsquare, white, border); add(shift(6,0)*q); picture r; filldraw(r, shift(0,2)*unitsquare, lightgreen, border); filldraw(r, shift(0,1)*unitsquare, lightgreen, border); filldraw(r, shift(0,0)*unitsquare, white, border); filldraw(r, shift(1,2)*unitsquare, lightgreen, border); filldraw(r, shift(1,1)*unitsquare, lightgreen, border); filldraw(r, shift(1,0)*unitsquare, white, border); filldraw(r, shift(2,2)*unitsquare, white, border); filldraw(r, shift(2,1)*unitsquare, lightgreen, border); filldraw(r, shift(2,0)*unitsquare, white, border); filldraw(r, shift(3,2)*unitsquare, white, border); filldraw(r, shift(3,1)*unitsquare, white, border); filldraw(r, shift(3,0)*unitsquare, white, border); add(shift(11,0)*r); [/asy][/asy] One of $m,n,$ is $5$ and the other is an odd integer. WLOG $m=5$, let's color the grid in the following fashion ( $5 \times 7$ for instance): [asy][asy] size(6cm); pen border = black+1.2; pen marker = red+1.6; picture p; filldraw(p, shift(0,4)*unitsquare, white, border); filldraw(p, shift(0,3)*unitsquare, white, border); filldraw(p, shift(0,2)*unitsquare, white, border); filldraw(p, shift(0,1)*unitsquare, white, border); filldraw(p, shift(0,0)*unitsquare, white, border); filldraw(p, shift(1,4)*unitsquare, white, border); filldraw(p, shift(1,3)*unitsquare, cyan, border); filldraw(p, shift(1,2)*unitsquare, white, border); filldraw(p, shift(1,1)*unitsquare, cyan, border); filldraw(p, shift(1,0)*unitsquare, white, border); filldraw(p, shift(2,4)*unitsquare, white, border); filldraw(p, shift(2,3)*unitsquare, white, border); filldraw(p, shift(2,2)*unitsquare, white, border); filldraw(p, shift(2,1)*unitsquare, white, border); filldraw(p, shift(2,0)*unitsquare, white, border); filldraw(p, shift(3,4)*unitsquare, white, border); filldraw(p, shift(3,3)*unitsquare, cyan, border); filldraw(p, shift(3,2)*unitsquare, white, border); filldraw(p, shift(3,1)*unitsquare, cyan, border); filldraw(p, shift(3,0)*unitsquare, white, border); filldraw(p, shift(4,4)*unitsquare, white, border); filldraw(p, shift(4,3)*unitsquare, white, border); filldraw(p, shift(4,2)*unitsquare, white, border); filldraw(p, shift(4,1)*unitsquare, white, border); filldraw(p, shift(4,0)*unitsquare, white, border); filldraw(p, shift(5,4)*unitsquare, white, border); filldraw(p, shift(5,3)*unitsquare, cyan, border); filldraw(p, shift(5,2)*unitsquare, white, border); filldraw(p, shift(5,1)*unitsquare, cyan, border); filldraw(p, shift(5,0)*unitsquare, white, border); filldraw(p, shift(6,4)*unitsquare, white, border); filldraw(p, shift(6,3)*unitsquare, white, border); filldraw(p, shift(6,2)*unitsquare, white, border); filldraw(p, shift(6,1)*unitsquare, white, border); filldraw(p, shift(6,0)*unitsquare, white, border); add(shift(0,0)*p); [/asy][/asy] Observe that any tile must cover at least one cyan grid, hence there are at most $2 \cdot \frac{n-1}{2}=n-1 <n$ tiles, a contradiction. Constructions: First let's introduce the tiling of $2 \times 5$ grid and $7 \times 15$ grid, as shown below. [asy][asy] size(10cm); pen border = black+1.2; pen marker = red+1.6; picture p; filldraw(p, shift(0,6)*unitsquare, lightgreen, border); filldraw(p, shift(0,5)*unitsquare, lightgreen, border); filldraw(p, shift(0,4)*unitsquare, cyan, border); filldraw(p, shift(0,3)*unitsquare, cyan, border); filldraw(p, shift(0,2)*unitsquare, cyan, border); filldraw(p, shift(0,1)*unitsquare, yellow, border); filldraw(p, shift(0,0)*unitsquare, yellow, border); filldraw(p, shift(1,6)*unitsquare, lightgreen, border); filldraw(p, shift(1,5)*unitsquare, lightgreen, border); filldraw(p, shift(1,4)*unitsquare, grey, border); filldraw(p, shift(1,3)*unitsquare, cyan, border); filldraw(p, shift(1,2)*unitsquare, cyan, border); filldraw(p, shift(1,1)*unitsquare, yellow, border); filldraw(p, shift(1,0)*unitsquare, yellow, border); filldraw(p, shift(2,6)*unitsquare, lightgreen, border); filldraw(p, shift(2,5)*unitsquare, grey, border); filldraw(p, shift(2,4)*unitsquare, grey, border); filldraw(p, shift(2,3)*unitsquare, red, border); filldraw(p, shift(2,2)*unitsquare, red, border); filldraw(p, shift(2,1)*unitsquare, red, border); filldraw(p, shift(2,0)*unitsquare, yellow, border); filldraw(p, shift(3,6)*unitsquare, magenta, border); filldraw(p, shift(3,5)*unitsquare, grey, border); filldraw(p, shift(3,4)*unitsquare, grey, border); filldraw(p, shift(3,3)*unitsquare, red, border); filldraw(p, shift(3,2)*unitsquare, red, border); filldraw(p, shift(3,1)*unitsquare, pink, border); filldraw(p, shift(3,0)*unitsquare, pink, border); filldraw(p, shift(4,6)*unitsquare, magenta, border); filldraw(p, shift(4,5)*unitsquare, magenta, border); filldraw(p, shift(4,4)*unitsquare, olive, border); filldraw(p, shift(4,3)*unitsquare, olive, border); filldraw(p, shift(4,2)*unitsquare, olive, border); filldraw(p, shift(4,1)*unitsquare, pink, border); filldraw(p, shift(4,0)*unitsquare, pink, border); filldraw(p, shift(5,6)*unitsquare, magenta, border); filldraw(p, shift(5,5)*unitsquare, magenta, border); filldraw(p, shift(5,4)*unitsquare, olive, border); filldraw(p, shift(5,3)*unitsquare, olive, border); filldraw(p, shift(5,2)*unitsquare, salmon, border); filldraw(p, shift(5,1)*unitsquare, salmon, border); filldraw(p, shift(5,0)*unitsquare, pink, border); filldraw(p, shift(6,6)*unitsquare, lightgrey, border); filldraw(p, shift(6,5)*unitsquare, lightgrey, border); filldraw(p, shift(6,4)*unitsquare, orange, border); filldraw(p, shift(6,3)*unitsquare, orange, border); filldraw(p, shift(6,2)*unitsquare, salmon, border); filldraw(p, shift(6,1)*unitsquare, salmon, border); filldraw(p, shift(6,0)*unitsquare, salmon, border); filldraw(p, shift(7,6)*unitsquare, lightgrey, border); filldraw(p, shift(7,5)*unitsquare, lightgrey, border); filldraw(p, shift(7,4)*unitsquare, orange, border); filldraw(p, shift(7,3)*unitsquare, orange, border); filldraw(p, shift(7,2)*unitsquare, orange, border); filldraw(p, shift(7,1)*unitsquare, springgreen, border); filldraw(p, shift(7,0)*unitsquare, springgreen, border); filldraw(p, shift(8,6)*unitsquare, lightgrey, border); filldraw(p, shift(8,5)*unitsquare, purple, border); filldraw(p, shift(8,4)*unitsquare, purple, border); filldraw(p, shift(8,3)*unitsquare, purple, border); filldraw(p, shift(8,2)*unitsquare, springgreen, border); filldraw(p, shift(8,1)*unitsquare, springgreen, border); filldraw(p, shift(8,0)*unitsquare, springgreen, border); filldraw(p, shift(9,6)*unitsquare, lightcyan, border); filldraw(p, shift(9,5)*unitsquare, purple, border); filldraw(p, shift(9,4)*unitsquare, purple, border); filldraw(p, shift(9,3)*unitsquare, lightyellow, border); filldraw(p, shift(9,2)*unitsquare, lightyellow, border); filldraw(p, shift(9,1)*unitsquare, lightblue, border); filldraw(p, shift(9,0)*unitsquare, lightblue, border); filldraw(p, shift(10,6)*unitsquare, lightcyan, border); filldraw(p, shift(10,5)*unitsquare, lightcyan, border); filldraw(p, shift(10,4)*unitsquare, lightyellow, border); filldraw(p, shift(10,3)*unitsquare, lightyellow, border); filldraw(p, shift(10,2)*unitsquare, lightyellow, border); filldraw(p, shift(10,1)*unitsquare, lightblue, border); filldraw(p, shift(10,0)*unitsquare, lightblue, border); filldraw(p, shift(11,6)*unitsquare, lightcyan, border); filldraw(p, shift(11,5)*unitsquare, lightcyan, border); filldraw(p, shift(11,4)*unitsquare, brown, border); filldraw(p, shift(11,3)*unitsquare, brown, border); filldraw(p, shift(11,2)*unitsquare, white, border); filldraw(p, shift(11,1)*unitsquare, white, border); filldraw(p, shift(11,0)*unitsquare, lightblue, border); filldraw(p, shift(12,6)*unitsquare, opacity(0.2)+red, border); filldraw(p, shift(12,5)*unitsquare, brown, border); filldraw(p, shift(12,4)*unitsquare, brown, border); filldraw(p, shift(12,3)*unitsquare, brown, border); filldraw(p, shift(12,2)*unitsquare, white, border); filldraw(p, shift(12,1)*unitsquare, white, border); filldraw(p, shift(12,0)*unitsquare, white, border); filldraw(p, shift(13,6)*unitsquare, opacity(0.2)+red, border); filldraw(p, shift(13,5)*unitsquare, opacity(0.2)+red, border); filldraw(p, shift(13,4)*unitsquare, opacity(0.2)+lightgreen, border); filldraw(p, shift(13,3)*unitsquare, opacity(0.2)+lightgreen, border); filldraw(p, shift(13,2)*unitsquare, opacity(0.2)+lightgreen, border); filldraw(p, shift(13,1)*unitsquare, opacity(0.2)+lightcyan, border); filldraw(p, shift(13,0)*unitsquare, opacity(0.2)+lightcyan, border); filldraw(p, shift(14,6)*unitsquare, opacity(0.2)+red, border); filldraw(p, shift(14,5)*unitsquare, opacity(0.2)+red, border); filldraw(p, shift(14,4)*unitsquare, opacity(0.2)+lightgreen, border); filldraw(p, shift(14,3)*unitsquare, opacity(0.2)+lightgreen, border); filldraw(p, shift(14,2)*unitsquare, opacity(0.2)+lightcyan, border); filldraw(p, shift(14,1)*unitsquare, opacity(0.2)+lightcyan, border); filldraw(p, shift(14,0)*unitsquare, opacity(0.2)+lightcyan, border); add(shift(0,0)*p); picture q; filldraw(q, shift(0,1)*unitsquare, lightgreen, border); filldraw(q, shift(0,0)*unitsquare, lightgreen, border); filldraw(q, shift(1,1)*unitsquare, lightgreen, border); filldraw(q, shift(1,0)*unitsquare, lightgreen, border); filldraw(q, shift(2,1)*unitsquare, lightgreen, border); filldraw(q, shift(2,0)*unitsquare, pink, border); filldraw(q, shift(3,1)*unitsquare, pink, border); filldraw(q, shift(3,0)*unitsquare, pink, border); filldraw(q, shift(4,1)*unitsquare, pink, border); filldraw(q, shift(4,0)*unitsquare, pink, border); add(shift(20,2)*q); [/asy][/asy] If $\min(m,n) \in \{2,4,6 \}$, WLOG $m \in \{2,4,6 \}$. Since $5 \mid mn$, we have $5 \mid n$, hence it can be divided into several $2 \times 5$ grids. If $\min(m,n)=5$, WLOG $m=5$, then $n$ must be an even integer, hence it can be divided into several $2 \times 5$ grids. If $\min(m,n) \ge 7$, since $5 \mid mn$, WLOG $5 \mid m$. Case a. If $10 \mid m$ and $n$ is even, it can be divided into several $2 \times 5$ grid. Case b. If $10 \mid m$ and $n$ is odd, it can be divided into $m \times 5$ grid and $m \times (n-5) $ grid, both of them can be divided into several $2 \times 5$ grids. Case c. If $10 \mid m+5$, then $m \ge 15$, it can be divided into $(m-15) \times n$ grid and $15 \times n$ grid. The former is tiled in Case a or Case b. If $n$ is even, the latter can be further divided into several $2 \times 5$ grid. If $n$ is odd, the latter can be further divided into $15 \times 7$ grid and $15 \times (n-7)$ grid, where the former is shown at the beginning, the latter can be divided into several $2 \times 5$ grid.