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
We say that a button covers a square if the button lies on either the square itself or one of its neighbors. Consider the corner areas and the central cross consisting of 5 squares (colored with green and red respectively in Fig. 17).
Every button covering a corner has to be located in the corresponding corner area, thus there is at least one button in each of them. Such a button covers exactly 3 squares in its area, meaning there exists a square in each area covered by other buttons.
If there is a button in the central square, then it covers no squares in the corner areas. One button can cover the missing squares of only 2 corner areas at once. Thus we would need at least 3 other buttons in addition to the 4 buttons located in the corner areas, meaning a total of at least 7 buttons.
If there is no button in the central square, then each button can cover at most 2 squares in the central cross, meaning at least 3 buttons needed to cover it. However, no such button can cover a corner square, meaning 4 other buttons to cover them for a total of at least 7 buttons.
One possibility for the covering of the square with 7 buttons is shown in Fig. 18.
---
Alternative solution.
Define covering like in Solution 1. Assume for contradiction that we have covered the grid with 6 buttons. Divide the grid into an edge zone and a central zone (green and red respectively in Fig. 19).
A button placed in the edge zone always covers exactly 3 consecutive edge zone squares. If it is in a corner square, then it covers no central zone squares, otherwise it covers exactly 1 central zone square. To cover the corner squares, we need at least 4 buttons in the edge zone, meaning at most 2 buttons in the central zone. The buttons located in the edge zone cover 12 edge zone squares, but there are 16 squares in total.
Fig. 19 Fig. 20
A button placed in the central zone covers at most 2 edge zone squares, but 2 is only possible if there is a single corner square between them (Fig. 20). Thus a central square button covers at most 1 edge zone square that is not already covered by the edge zone buttons. Thus, in order to cover all squares of the edge zone, we would need at least 5 buttons in it. These cover at most 15 squares in the edge zone and 5 squares in the central zone. Thus the final button has to cover at least 1 edge zone square and 4 central zone squares. This is only possible if the covered edge zone square is the middle square of a side (Fig. 21). But then the only way to place 5 buttons in the edge zone to cover 15 of its squares is to place 2 of them in the corners. But buttons placed in the corners do not cover squares in the central region, which leaves the center uncovered (Fig. 22). The contradiction shows that we need at least 7 buttons.
Fig. 21
Fig. 22
One possibility for the covering of the square with 7 buttons is shown in Fig. 18.
---
Alternative solution.
Define covering like in Solution 1. To cover the corner squares, we need at least 4 buttons located either in corner squares or in squares adjacent to them.
In a corner square, a button covers 3 squares. On the edge, but not in the corner, a button covers 4 squares and elsewhere it covers 5 squares. Consider two cases.
If there are buttons in corner squares, then the 4 buttons covering the corners cover at most squares, meaning
squares remain uncovered by them. As , this requires at least 3 more buttons for a total of at least 7.
If there is at most 1 button in a corner square, then there exists a pair of empty opposite corners (w.l.o.g., these are the upper left and lower right corner, with the button covering the upper left corner in the left-most column, as in Fig. 23). Then to cover the red square in Fig. 23, another button needs to be located on it or in the central square of the top row. Repeating the same argument for the other empty corner shows that there must be 2 buttons in both red regions in Fig. 24, alongside at least 1 button in both green regions. Thus we have a total of 6 buttons on the edge of the grid, meaning another button is necessary to cover the central square. Thus we need at least 7 buttons in total.
Fig. 23 Fig. 24
One possibility for the covering of the square with 7 buttons is shown in Fig. 18.
Every button covering a corner has to be located in the corresponding corner area, thus there is at least one button in each of them. Such a button covers exactly 3 squares in its area, meaning there exists a square in each area covered by other buttons.
If there is a button in the central square, then it covers no squares in the corner areas. One button can cover the missing squares of only 2 corner areas at once. Thus we would need at least 3 other buttons in addition to the 4 buttons located in the corner areas, meaning a total of at least 7 buttons.
If there is no button in the central square, then each button can cover at most 2 squares in the central cross, meaning at least 3 buttons needed to cover it. However, no such button can cover a corner square, meaning 4 other buttons to cover them for a total of at least 7 buttons.
One possibility for the covering of the square with 7 buttons is shown in Fig. 18.
---
Alternative solution.
Define covering like in Solution 1. Assume for contradiction that we have covered the grid with 6 buttons. Divide the grid into an edge zone and a central zone (green and red respectively in Fig. 19).
A button placed in the edge zone always covers exactly 3 consecutive edge zone squares. If it is in a corner square, then it covers no central zone squares, otherwise it covers exactly 1 central zone square. To cover the corner squares, we need at least 4 buttons in the edge zone, meaning at most 2 buttons in the central zone. The buttons located in the edge zone cover 12 edge zone squares, but there are 16 squares in total.
Fig. 19 Fig. 20
A button placed in the central zone covers at most 2 edge zone squares, but 2 is only possible if there is a single corner square between them (Fig. 20). Thus a central square button covers at most 1 edge zone square that is not already covered by the edge zone buttons. Thus, in order to cover all squares of the edge zone, we would need at least 5 buttons in it. These cover at most 15 squares in the edge zone and 5 squares in the central zone. Thus the final button has to cover at least 1 edge zone square and 4 central zone squares. This is only possible if the covered edge zone square is the middle square of a side (Fig. 21). But then the only way to place 5 buttons in the edge zone to cover 15 of its squares is to place 2 of them in the corners. But buttons placed in the corners do not cover squares in the central region, which leaves the center uncovered (Fig. 22). The contradiction shows that we need at least 7 buttons.
Fig. 21
Fig. 22
One possibility for the covering of the square with 7 buttons is shown in Fig. 18.
---
Alternative solution.
Define covering like in Solution 1. To cover the corner squares, we need at least 4 buttons located either in corner squares or in squares adjacent to them.
In a corner square, a button covers 3 squares. On the edge, but not in the corner, a button covers 4 squares and elsewhere it covers 5 squares. Consider two cases.
If there are buttons in corner squares, then the 4 buttons covering the corners cover at most squares, meaning
squares remain uncovered by them. As , this requires at least 3 more buttons for a total of at least 7.
If there is at most 1 button in a corner square, then there exists a pair of empty opposite corners (w.l.o.g., these are the upper left and lower right corner, with the button covering the upper left corner in the left-most column, as in Fig. 23). Then to cover the red square in Fig. 23, another button needs to be located on it or in the central square of the top row. Repeating the same argument for the other empty corner shows that there must be 2 buttons in both red regions in Fig. 24, alongside at least 1 button in both green regions. Thus we have a total of 6 buttons on the edge of the grid, meaning another button is necessary to cover the central square. Thus we need at least 7 buttons in total.
Fig. 23 Fig. 24
One possibility for the covering of the square with 7 buttons is shown in Fig. 18.
Final answer
7
Techniques
Coloring schemes, extremal arguments