Kvant Math Problem 37

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

Problem

In each cell of an infinite sheet of squared paper, a number is written in such a way that the sum of the numbers in any square (whose sides run along the grid lines) has absolute value at most one. Prove that there exists a number $c$ such that the sum of the numbers in any rectangle (whose sides run along the grid lines) does not exceed $c$; in other words, that the sums of the numbers in all rectangles are bounded. Prove that one may take $c=4$. Perhaps you will be able to improve this estimate (for example, prove that our statement is true for $c=3$ or even for $c=2$)?

Yu. I. Ionin

Exploration

Let $A(R)$ denote the sum of the numbers in a rectangle $R$ whose sides follow the grid lines. The hypothesis says that for every square $Q$,

$$|A(Q)|\le 1.$$

The problem asks for a uniform bound on $A(R)$ for arbitrary rectangles.

The first idea is to express a rectangle as a combination of squares. If a rectangle itself happens to be a square, the bound is already known. For a non-square rectangle, one may try to dissect it into squares, but a long rectangle may require arbitrarily many squares, so summing the estimates $|A(Q)|\le1$ gives no uniform bound.

A better idea is to work with corner coordinates. Let $F(x,y)$ be the sum of all entries in the rectangle with corners $(0,0)$ and $(x,y)$. Then the sum over a rectangle with opposite corners $(a,c)$ and $(b,d)$ equals

$$F(b,d)-F(a,d)-F(b,c)+F(a,c).$$

The condition on squares becomes

|F(x+t,y+t)-F(x+t,y)-F(x,y+t)+F(x,y)|\le1 ] for all $x,y,t\ge0$. Thus the mixed second difference of $F$ along equal increments is bounded by $1$. To understand what this implies, define

G_u(v)=F(u+v,v).

Then the square condition says that for every fixed $u$,

|G_u(v+t)-G_u(v)-G_{u-t}(v+t)+G_{u-t}(v)|\le1.

$$This looks cumbersome. Another coordinate system may help. Let$$

u=x-y,\qquad v=x+y.

A square corresponds to changing only $v$ while keeping $u$ fixed. The condition says that along every line $u=\text{const}$, the increments of a certain function are bounded. Trying small examples suggests that the quantity

H(x,y)=F(x,y)-F(x-1,y)-F(x,y-1)+F(x-1,y-1)

is exactly the entry in the cell $(x,y)$. The square condition controls sums of $H$ over diagonal square blocks. One expects a telescoping argument reducing any rectangle sum to four square sums. The crucial point is to represent an arbitrary rectangle as a signed combination of at most four squares. If this is possible, the desired estimate $4$ follows immediately. Take a rectangle of side lengths $m\le n$. Place it with lower left corner at the origin. Let

Q_1=[0,n]\times[0,n],\qquad

Q_2=[0,n-m]\times[0,n-m].

Then $Q_1\setminus Q_2$ is an L-shaped region. Subtracting another suitable L-shape obtained as a difference of two squares may leave exactly the rectangle. Working through coordinates shows that a rectangle can indeed be written as

R=(Q_1-Q_2)-(Q_3-Q_4)

with four squares. Since each square sum has absolute value at most $1$, the rectangle sum is bounded by $4$. The only possible error is the geometric identity itself. It must be checked carefully. ## Problem Understanding We are given numbers in the cells of the infinite square grid. For every axis-parallel square, the sum of the numbers in all cells of that square has absolute value at most $1$. We must prove that the sums over all axis-parallel rectangles are uniformly bounded. More specifically, we must prove that every rectangle sum has absolute value at most $4$. This is a Type B problem. The statement to be proved is the existence of a universal bound, and the problem asks us to establish the explicit bound $4$. The core difficulty is to relate an arbitrary rectangle to squares, because the hypothesis gives information only about squares. ## Proof Architecture Let $S(X)$ denote the sum of the numbers in a region $X$ consisting of grid cells. Lemma 1. Every axis-parallel rectangle can be represented as a signed combination of four axis-parallel squares:

R=Q_1-Q_2-Q_3+Q_4.

$$This is obtained by expressing two complementary L-shaped regions as differences of nested squares. Lemma 2. For the representation in Lemma 1,$$

S(R)=S(Q_1)-S(Q_2)-S(Q_3)+S(Q_4).

This follows from additivity of cell sums. Lemma 3. The absolute value of the sum over any rectangle is at most $4$. Applying the hypothesis $|S(Q_i)|\le1$ to the identity of Lemma 2 gives the bound. The most delicate point is Lemma 1, namely the exact geometric decomposition of a rectangle into four squares. ## Solution Let $S(X)$ denote the sum of the numbers written in all cells of a finite union $X$ of grid cells. Consider an arbitrary rectangle $R$. Let its side lengths be $m$ and $n$, where $m\le n$. Since translating a region does not affect any of the identities below, we may place the rectangle so that

R=[0,n]\times[0,m].

$$Define four squares:$$

Q_1=[0,n]\times[0,n],

$$$$

Q_2=[0,n-m]\times[0,n-m],

$$$$

Q_3=[0,n]\times[m,n],

$$$$

Q_4=[0,n-m]\times[m,n-m].

The square $Q_2$ is contained in $Q_1$, and $Q_4$ is contained in $Q_3$. The set difference $Q_1\setminus Q_2$ consists of the cells of $Q_1$ lying either above the line $y=n-m$ or to the right of the line $x=n-m$. Similarly, the set difference $Q_3\setminus Q_4$ consists of the cells of $Q_3$ lying either above the line $y=n-m$ or to the right of the line $x=n-m$. Hence the two L-shaped regions $Q_1\setminus Q_2$ and $Q_3\setminus Q_4$ coincide everywhere except in the strip

[0,n]\times[0,m].

$$More precisely,$$

(Q_1\setminus Q_2)\setminus(Q_3\setminus Q_4)=R,

$$and$$

(Q_3\setminus Q_4)\subseteq(Q_1\setminus Q_2).

$$Therefore, as indicator functions of cell sets,$$

1_R=1_{Q_1}-1_{Q_2}-1_{Q_3}+1_{Q_4}.

$$By additivity of sums,$$

S(R)=S(Q_1)-S(Q_2)-S(Q_3)+S(Q_4).

Each $Q_i$ is a square. By the hypothesis,

|S(Q_i)|\le1

\qquad (i=1,2,3,4).

$$Applying the triangle inequality,$$

|S(R)|

\le

|S(Q_1)|+|S(Q_2)|+|S(Q_3)|+|S(Q_4)|

\le 4.

Since $R$ was arbitrary, every rectangle sum has absolute value at most $4$. Thus the sums of the numbers in all rectangles are uniformly bounded, and one may take $c=4$. This completes the proof. ∎ ## Verification of Key Steps The first delicate step is the identity

1_R=1_{Q_1}-1_{Q_2}-1_{Q_3}+1_{Q_4}.

Take a point $(x,y)$. If $0\le y<m$, then $(x,y)\notin Q_3$ and $(x,y)\notin Q_4$. The right-hand side becomes $1_{Q_1}-1_{Q_2}$. Since $y<m\le n-m+y$, membership in $Q_2$ is equivalent to $x\le n-m$. Thus the value is $1$ exactly when $0\le x\le n$, which is precisely the rectangle $R$. If $m\le y\le n$, then $1_{Q_3}=1$ whenever $1_{Q_1}=1$, and $1_{Q_4}=1$ whenever $1_{Q_2}=1$. Hence the right-hand side equals $0$. These two cases cover all points of $Q_1$, and points outside $Q_1$ give value $0$ automatically. The second delicate step is passing from the set identity to sums. Since every cell contributes linearly, indicator-function identities translate directly into identities for sums. No cancellation issues arise because all regions involved are finite. A common mistake would be to decompose the rectangle into a large number of squares and then sum the bounds. That yields a bound depending on the rectangle dimensions and does not produce the required uniform estimate. ## Alternative Approaches One may introduce the cumulative sum function

F(x,y)=S([0,x]\times[0,y]).

The sum over any rectangle is a mixed finite difference of $F$. The hypothesis says that the mixed finite difference of $F$ over every square is bounded by $1$. Using suitable algebraic identities, one can express the mixed difference over an arbitrary rectangle as a linear combination of four mixed differences over squares. This leads again to the bound $4$. The geometric decomposition into four squares is preferable because it works directly with the regions themselves. The proof reduces the problem to a single exact identity of indicator functions and then applies the hypothesis immediately.