Maths Olympiad Prep

Library / /7 of 12

Algebra Difficulty 5.8 AIME, harder Prove it Mongolia

A 10×1010 \times 10 square is divided into 1×11 \times 1 squares. A *point light* at a vertex of 1×11 \times 1 square lights all the 1×11 \times 1 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 5555.
Each 1×11 \times 1 black square needs at least 22 lights and each figure that consist of three 1×11 \times 1 square needs at least 33 lights. (See picture 1.) So we need at least 2×20+3×5=552 \times 20 + 3 \times 5 = 55 lights.
Picture 2 shows that 5555 lights could be placed as required.

Figure 1
Picture 1
Figure 2
Picture 2

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.