A unit square is removed from the corner of an $n \times n$ grid, where $n \geq 2$. Prove that the remainder can be covered by copies of the figures of $3$ or $5$ unit squares depicted in the drawing below. [asy][asy] import geometry; draw((-1.5,0)--(-3.5,0)--(-3.5,2)--(-2.5,2)--(-2.5,1)--(-1.5,1)--cycle); draw((-3.5,1)--(-2.5,1)--(-2.5,0)); draw((0.5,0)--(0.5,3)--(1.5,3)--(1.5,1)--(3.5,1)--(3.5,0)--cycle); draw((1.5,0)--(1.5,1)); draw((2.5,0)--(2.5,1)); draw((0.5,1)--(1.5,1)); draw((0.5,2)--(1.5,2)); [/asy][/asy] Note: Every square must be covered once and figures must not go over the bounds of the grid.
Problem
Source: 2022 Nigerian MO Round 3/Problem 3
Tags: Tiling, grid, Combinatorial Number Theory, Number theoretic combinatorics
ZhuTao
03.05.2022 01:55
Maybe combinatorics. Use induction. Two 3-unit figure can make a $2\times 3$ rectangular, so $2xy$ 3-unit figure can make $2x\times 3y$ rectangular. Assume cases when $2\leq n \leq k$ have been proved. Then when $n=k+1$, try rewrite $n=2x+1+3y$. If such $(x,y)\in \mathbb{Z}_{>0}^2$ exists, $(k+1)\times(k+1)$ with a unit removed from a corner can be made as below. And when $n = 6$ or $n\geq 8$, such $(x,y)$ does exist. So we only need to prove when$n=2,3,4,5,7$. $n=2,3$ is trivial. $n=4$: $n=5$: $n=7$:
oVlad
03.05.2022 17:01
This was originally a problem from the Estonian Mathematical Olympiad 2009. It was also later on used as Problem 4 in the Junior Mathematical Danube Competition 2016. (Edit: feel free to copy the asy code from the linked post for a better diagram)
Rukevwe
09.07.2022 22:55
ZhuTao wrote:
Maybe combinatorics.
Use induction. Two 3-unit figure can make a $2\times 3$ rectangular, so $2xy$ 3-unit figure can make $2x\times 3y$ rectangular.
Assume cases when $2\leq n \leq k$ have been proved. Then when $n=k+1$, try rewrite $n=2x+1+3y$. If such $(x,y)\in \mathbb{Z}_{>0}^2$ exists, $(k+1)\times(k+1)$ with a unit removed from a corner can be made as below.
And when $n = 6$ or $n\geq 8$, such $(x,y)$ does exist. So we only need to prove when$n=2,3,4,5,7$.
$n=2,3$ is trivial.
$n=4$:
$n=5$:
$n=7$:
Beautiful solution