In a grid, an integer is written in each of the cells. Let be the configuration of cells formed by removing the central cell of a grid. It is given that for any group of cells in the grid forming the configuration , the sum of the numbers written in the cells is positive. Prove that there is a grid so that the sum of the numbers in the cells is positive.
Solution
Consider the grid. Place overlapping copies of as shown (left figure), where the number indicates the cells of the copy of . The same grid is also covered by overlapping copies of grid (right), with each cell covered the same number of times. (Note that in the first figure the top left cells of the copies of form a grid while in the second figure, the top left cells of the grid form the configuration . This is important for the general case.)
| 1 | 12 | 12 | 2 |
|---|---|---|---|
| 13 | 234 | 134 | 24 |
| 13 | 124 | 123 | 24 |
| 3 | 34 | 34 | 4 |
| 1 | 12 | 23 | 3 |
|---|---|---|---|
| 14 | 124 | 235 | 35 |
| 46 | 467 | 578 | 58 |
| 6 | 67 | 78 | 8 |
Thus the sum of the sums of the numbers in the cells of the copies of is equal to that of the copies of the grid. Since the former is positive, one of the grid must be positive as well.
It is easy to see that the result holds for any two configurations , provided the grid is large enough. Choose a pair of coordinate axes. Let the number of cells in and be and respectively. Place and in some position. Let be the centres of the cells covered by and let be the centres of the cells covered by . Let be the position of after it has been translated by and let be the corresponding sum. The sum is similarly defined. It is clear that the cells, counting multiplicity, covered by when it is translated by the vectors are the same as the cells, counting multiplicity, covered by when it is translated by the vectors . Thus
Since the LHS is positive, at least one of the terms on the RHS is positive.