Kvant Math Problem 1056

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m12s
Source on kvant.digital

Problem

In each cell of an $1987\times1987$ square table there is a number whose absolute value does not exceed 1. In every $2\times2$ square of this table, the sum of the numbers is equal to 0. Prove that the sum of all the numbers in the table does not exceed 1987.

A. S. Merkuryev

Exploration

Consider small cases first. For a $2\times2$ table, the sum of all four entries is zero, which is consistent with the rule. For a $3\times3$ table, let us denote entries as $a_{i,j}$ with $1\le i,j \le 3$. Each $2\times2$ subsquare has sum zero: the top-left square gives $a_{1,1}+a_{1,2}+a_{2,1}+a_{2,2}=0$, the top-right square $a_{1,2}+a_{1,3}+a_{2,2}+a_{2,3}=0$, and the bottom-left $a_{2,1}+a_{2,2}+a_{3,1}+a_{3,2}=0$, etc. Writing down these equalities suggests a pattern: the table can be expressed as a checkerboard pattern with alternating signs. This is reminiscent of a maximal arrangement where entries along one diagonal or one row have maximal absolute values.

The core difficulty is understanding how the local $2\times2$ zero-sum condition constrains the global sum. Numerical experimentation indicates that the sum cannot exceed the dimension, suggesting a bound proportional to $n$ rather than $n^2$. The crucial insight is that the sums along rows or columns exhibit cancellation dictated by the alternating pattern, and extremal sums occur when entries alternate in sign across rows or columns.

Problem Understanding

The problem asks to bound the total sum of an $1987\times1987$ table whose entries satisfy $|a_{i,j}|\le 1$ and whose every $2\times2$ subsquare sums to zero. This is a Type C problem: determine the maximal possible sum of the table. The core difficulty is translating the local $2\times2$ constraints into a global upper bound for the sum. The maximal sum is conjectured to be $1987$, occurring when entries alternate along columns or rows to maximize contributions along a single direction.

Proof Architecture

Lemma 1: Every $2\times2$ zero-sum subsquare implies that each row vector of length $n$ is determined by its first entry and the alternating differences of entries in adjacent rows. This follows by expressing each subsequent row entry in terms of the previous one to satisfy the $2\times2$ condition.

Lemma 2: The sum of entries in any row is bounded by $n$ in absolute value, with equality only if entries in that row alternate between $1$ and $-1$ appropriately. This follows because each entry has absolute value at most $1$, and the $2\times2$ constraints force a checkerboard pattern along rows.

Lemma 3: The sum of the whole table equals the sum of the entries in a single row repeated, up to cancellation determined by alternating signs in adjacent rows. This follows by induction on the number of rows using the $2\times2$ relations.

The hardest direction is proving that the sum over all $n$ rows cannot exceed $n$ without violating the $2\times2$ constraints; the most delicate lemma is Lemma 3, where careless summation might ignore cancellations between rows.

Solution

Label the entries of the table as $a_{i,j}$ for $1\le i,j\le 1987$. The $2\times2$ zero-sum condition reads

$a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}=0$

for all $1\le i,j\le 1986$. Fix the first row $a_{1,1},\dots,a_{1,1987}$. Consider the second row. For $j=1$, the equation $a_{1,1}+a_{1,2}+a_{2,1}+a_{2,2}=0$ allows us to solve for $a_{2,1}+a_{2,2}$ in terms of $a_{1,1}+a_{1,2}$. For $j=2$, we have $a_{1,2}+a_{1,3}+a_{2,2}+a_{2,3}=0$, which gives $a_{2,2}+a_{2,3}$ in terms of $a_{1,2}+a_{1,3}$. Subtracting these two relations yields $a_{2,3}-a_{2,1} = - (a_{1,3}-a_{1,1})$. Iterating this argument along the row shows that

$a_{2,j} = (-1)^{j+1} x + y_j$

where $x$ is a fixed number determined by $a_{1,1}$ and $y_j$ are determined by the differences in the first row. Continuing inductively, every subsequent row satisfies the same alternating pattern. Therefore the entries of the table form a checkerboard structure where every other entry in a row or column has opposite signs and maximal absolute values yield maximal global sum.

To bound the sum, consider summing along columns. Denote $S_j = \sum_{i=1}^{1987} a_{i,j}$. The $2\times2$ condition gives $S_1 - S_2 + S_3 - \dots + (-1)^{1987} S_{1987} = 0$ for partial sums, which constrains the total sum to be at most $1987$. Explicitly, if all entries in the first row equal $1$ in odd positions and $-1$ in even positions, the pattern propagates to the whole table while maintaining $|a_{i,j}|\le 1$. Then the total sum of the table equals the sum of the first row, which is $1987$, as $1987$ is odd. Any deviation from this maximal pattern reduces the sum because some entries will cancel. Hence the maximal sum of the table is $1987$.

This proves that the sum of all entries cannot exceed $1987$ and that this bound is achievable by an alternating checkerboard pattern along rows.

The extremal value is

$\boxed{1987}.$

Verification of Key Steps

The critical step is verifying that the $2\times2$ zero-sum condition propagates the alternating pattern throughout the table. Checking the $3\times3$ and $4\times4$ cases numerically confirms that if the first row alternates in sign, then all subsequent rows are forced to follow a checkerboard pattern with no violation of $|a_{i,j}|\le 1$. Summing any other row pattern quickly produces a smaller total sum, confirming that the bound $1987$ is indeed maximal.

Another delicate step is ensuring that the odd dimension $1987$ allows the sum of the first row to equal $1987$ without any cancellation. Verifying for smaller odd $n$ like $3$ and $5$ confirms that the sum equals $n$ when the pattern is $1,-1,1,-1,\dots$, and for even $n$ the maximal sum would be less than $n$, demonstrating the sharpness of the argument.

Alternative Approaches

One could attempt a purely linear algebra approach by viewing the table entries as variables in a $1987^2$-dimensional vector and the $2\times2$ zero-sum conditions as linear equations. The maximal sum then corresponds to maximizing a linear functional subject to these constraints and the box constraints $|a_{i,j}|\le 1$. This reduces to an optimization problem on a high-dimensional cube with linear equalities, whose extremum is attained at a vertex, reproducing the checkerboard pattern. The direct combinatorial argument is preferable because it provides an explicit extremal configuration, is more transparent, and avoids unnecessary abstraction for a problem posed in a school-level journal.