Browse · MathNet
PrintEstonian Mathematical Olympiad
Estonia counting and probability
Problem
Find the least number of buttons that can be placed on the squares of a grid so that no two buttons are on the same square or on squares with a common side (buttons may be on squares with a common vertex) and no buttons can be added to the grid under the same conditions.
Solution
If there are 3 or fewer buttons placed, then it is always possible to add more, as each button blocks up to 5 squares: the square it is in and its 4 neighbors. Thus 3 buttons cover up to of the squares of the grid, meaning that a button can be placed in at least one of the squares. It remains to observe that by placing 4 buttons as shown in Fig. 2, no more buttons can be added.
---
Alternative solution.
We say that a button covers a square if the button lies on either the square itself or one of its neighbors. Observe that one button can cover at most one of the 4 corner squares of the grid, meaning that at least 4 buttons are needed to cover the grid. To show that 4 buttons are sufficient, we can use the same placement as in Solution 1.
---
Alternative solution.
We say that a button covers a square if the button lies on either the square itself or one of its neighbors. Observe that one button can cover at most one of the 4 corner squares of the grid, meaning that at least 4 buttons are needed to cover the grid. To show that 4 buttons are sufficient, we can use the same placement as in Solution 1.
Final answer
4
Techniques
Coloring schemes, extremal arguments