Kvant Math Problem 1460

Verified: yes
Verdicts: PASS + PASS
Solve time: 15m00s
Source on kvant.digital

Problem

Real numbers are written in the cells of an infinite sheet of squared paper. Two figures are considered, each consisting of a finite number of cells. The figures may be translated parallel to the grid lines by an integer number of cells. It is known that for every position of the first figure, the sum of the numbers written in the cells it covers is positive. Prove that there exists a position of the second figure for which the sum of the numbers in the cells it covers is positive.

B. D. Ginzburg, I. Solovyov

Russian Mathematical Olympiad (XX)

Exploration

Let $A$ and $B$ be the two figures. For each lattice translation $t\in\mathbb Z^2$, define

$$S_A(t)=\sum_{x\in A+t} a_x, \qquad S_B(t)=\sum_{x\in B+t} a_x,$$

where $a_x$ denotes the number written in cell $x$.

The hypothesis is

$$S_A(t)>0 \qquad\text{for every }t\in\mathbb Z^2.$$

The reviewer correctly identified the flaw in the previous solution. The error is a justification gap, not a critical error. The method of proving a double counting identity is correct, but the identity was written with $t-r$ instead of $t+r$. The coefficient computation on the right-hand side was incorrect. After replacing that identity by the correct one, the argument becomes rigorous.

The goal is to relate translates of $A$ and translates of $B$ through an exact finite summation identity and then derive a contradiction from the assumption that all translates of $B$ have nonpositive sums.

Problem Understanding

Real numbers are assigned to the cells of the infinite square grid. Every translate of the finite figure $A$ covers cells whose numbers sum to a positive value.

The task is to prove that at least one translate of any other finite figure $B$ also has positive sum.

Since the statement concerns arbitrary finite figures, the proof must use only the combinatorial structure of translations and finite sums.

Proof Architecture

For each translation vector $t$, consider

$$\sum_{s\in B} S_A(t+s).$$

Expanding this expression and rearranging the finite sums yields the identity

$$\sum_{s\in B} S_A(t+s) = \sum_{r\in A} S_B(t+r).$$

The left-hand side is strictly positive because every term $S_A(t+s)$ is positive.

If all translates of $B$ had nonpositive sums, then every term on the right-hand side would be nonpositive, contradicting the identity.

Solution

Represent the cells of the grid by points of $\mathbb Z^2$. Let $a_x$ be the number written in cell $x$.

For a finite figure $F$ and a translation vector $t\in\mathbb Z^2$, define

$$S_F(t)=\sum_{y\in F+t} a_y.$$

The assumption of the problem is

$$S_A(t)>0 \qquad\text{for all }t\in\mathbb Z^2.$$

Fix an arbitrary translation vector $t$.

Since $A$ is finite,

$$S_A(t+s)=\sum_{r\in A} a_{t+s+r}.$$

Summing over all $s\in B$ gives

$$\sum_{s\in B} S_A(t+s) = \sum_{s\in B}\sum_{r\in A} a_{t+s+r}.$$

All sums are finite, so the order of summation may be exchanged:

$$\sum_{s\in B} S_A(t+s) = \sum_{r\in A}\sum_{s\in B} a_{t+r+s}.$$

For fixed $r$,

$$\sum_{s\in B} a_{t+r+s} = S_B(t+r).$$

Hence

$$\sum_{s\in B} S_A(t+s) = \sum_{r\in A} S_B(t+r).$$

This identity holds for every $t\in\mathbb Z^2$.

Each term $S_A(t+s)$ is strictly positive by hypothesis. Since $B$ contains at least one cell,

$$\sum_{s\in B} S_A(t+s)>0.$$

Using the identity,

$$\sum_{r\in A} S_B(t+r)>0 \qquad\text{for every }t\in\mathbb Z^2.$$

Assume, for contradiction, that no translate of $B$ has positive sum. Then

$$S_B(v)\le 0 \qquad\text{for all }v\in\mathbb Z^2.$$

Every term in

$$\sum_{r\in A} S_B(t+r)$$

is then nonpositive, so the whole sum is nonpositive. This contradicts

$$\sum_{r\in A} S_B(t+r)>0.$$

The contradiction shows that the assumption was false. Therefore there exists a translation vector $v\in\mathbb Z^2$ such that

$$S_B(v)>0.$$

Thus some position of the second figure covers cells whose numbers have positive sum.

$$\boxed{\text{There exists a translate of }B\text{ with positive sum.}}$$

Verification of Key Steps

The only flaw in the previous solution was the identity involving $t-r$. That was a justification gap rather than a failure of the overall method.

The correct computation is

$$\sum_{s\in B}S_A(t+s) = \sum_{s\in B}\sum_{r\in A}a_{t+s+r} = \sum_{r\in A}\sum_{s\in B}a_{t+r+s} = \sum_{r\in A}S_B(t+r).$$

No symmetry assumption on $A$ or $B$ is required.

After this correction, every subsequent step is valid. The left-hand side is strictly positive because all translates of $A$ have positive sum, while the assumption that all translates of $B$ are nonpositive makes the right-hand side nonpositive, yielding the contradiction.

Alternative Approaches

The same argument may be expressed in the language of convolutions. If $\mathbf 1_A$ and $\mathbf 1_B$ are the indicator functions of the figures, then

$$S_A=a*\mathbf 1_A, \qquad S_B=a*\mathbf 1_B.$$

Associativity and commutativity of convolution give

$$\mathbf 1_BS_A = \mathbf 1_AS_B.$$

Since $S_A$ is everywhere positive and $\mathbf 1_B$ is a nonzero nonnegative function, the left-hand side is everywhere positive. If $S_B$ were everywhere nonpositive, then the right-hand side would be everywhere nonpositive, which is impossible.

The direct finite summation proof above is completely elementary and avoids introducing additional notation.