Browse · MathNet
Print58th Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
Given a foundation that is in a form of a square, 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 two gaps of length . Such covering is called strong, if every gap is covered by a brick at least in one of the layers. Determine the minimum amount of layers required for a strong covering. (Bogdan Rublyov)
Solution
By contradiction, suppose cover can have three layers. Consider a grey square and four marked gaps as in Fig. 26. Each gap can be covered only by a brick that will also cover a grey square. Any such brick can't cover two of the marked gaps simultaneously. Thus, the grey square has to be covered by at least four bricks. Therefore, is the least possible amount of layers for a strong cover.
It suffices to find an example for four layers, that is shown in Fig. 27.
It suffices to find an example for four layers, that is shown in Fig. 27.
Final answer
4
Techniques
Pigeonhole principleColoring schemes, extremal arguments