2020 INMO Problems/Problem 6


A stromino is a $3 \times 1$ rectangle. Show that a $5 \times 5$ board divided into twenty-five $1 \times 1$ squares cannot be covered by $16$ strominos such that each stromino covers exactly three squares of the board, and every square is covered by one or two strominos. (A stromino can be placed either horizontally or vertically on the board.)


At first of all let assigne a $5\times 5$ matrix with $a_{ij} = (i+j)$.

Now notice that $\sum_{i=1} ^ 5 \sum_{j=1}^5  a_{ij} \equiv 0 \pmod{3}$.

Now notice that , For each trominoes sum of the numbers that it cover is $0$ modulo $3$.

Now let's assume that there are are$x$ unit square covered exactly once and $25-x$ unit square covered twice . So, $x+2(25-x) =16\times 3=48$.

So there are only $2$ unit square coverd exactly once.

Let assume that $a_{xy}$ and $a_{zw}$ are the unit squares that covered exactly once.

Since, I have assume that the colouring is possible that's why

, $2(\sum_{i=1} ^ 5 \sum_{j=1}^5  a_{ij})-a_{xy} -a_{zw} \equiv 0 \pmod{3}$.

\[\implies (x+y)\equiv 2(z+w) \pmod{3} \cdots (1)\]

again assign another kind of coloring , $a_{ij} = (i-j)$.

In this case we also get, $2(\sum_{i=1} ^ 5 \sum_{j=1}^5  a_{ij})-a_{xy} -a_{zw} \equiv 0 \pmod{3}$.

\[\implies x-y\equiv 2(z-w) \pmod{3}\cdots (2)\].

From equation (1 )and (2) we should get, \[x\equiv 2z \implies x+z \equiv 0 \pmod{3}\].

\[\implies  x+z \equiv  y+w \equiv 0 \pmod{3}\].

Similarly we have $x-z \equiv y-w \equiv 0\pmod{3}$.

So , only possibility is $x=y=z=w=3$.

So there will exactly one unit square covered exactly once.

Contradiction ! And we are done. ~ftheftics

Invalid username
Login to AoPS