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.
Solutions — 2
Solution 1
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.
Solution 2
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.
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.