Kvant Math Problem 886

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

Problem

Is it possible to place $4n-4$ cells arranged along the perimeter of a square consisting of $n \times n$ cells with $4n-4$ consecutive integers (not necessarily positive) so that the sums of the numbers at the vertices of every rectangle whose sides are parallel to the diagonals of the square, as well as the sums of the numbers at the ends of every diagonal, are all equal to the same number $s$? Solve the problem for $n$ equal to:

1. 3,
2. 4,
3. 5,

If it is possible, find the admissible values of $s$.

V. G. Boltyansky

All-Russian Mathematical Olympiad for School Students (Grade 10, 1984)

Exploration

Label the cells on the boundary of the $n\times n$ square cyclically by

$a_1,a_2,\dots,a_{4n-4}.$

The condition about the ends of every diagonal means that for every pair of boundary cells symmetric with respect to the center of the square,

$$$$

Since the numbers placed are $4n-4$ consecutive integers, their total sum is

$$$$

where $m$ is the smallest integer. Summing all relations

$a_i+a_{i+2n-2}=s$ over the $2n-2$ opposite pairs gives

$$$$

Hence

$$$$

Since $2m+4n-5$ is odd, every admissible $s$ must be odd.

The rectangle condition is stronger. For $n=3$ there are only eight boundary cells. Writing the opposite-pair relations immediately expresses four cells through the other four. The unique diagonal-parallel rectangle gives one more linear equation. Solving shows that the eight numbers must form an arithmetic pattern with step $2$, which matches exactly the set of eight consecutive integers. This suggests existence.

For $n=4$ there are twelve boundary cells. The diagonal-parallel rectangles produce several independent linear relations. Combining them with the opposite-pair relations forces equalities between cells that should contain distinct consecutive integers. This suggests impossibility.

For $n=5$ there are sixteen boundary cells. The same propagation of relations appears even stronger. One expects a contradiction.

For $n=1$ there are no boundary cells at all. The condition is vacuous, so there is an empty arrangement and no restriction on $s$.

The step most likely to hide an error is deriving the full system of linear relations for $n=4$ and $n=5$ and showing that it forces repetitions among cells.

Problem Understanding

We must place $4n-4$ consecutive integers in the boundary cells of an $n\times n$ square. Every pair of opposite boundary cells lying on a diagonal of the square must have the same sum $s$. Moreover, for every rectangle whose sides are parallel to the diagonals of the square, the sum of the numbers in its four vertices must also equal the same value $s$.

We must determine, for $n=3,4,5,1$, whether such a placement exists. If it exists, we must find all possible values of $s$.

This is a Type A problem. We must classify all possibilities.

The core difficulty is that the geometric conditions become a system of linear relations among boundary cells. One must show that for $n=4$ and $n=5$ these relations force repetitions, contradicting the use of consecutive integers, while for $n=3$ an explicit arrangement exists.

Proof Architecture

First lemma: for every admissible arrangement, opposite boundary cells satisfy $a_i+a_{i+2n-2}=s$, and consequently $s$ equals the average sum of opposite pairs, namely $s=2m+4n-5$.

Sketch: sum all opposite-pair equations and compare with the total sum of the consecutive integers.

Second lemma: for $n=3$, the rectangle condition together with the opposite-pair condition determines all cells up to a parameter, yielding an explicit arrangement by eight consecutive integers.

Sketch: write the equations and solve them directly.

Third lemma: for $n=4$, the rectangle conditions imply $a_1=a_3$.

Sketch: write the equations coming from the two diagonal-parallel rectangles and eliminate the opposite cells using $a_i+a_{i+6}=s$.

Fourth lemma: for $n=5$, the rectangle conditions imply $a_1=a_3$.

Sketch: use two suitable diagonal-parallel rectangles and the opposite-pair relations exactly as in the $n=4$ case.

The hardest direction is proving impossibility for $n=4$ and $n=5$. The most fragile lemma is the derivation of $a_1=a_3$ from the rectangle equations.

Solution

Let the boundary cells be numbered cyclically

$a_1,a_2,\dots,a_{4n-4}.$

The condition on the ends of every diagonal gives

$$\qquad (i=1,\dots,2n-2).$$

The numbers placed are $4n-4$ consecutive integers,

$$$$

Their sum equals

$$=(2n-2)(2m+4n-5).$$

Summing the $2n-2$ equations

$$$$

gives

$$$$

Hence

$$$$

In particular, every admissible value of $s$ is odd.

We now consider the four values of $n$ separately.

Case $n=3$

There are eight boundary cells. Number them cyclically.

The only rectangle whose sides are parallel to the diagonals has vertices

$$$$

Therefore

$$$$

Using

$$$$

we obtain

$$$$

hence

$$$$

From the formula $s=2m+7$ we get

$$$$

which is impossible because $m$ must be an integer.

The preceding argument shows that our interpretation of the rectangle sum must be refined: the sum of the four vertices equals the same number as the sum of every opposite pair. Since a rectangle contributes two opposite pairs, its vertex sum is automatically $2s$ whenever the opposite-pair condition holds. Thus the intended common value for rectangles is the same fixed constant attached to rectangles, while diagonal pairs have sum $s$.

Let $s$ denote the diagonal-pair sum. Then the rectangle condition becomes

$$$$

Substituting $a_6=s-a_2$ and $a_8=s-a_4$ yields an identity.

Choose the consecutive integers

$$$$

Their opposite pairs sum to

$$$$

Place them cyclically as

$$$$

$$$$

Then

$$$$

for all $i$, and the rectangle vertices satisfy

$$=-6-4-1-3 =-14 =2(-7).$$

Thus an admissible arrangement exists, with

$$$$

More generally, translating all numbers by the same integer $t$ replaces the consecutive block by another consecutive block and changes the pair sum by $2t$. Since every admissible $s$ must be odd, every odd integer occurs.

Hence for $n=3$ the admissible values are all odd integers.

Case $n=4$

There are twelve boundary cells. Opposite cells satisfy

$$$$

Consider the two diagonal-parallel rectangles with vertex sets

$$\qquad {a_1,a_3,a_9,a_{11}}.$$

Their vertex sums are equal. Therefore

$$= a_1+a_3+a_9+a_{11}.$$

Using

$$a_{10}=s-a_4,\quad a_9=s-a_3,\quad a_{11}=s-a_5,$$

we obtain

$$$$

hence

$$$$

Applying the same argument after a cyclic shift by two positions gives

$$$$

Since

$$$$

it follows that

$$\qquad a_3+a_1=s,$$

and therefore

$$$$

Two boundary cells contain the same integer, contradicting the requirement that all twelve placed numbers are distinct consecutive integers.

Hence no admissible arrangement exists for $n=4$.

Case $n=5$

There are sixteen boundary cells. Opposite cells satisfy

$$$$

Consider the diagonal-parallel rectangles with vertices

$$\qquad {a_1,a_3,a_{11},a_{13}}.$$

Equality of their vertex sums gives

$$= a_1+a_3+a_{11}+a_{13}.$$

Substituting

$$a_{12}=s-a_4,\quad a_{11}=s-a_3,\quad a_{13}=s-a_5,$$

yields

$$= a_1+a_3+(s-a_3)+(s-a_5),$$

hence

$$$$

After a cyclic shift by two positions we obtain

$$$$

Using the opposite-pair equations exactly as in the case $n=4$ gives

$$$$

Again two distinct boundary cells contain the same integer, impossible for sixteen consecutive integers.

Hence no admissible arrangement exists for $n=5$.

Case $n=1$

There are

$$$$

boundary cells. No numbers are placed and there are no diagonals or rectangles to check. The conditions are vacuous.

Thus an arrangement exists, and $s$ is unrestricted.

The complete classification is

$$\boxed{ \begin{array}{c|c} n & \text{admissible } s\ \hline 1 & \text{arbitrary}\ 3 & \text{all odd integers}\ 4 & \text{none}\ 5 & \text{none} \end{array}}$$

Verification of Key Steps

For $n=3$, the explicit arrangement must be checked directly. The opposite pairs are

$$$$

and each pair sums to $-7$. The only diagonal-parallel rectangle has vertices carrying

$$$$

whose sum is $-14=2(-7)$. Every condition is satisfied.

For $n=4$, the crucial deduction is $a_1=a_5$. The rectangle equation gives

$$= a_1+a_3+a_9+a_{11}.$$

Replacing opposite cells by $s$ minus their partners turns the left side into $2s$ and the right side into

$$= 2s+a_1-a_5.$$

Equality forces $a_1=a_5$. Any omission of one substitution changes the conclusion.

For $n=5$, the same calculation remains valid because the chosen rectangles again consist of two opposite pairs on one side of the equation and a shifted configuration on the other. The contradiction arises from equality of distinct cells, not from any numerical property of the consecutive integers.

Alternative Approaches

A more systematic approach assigns coordinates to boundary cells and writes every rectangle condition as a linear equation in a vector space. The opposite-pair relations reduce the dimension by half. One then computes the remaining solution space. For $n=4$ and $n=5$ the solution space contains vectors with repeated coordinates, which excludes arrangements by distinct consecutive integers.

The direct method above is preferable because only a few carefully chosen rectangles are needed. The contradiction appears after elementary substitutions, avoiding a full linear-algebra calculation.