An $n\times n$ square is divided into $n^2$ unit cells. Is it possible to cover this square with some layers of 4-cell figures of the following shape (i.e. each cell of the square must be covered with the same number of these figures) if a) $n=6$? b) $n=7$? (The sides of each figure must coincide with the sides of the cells; the figures may be rotated and turned over, but none of them can go beyond the bounds of the square.)
Problem
Source: 2014 Belarusian MO A 11.8
Tags: combinatorial geometry, combinatorics, covering
Com10atorics
26.12.2020 00:38
None of them works. a) Let us colour the square in a chessboard way with the colours black and white. See that one shape covers three cells of one colour and one of the other. Define $a$ as the number of shapes that covers $3$ black cells and $1$ white cell and $b$ as the opposite of $a$. So we must have, $(3a+b)+(3b+a)=36$ which gives $a+b=9$. But since the square has now an equal number of black and white cells we must have $a=b$. So now we have $2a=9$ which doesn't work in integers. b) $4$ doesn't divide $49$. From the solutions we see that the only squares that can be covered by this shape are those with $4|n$.
Zhumanadilbek
05.05.2024 17:56
@Com10atorics it seems like you misunderstood the question. "each cell of the square must be covered with the same number of these figures" is written there, i.e. not namely one layer .