Browse · MathNet
Print58th Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
Given a foundation that is in a form of a rectangle that is divided into smaller squares. There is a gap of length between any two adjacent squares. The foundation is covered by several layers of bricks of size . Every layer consists of bricks and each brick fully covers exactly one gap of length . 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)
Solution
Without loss of generality let . Consider a square of size , that does not touch the sides of a big rectangle. All 4 sides of it have to be covered with different bricks, since half of each brick covers the square itself. Therefore, covering with less than 4 layers is not possible. It suffices to show that covering with 4 layers is possible (Fig. 19). First two layers are shown on the picture, the other two layers are given by dividing rectangle on squares. Then two different options of dividing such squares into bricks give two layers as in Fig. 19.
Clearly, in case of it suffices to have 2 layers.
If covering with 3 layers exists. Example is shown in Fig. 20. Covering with less layers is not possible, since for those squares whose vertices does not coincide with a vertices of a big rectangle, 3 sides have to be covered, that is possible only with at least three layers.
Clearly, in case of it suffices to have 2 layers.
If covering with 3 layers exists. Example is shown in Fig. 20. Covering with less layers is not possible, since for those squares whose vertices does not coincide with a vertices of a big rectangle, 3 sides have to be covered, that is possible only with at least three layers.
Final answer
Minimum number of layers = 2 if m = n = 1; 3 if exactly one of m, n equals 1 and the other is greater than 1; 4 otherwise.
Techniques
Matchings, Marriage Lemma, Tutte's theoremColoring schemes, extremal arguments