Find all pairs of positive integers \((a,b)\) with the following property: there exists an integer \(N\) such that for any integers \(m\ge N\) and \(n\ge N\), every \(m\times n\) grid of unit squares may be partitioned into \(a\times b\) rectangles and fewer than \(ab\) unit squares. Proposed by Holden Mui
Problem
Source: ELMO Shortlist 2023 C3
Tags: Elmo, combinatorics
30.06.2023 14:33
Is rotation allowed, namely $b\times a$ rectangles as well?
30.06.2023 15:11
I am pretty sure this is allowed.
02.07.2023 01:05
The solution set is $\boxed{\{(1, 1), (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)\}}$. Constructions The constructions for $1 \times 1$ rectangles and $1 \times 2$ rectangles are obvious. For $1 \times 3$ rectangles, a construction for $(m+3, n+3)$ can be obtained from a construction for $(m, n)$ as shown below: [asy][asy] size(100); draw((0, 0) -- (0, 8) -- (9, 8) -- (9, 0) -- cycle); draw((6, 0) -- (6, 5) -- (0, 5)); for (int i = 3; i < 9; ++i) { draw((i, 5) -- (i, 8)); } for (int i = 2; i <= 5; ++i) { draw((6, i) -- (9, i)); } label("$\ldots$", (1.5, 1.5) + (0, 5)); label("$\vdots$", (1.5, 1) + (6, 0)); [/asy][/asy] so it suffices to give constructions for $(1, 1)$, $(1, 2)$, and $(5, 5)$, by induction. The first two cases are vacuous, and a $5 \times 5$ grid can be tiled as shown below. [asy][asy] size(100); draw((0, 0) -- (0, 5) -- (5, 5) -- (5, 0) -- cycle); draw((0, 2) -- (3, 2)); draw((0, 1) -- (3, 1)); draw((3, 0) -- (3, 3)); draw((4, 0) -- (4, 3)); draw((2, 3) -- (5, 3)); draw((2, 4) -- (5, 4)); draw((2, 2) -- (2, 5)); draw((1, 2) -- (1, 5)); [/asy][/asy] Lastly, for $2 \times 3$ rectangles, a construction for $(m+6, n+6)$ can be obtained from $(m, n)$ for $m, n \geq 2$ using a method similar to the $1 \times 3$ case, since any $k \times 6$ rectangle can be tiled with $2 \times 3$ rectangles for $k \geq 2$, by writing $k$ as the sum of a multiple of 2 and a multiple of 3. Hence, it suffices to give constructions for all pairs $(m, n) \in \{2, 3, 4, 5, 6, 7\}^2$, which is given below. [asy][asy] size(400); for (int i = 2; i < 8; ++i) { for (int j = 2; j < 8; ++j) { path[] p; if (i == 2 && j == 2) { p = (0, 1) -- (2, 1) ^^ (1, 0) -- (1, 2); } else if (i == 2 && j == 3) { p = (0, 0) -- (0, 0) ^^ (0, 0) -- (0, 0); } else if (i == 2 && j == 4) { p = (3, 0) -- (3, 2) ^^ (3, 1) -- (4, 1); } else if (i == 2 && j == 5) { p = (3, 0) -- (3, 2) ^^ (3, 1) -- (5, 1) ^^ (4, 0) -- (4, 2); } else if (i == 2 && j == 6) { p = (3, 0) -- (3, 2) ^^ (3, 0) -- (3, 0); } else if (i == 2 && j == 7) { p = (3, 0) -- (3, 2) ^^ (6, 0) -- (6, 2) ^^ (6, 1) -- (7, 1); } else if (i == 3 && j == 2) { p = (0, 0) -- (0, 0) ^^ (0, 0) -- (0, 0); } else if (i == 3 && j == 3) { p = (0, 2) -- (3, 2) ^^ (1, 2) -- (1, 3) ^^ (2, 2) -- (2, 3); } else if (i == 3 && j == 4) { p = (2, 0) -- (2, 3) ^^ (0, 0) -- (0, 0); } else if (i == 3 && j == 5) { p = (2, 0) -- (2, 3) ^^ (4, 0) -- (4, 3) ^^ (4, 1) -- (5, 1) ^^ (4, 2) -- (5, 2); } else if (i == 3 && j == 6) { p = (2, 0) -- (2, 3) ^^ (4, 0) -- (4, 3); } else if (i == 3 && j == 7) { p = (2, 0) -- (2, 3) ^^ (4, 0) -- (4, 3) ^^ (6, 0) -- (6, 3) ^^ (6, 1) -- (7, 1) ^^ (6, 2) -- (7, 2); } else if (i == 4 && j == 2) { p = (0, 3) -- (2, 3) ^^ (1, 3) -- (1, 4); } else if (i == 4 && j == 3) { p = (0, 2) -- (3, 2) ^^ (0, 0) -- (0, 0); } else if (i == 4 && j == 4) { p = (2, 0) -- (2, 4) ^^ (0, 3) -- (4, 3) ^^ (1, 3) -- (1, 4) ^^ (3, 3) -- (3, 4); } else if (i == 4 && j == 5) { p = (0, 2) -- (3, 2) ^^ (3, 0) -- (3, 4) ^^ (3, 3) -- (5, 3) ^^ (4, 3) -- (4, 4); } else if (i == 4 && j == 6) { p = (3, 0) -- (3, 4) ^^ (0, 2) -- (6, 2); } else if (i == 4 && j == 7) { p = (3, 0) -- (3, 4) ^^ (0, 2) -- (6, 2) ^^ (6, 0) -- (6, 4) ^^ (6, 1) -- (7, 1) ^^ (6, 2) -- (7, 2) ^^ (6, 3) -- (7, 3); } else if (i == 5 && j == 2) { p = (0, 3) -- (2, 3) ^^ (0, 4) -- (2, 4) ^^ (1, 3) -- (1, 5); } else if (i == 5 && j == 3) { p = (0, 2) -- (3, 2) ^^ (0, 4) -- (3, 4) ^^ (1, 4) -- (1, 5) ^^ (2, 4) -- (2, 5); } else if (i == 5 && j == 4) { p = (2, 0) -- (2, 3) ^^ (0, 3) -- (4, 3) ^^ (3, 3) -- (3, 5) ^^ (3, 4) -- (4, 4); } else if (i == 5 && j == 5) { p = (0, 2) -- (3, 2) ^^ (3, 0) -- (3, 3) ^^ (2, 3) -- (5, 3) ^^ (2, 2) -- (2, 5); } else if (i == 5 && j == 6) { p = (3, 0) -- (3, 2) ^^ (0, 2) -- (6, 2) ^^ (2, 2) -- (2, 5) ^^ (4, 2) -- (4, 5); } else if (i == 5 && j == 7) { p = (3, 0) -- (3, 2) ^^ (0, 2) -- (6, 2) ^^ (2, 2) -- (2, 5) ^^ (4, 2) -- (4, 5) ^^ (6, 0) -- (6, 5) ^^ (6, 1) -- (7, 1) ^^ (6, 2) -- (7, 2) ^^ (6, 3) -- (7, 3) ^^ (6, 4) -- (7, 4); } else if (i == 6 && j == 2) { p = (0, 3) -- (2, 3) ^^ (0, 0) -- (0, 0); } else if (i == 6 && j == 3) { p = (0, 2) -- (3, 2) ^^ (0, 4) -- (3, 4); } else if (i == 6 && j == 4) { p = (2, 0) -- (2, 6) ^^ (0, 3) -- (4, 3); } else if (i == 6 && j == 5) { p = (2, 0) -- (2, 6) ^^ (0, 3) -- (2, 3) ^^ (2, 2) -- (5, 2) ^^ (2, 4) -- (5, 4); } else if (i == 6 && j == 6) { p = (2, 0) -- (2, 6) ^^ (4, 0) -- (4, 6) ^^ (0, 3) -- (6, 3); } else if (i == 6 && j == 7) { p = (2, 0) -- (2, 6) ^^ (4, 0) -- (4, 6) ^^ (0, 3) -- (4, 3) ^^ (4, 2) -- (7, 2) ^^ (4, 4) -- (7, 4); } else if (i == 7 && j == 2) { p = (0, 3) -- (2, 3) ^^ (0, 6) -- (2, 6) ^^ (1, 6) -- (1, 7); } else if (i == 7 && j == 3) { p = (0, 2) -- (3, 2) ^^ (0, 4) -- (3, 4) ^^ (0, 6) -- (3, 6) ^^ (1, 6) -- (1, 7) ^^ (2, 6) -- (2, 7); } else if (i == 7 && j == 4) { p = (2, 0) -- (2, 7) ^^ (0, 3) -- (4, 3) ^^ (0, 6) -- (4, 6) ^^ (1, 6) -- (1, 7) ^^ (3, 6) -- (3, 7); } else if (i == 7 && j == 5) { p = (2, 0) -- (2, 7) ^^ (0, 3) -- (2, 3) ^^ (0, 6) -- (5, 6) ^^ (2, 2) -- (5, 2) ^^ (2, 4) -- (5, 4) ^^ (1, 6) -- (1, 7) ^^ (3, 6) -- (3, 7) ^^ (4, 6) -- (4, 7); } else if (i == 7 && j == 6) { p = (3, 0) -- (3, 4) ^^ (0, 2) -- (6, 2) ^^ (0, 4) -- (6, 4) ^^ (2, 4) -- (2, 7) ^^ (4, 4) -- (4, 7); } else if (i == 7 && j == 7) { p = (0, 3) -- (4, 3) ^^ (4, 0) -- (4, 4) ^^ (3, 4) -- (7, 4) ^^ (3, 3) -- (3, 7) ^^ (2, 0) -- (2, 3) ^^ (4, 2) -- (7, 2) ^^ (5, 4) -- (5, 7) ^^ (0, 5) -- (3, 5); } else { p = circle((0, 0), 1) ^^ (0, 0) -- (1, 1); } draw(shift((j+3)*j/2, (i+3)*i/2) * (p ^^ (0, 0) -- (0, i) -- (j, i) -- (j, 0) -- cycle)); } } [/asy][/asy] Completeness of solution set To show that no other pairs $(a, b)$ work, consider the following claim. Claim. For $c, d \in \mathbb{Z}^+$ and $k \geq 4$, any tiling of an $(ck+2) \times \left(dk+\left\lceil\frac{k}{2}\right\rceil\right)$ rectangle with $1 \times k$ rectangles must leave at least $k$ cells empty. Proof Consider a $(ck+2) \times \left(dk+\left\lceil\frac{k}{2}\right\rceil\right)$ with its bottom-left cell at the origin, and label each cell with the sum of its coordinates modulo $k$. [asy][asy] size(200); for (int x = 0; x < 13; ++x) { for (int y = 0; y < 7; ++y) { if ((x+y+1) % 5 == 0) { fill((x, y) -- (x+1, y) -- (x+1, y+1) -- (x, y+1) -- cycle, lightgray); } label(string((x + y) % 5), (x + 1/2, y + 1/2)); } } draw((0, 0) -- (0, 7) -- (13, 7) -- (13, 0) -- cycle); draw((0, 5) -- (13, 5)); draw((10, 0) -- (10, 7)); [/asy][/asy] By construction, every $1 \times k$ rectangle must cover one cell whose label is $k-1$. However, when $k \geq 4$, no cell in the top-right-most $2 \times \left\lceil\frac{k}{2}\right\rceil$ rectangle can contain an $k-1$, since the top-right cell's label is \[(2-1) + \left(\left\lceil\frac{k}{2}\right\rceil-1\right) = \left\lceil\frac{k}{2}\right\rceil < k-1.\]Therefore, any tiling of $1 \times k$ rectangles must leave at least $2 \times \left\lceil\frac{k}{2}\right\rceil \geq k$ cells empty. $\blacksquare$ To show that no pairs $(a, b)$ with $\max(a, b) \geq 4$ work, assume $b \geq 4$. Since $a \times b$ rectangles can be partitioned into $a$ separate $1 \times b$ rectangles, it suffices to find values for $c$ and $d$ for which \[a \mid \underbrace{\left\lfloor\frac{(bc+2) \left(bd+\left\lceil\frac{b}{2}\right\rceil\right)}{b}\right\rfloor}_{\text{number of $1 \times b$ rectangles}} = bcd + \left\lceil\frac{b}{2} \right\rceil c + 2d + 1,\]by the claim. (For example, a $7 \times 13$ rectangle cannot contain six $3 \times 5$ rectangles since it cannot contain eighteen $1 \times 5$ rectangles.) If $b$ is even, then $a$ must be odd or else large odd-sized grids cannot be partitioned. Since \[bcd + \left\lceil\frac{b}{2} \right\rceil c + 2d + 1 = \left(\frac{b}{2} c+1\right)\left(2d+1\right),\]choosing $d = \frac{a-1}{2}$ works. If $b$ is odd, then choosing $c = k(2d+1)$ gives \[bcd + \left\lceil\frac{b}{2} \right\rceil c + 2d + 1 = (2d+1)\left(b\left(\frac{c}{2}\right)+1\right)+\frac{c}{2} = (2d+1)\frac{bk(2d+1)+3}{2}.\]Then $d$ can be chosen such that the first term contains all odd prime factors of $a$ and $k$ can be chosen so that the second term contains all even prime factors of $a$. Therefore, it suffices to check that $(2, 2)$ and $(3, 3)$ don't work. $(2, 2)$ doesn't work because each row in a partitioning of an odd-sized grid must contain a unit square, and $(3, 3)$ doesn't work for similar reasons.