Track / Stage 6 / 13 of 400 #1013 of 1964

Problem 1013

National Olympiad, first round

Combinatorics Difficulty 6.0 Prove it Ukrainian National Mathematical Olympiad · Ukraine

Given a foundation that is in form of a square $4 \times 4$ , that is divided into smaller $1 \times 1$ squares. There is a gap of length $1$ between any two adjacent squares. The foundation is covered with several layers of bricks of size $2 \times 1$ . Every layer consists of $8$ bricks and each brick fully covers exactly one gap of length $1$ . Such cover is called strong, if every gap is covered by a brick at least in one of the layers. What is the minimum amount of layers that make a strong cover?
(Bogdan Rublyov)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Consider a square $A$ of size $1 \times 1$ , that does not touch the borders of $4 \times 4$ . All $4$ sides of it have to be covered by bricks. Moreover, these bricks have to be different for different

Fig. 16
sides, since one half of each brick covers the square $A$ . Thus, there have to be at least $4$ layers in order for cover to be strong. It suffices to show that it is possible to have a strong cover with $4$ layers (Fig. 16).

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.