Kvant Math Problem 696

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m58s
Source on kvant.digital

Problem

Is it possible to fill a $10 \times 10$-cell table with 100 distinct natural numbers so that for any $k \times k$-cell square ($2 \le k \le 10$)

the sums,
the products

$k$ of the numbers on its diagonals are equal?

A. Balinsky

Exploration

Consider the problem for small $k \times k$ squares. For a $2 \times 2$ square, the two diagonals each contain two numbers. If the sums of the diagonals must be equal, then for numbers $a, b, c, d$ arranged as

$$\begin{pmatrix} a & b \ c & d \end{pmatrix},$$

the condition $a + d = b + c$ must hold. Simultaneously, the products of the diagonals must satisfy $a d = b c$. These two conditions imply strong constraints on the numbers. Using the equations, we can solve for $d$ in terms of $a, b, c$ from the sum equality: $d = b + c - a$. Substituting into the product equality yields $a(b + c - a) = b c$, which simplifies to $ab + ac - a^2 = bc$, then $-a^2 + a(b + c) - bc = 0$, which factors as $(a - b)(a - c) = 0$. Thus $a = b$ or $a = c$, forcing repetition. Already in the $2 \times 2$ case, distinct numbers are impossible.

Extending this observation to larger $k$, each $2 \times 2$ sub-square within the $10 \times 10$ table would require a repeated number. Since the table must be filled with distinct natural numbers, this is impossible. The key difficulty is whether the constraints for $k > 2$ could somehow avoid repetition, but the $2 \times 2$ sub-squares already impose an unavoidable collision.

Problem Understanding

The problem asks whether it is possible to fill a $10 \times 10$ table with distinct natural numbers such that for every $k \times k$ square with $2 \le k \le 10$, the sums and products of the numbers along both diagonals are equal. This is a Type B problem, as it requires proving or disproving the existence of such a configuration. The core difficulty is understanding whether the simultaneous sum and product equalities can coexist for distinct numbers. Preliminary calculations with $2 \times 2$ squares suggest an immediate obstruction, hinting that no solution exists.

Proof Architecture

Lemma 1: For any $2 \times 2$ square of natural numbers with equal diagonal sums and equal diagonal products, at least two numbers must coincide. This follows from solving the system of two equations for four variables, yielding $(a - b)(a - c) = 0$.

Lemma 2: Any $k \times k$ square contains a $2 \times 2$ sub-square. This is evident because choosing any two consecutive rows and two consecutive columns within the $k \times k$ square produces a $2 \times 2$ sub-square.

Lemma 3: Therefore, the $10 \times 10$ table must contain repeated numbers. This is a direct consequence of Lemmas 1 and 2, since each $2 \times 2$ sub-square requires repetition, contradicting the distinctness requirement.

The hardest step is Lemma 1, where an explicit algebraic argument must show that equal sums and products enforce repetition.

Solution

Consider a $2 \times 2$ square of natural numbers

$$\begin{pmatrix} a & b \ c & d \end{pmatrix}.$$

The condition that the sums of the diagonals are equal gives

$$a + d = b + c,$$

and the condition that the products of the diagonals are equal gives

$$a d = b c.$$

From the sum equality, solve for $d$:

$$d = b + c - a.$$

Substitute into the product equality:

$$a(b + c - a) = b c.$$

Expand and rearrange:

$$a b + a c - a^2 = b c \implies -a^2 + a(b + c) - b c = 0.$$

This factors as

$$(a - b)(a - c) = 0,$$

so $a = b$ or $a = c$. In either case, the square contains repeated numbers. This proves Lemma 1.

Next, any $k \times k$ square with $k \ge 2$ contains a $2 \times 2$ sub-square. This sub-square must satisfy the same diagonal sum and product conditions, so by Lemma 1, it contains repeated numbers. Applying this to the $10 \times 10$ table shows that the table must have repeated numbers.

Since the problem requires all 100 numbers to be distinct, this is impossible. Hence, no such table exists.

This completes the proof.

∎

Verification of Key Steps

The derivation in Lemma 1 was verified by explicitly solving the system for $d$ and substituting into the product equation. Factoring $-a^2 + a(b + c) - bc$ as $(a - b)(a - c)$ was checked by expansion: $(a - b)(a - c) = a^2 - a c - a b + b c = -a^2 + a(b + c) - b c$ after multiplying both sides by $-1$, confirming correctness. The application of Lemma 1 to all $2 \times 2$ sub-squares inside larger $k \times k$ squares was confirmed by considering arbitrary pairs of consecutive rows and columns, guaranteeing coverage of every $2 \times 2$ subset.

Alternative Approaches

One could attempt a combinatorial argument using parity or modular arithmetic, assigning hypothetical numbers modulo a prime and showing a collision in diagonal sums or products must occur. Another approach is to attempt explicit construction for small tables and observe failure patterns as size increases. The algebraic method presented is preferable because it provides a direct and complete obstruction in the simplest $2 \times 2$ case, which immediately scales to the full $10 \times 10$ table.