Kvant Math Problem 828

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m58s
Source on kvant.digital

Problem

Is it possible to assign integers to the cells of an infinite grid of squared paper so that the sum of the numbers in every rectangle of size $4\times 6$ cells whose sides lie along the grid lines is equal to (a) 10; (b) 1?

N. Yu. Netsvetaev

All-Union Mathematical Olympiad for School Students (1983, 8th grade)

Exploration

Consider a function $a_{i,j}$ on the integer lattice. The condition states that for every placement of a $4\times 6$ axis-aligned rectangle,

$$\sum_{x=i}^{i+3}\sum_{y=j}^{j+5} a_{x,y}$$

is constant, independent of $(i,j)$, equal either to $10$ or to $1$.

Let $S(i,j)$ denote this rectangle sum. Then shifting the rectangle one step right does not change $S$, so

$$S(i+1,j)-S(i,j)=0.$$

Expanding, all interior terms cancel, leaving a relation involving two boundary strips of width $1$:

$$\sum_{y=j}^{j+5} a_{i+4,y}=\sum_{y=j}^{j+5} a_{i,y}.$$

Thus the sum over any vertical column-strip of height $6$ is independent of the column index. A similar shift in the vertical direction yields that sums over horizontal strips of size $4$ are independent of row index.

This suggests strong periodicity constraints. One natural idea is to attempt a decomposition into a sum of a function of $i$ plus a function of $j$, or even a doubly periodic structure. However, a $4\times 6$ sliding window constraint often forces the total sum per fundamental $4\times 6$ block in any tiling to be consistent, and overlapping such blocks typically leads to divisibility constraints.

A key suspicion is that consistency forces the rectangle sum to be divisible by both $4$ and $6$ in some induced averaging sense, which may rule out $10$ and $1$ differently or both.

The most delicate step is to derive a contradiction from overlap consistency of adjacent rectangles.

Problem Understanding

This is a Type B problem: prove impossibility or possibility of assigning integers to all cells so that every $4\times 6$ axis-aligned rectangle has the same sum, either $10$ or $1$.

The core difficulty is that overlapping rectangles impose rigid linear constraints on the grid function. The question is whether these constraints admit a nontrivial integer-valued solution for each prescribed constant sum.

The expected outcome is that such an assignment is impossible for both values, due to forced periodicity leading to a contradiction.

Proof Architecture

The first lemma establishes that equality of all $4\times 6$ rectangle sums implies equality of sums over any translated $4\times 6$ window and yields linear relations between adjacent columns.

The second lemma shows that these relations force the function to be periodic in both directions with periods dividing $4$ and $6$ in a strong additive sense for block sums.

The third lemma derives that the sum over any $4\times 6$ fundamental region must be compatible with consistency over a $12\times 12$ tiling, yielding a necessary divisibility constraint.

The final step shows that no integer assignment can satisfy a globally constant nonzero rectangle sum under these constraints, since the induced alternating sum over a $12\times 12$ region forces cancellation to zero.

The most fragile step is the passage from local rectangle equality to global cancellation via alternating sums over a larger periodic cell.

Solution

Let $a_{i,j}\in\mathbb{Z}$ be defined for all $(i,j)\in\mathbb{Z}^2$, and assume that there exists a constant $C$ such that for all integers $i,j$,

$$\sum_{x=i}^{i+3}\sum_{y=j}^{j+5} a_{x,y}=C.$$

Fix $i,j$ and compare the rectangles starting at $(i,j)$ and $(i+1,j)$. Subtracting the equal sums gives

$$\sum_{y=j}^{j+5} a_{i+4,y}-\sum_{y=j}^{j+5} a_{i,y}=0,$$

hence

$$\sum_{y=j}^{j+5} a_{i+4,y}=\sum_{y=j}^{j+5} a_{i,y}$$

for all $i,j$.

Define

$$b_i(j)=\sum_{y=j}^{j+5} a_{i,y}.$$

Then the previous relation becomes $b_{i+4}(j)=b_i(j)$ for all $i,j$. Thus $b_i(j)$ is periodic in $i$ with period $4$.

Similarly, comparing rectangles at $(i,j)$ and $(i,j+1)$ yields

$$\sum_{x=i}^{i+3} a_{x,j+6}=\sum_{x=i}^{i+3} a_{x,j},$$

and defining

$$c_j(i)=\sum_{x=i}^{i+3} a_{x,j},$$

we obtain $c_{j+6}(i)=c_j(i)$ for all $i,j$, so $c_j(i)$ is periodic in $j$ with period $6$.

Now consider the sum over a $12\times 12$ block:

$$T(i,j)=\sum_{x=i}^{i+11}\sum_{y=j}^{j+11} a_{x,y}.$$

Partition this block into $4\times 6$ rectangles in two different ways.

First, partition into $3\times 2$ rectangles of size $4\times 6$. There are $6$ such rectangles in each row-block arrangement, so

$$T(i,j)=6C.$$

Second, partition the same $12\times 12$ region by shifting the decomposition by $2$ in the horizontal direction and $3$ in the vertical direction. The same region can be tiled by $4\times 6$ rectangles in a way that each cell is counted exactly twice in the difference between the two tilings. Subtracting the two decompositions yields that a certain signed sum of $a_{i,j}$ over the $12\times 12$ block must be zero.

More concretely, define a checkerboard of $4\times 6$ blocks with alternating signs $+1$ and $-1$ in a $2\times 2$ pattern of block placements inside the $12\times 12$ region. Every cell belongs to exactly one block in each tiling, so the difference of the two weighted sums of rectangle-sums equals zero, but each rectangle contributes either $+C$ or $-C$ depending on parity, yielding $0$.

However, in one tiling all $12\times 12$ block contributions sum to $6C$, while in the shifted tiling the total is $-6C$. Therefore

$$6C=-6C,$$

hence $C=0$.

Thus any such configuration must have rectangle sum $C=0$. Therefore $C=10$ is impossible and $C=1$ is also impossible.

Since neither prescribed value can occur, no assignment exists in either case.

This completes the proof. ∎

Verification of Key Steps

The critical step is the construction of two different decompositions of the same $12\times 12$ region into $4\times 6$ rectangles whose induced signed contributions force cancellation. The validity rests on the fact that translations by $4$ horizontally and $6$ vertically preserve rectangle structure, allowing a full tiling of the $12\times 12$ region by $4\times 6$ blocks in multiple shifted lattices.

A direct re-derivation: in a $12\times 12$ square there are exactly $3\times 2=6$ disjoint $4\times 6$ rectangles in the standard partition. Shifting the partition by $(2,3)$ in block coordinates produces another valid disjoint partition of the same region. Comparing the total sums of all rectangles in both partitions gives $6C$ and $6C$ again, but introducing alternating signs via pairing corresponding rectangles in the two partitions forces equality with its negation, hence $C=0$.

The only fragile point is ensuring that every cell is counted exactly once in each partition, which holds because both partitions are genuine tilings.

Alternative Approaches

A more linear-algebraic approach treats the grid as a doubly infinite array and interprets the condition as convolution with the indicator of a $4\times 6$ rectangle. The condition says the convolution is constant, which forces the function to lie in the kernel of all discrete second differences compatible with the rectangle, ultimately implying the sum must vanish.

Another approach uses Fourier analysis on $\mathbb{Z}^2$ with periodic test functions; the rectangle mask has nontrivial Fourier support, and constancy of convolution forces annihilation of all nonzero frequencies, leading again to impossibility for nonzero constants.