Browse · MathNet
PrintMongolian National Mathematical Olympiad
Mongolia algebra
Problem
A square is divided into squares. A point light at a vertex of square lights all the squares that the vertex belongs. (A point light can be positioned on a vertex on the edge of the big square). Find the minimum number of point lights required such that all the squares are lit even if one of the point lights is not functioning. (Proposed by B. Battsengel)
Solution
The minimum number of light is . Each black square needs at least lights and each figure that consist of three square needs at least lights. (See picture 1.) So we need at least lights. Picture 2 shows that lights could be placed as required.
Picture 1 Picture 2
Picture 1 Picture 2
Final answer
55
Techniques
Combinatorial optimizationColoring schemes, extremal arguments