Fill up each square of a $50$ by $50$ grid with an integer. Let $G$ be the configuration of $8$ squares obtained by taking a $3$ by $3$ grid and removing the central square. Given that for any such $G$ in the $50$ by $50$ grid, the sum of integers in its squares is positive, show there exist a $2$ by $2$ square such that the sum of its entries is also positive.
Problem
Source: Singapore Mathematical Olympiad 2014 Problem 4
Tags: combinatorics proposed, combinatorics
chaotic_iak
05.07.2014 12:41
Suppose the sum of the entries in any 2x2 square is negative. Observe the upper-left 4x4 square. A B C D E F G H I J K L M N O P Since the sum of each "donut" is positive, we can sum over them: $(A+B+C+G+K+J+I+E) + (B+C+D+H+L+K+J+F) +$ $(E+F+G+K+O+N+M+I) + (F+G+H+L+P+O+N+J) > 0$ $(A+D+M+P) + 2(B+C+E+H+I+L+N+O) + 3(F+G+J+K) > 0$ On the other hand, we can apply the same thing to each "box" except the center one: $(A+B+F+E) + (B+C+G+F) + (C+D+H+G) + (E+F+J+I) +$ $(G+H+L+K) + (I+J+N+M) + (J+K+O+N) + (K+L+P+O) < 0$ $(A+D+M+P) + 2(B+C+E+H+I+L+N+O) + 3(F+G+J+K) < 0$ Clearly a contradiction. Thus there exists a 2x2 square whose sum of entries is positive.
quangminh1173
02.09.2020 08:15
The result still holds for any two configuration $G_1, G_2$, provided the grid is large enough. Choose a pair of coordinate axes. Let the number of cells in $G_1$ and $G_2$ be $m$ and $n$ respectively. Place $G_1$ and $G_2$ in some position. Let $a_1,...,a_m$ be the centres of the cells covered by $G_1$ and $b_1,...,b_n$ be centres of the cells covered by $G_2.$ Let $G_1(b_i)$ be the position of $G_1$ after it has been translated by $b_i$ and let $P_1(b_i)$ be the corresponding sum. The sum $P_2(a_i)$ is similarly defined. It is clear that, counting multiplicity, the cells covered by $G_1$ when it is translated by the vectors $b_1,...,b_n$ are the same as the cells covered by $G_2$ when it is translated by vectors $a_1,...,a_m.$ Thus
$$\sum P_1(b_i)=\sum P_2(a_j).$$Since the LHS is positive, so is at least one of the term on the RHS.