Kvant Math Problem 282

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m56s
Source on kvant.digital

Problem

In the cells of a rectangular table of size $m \times n$, arbitrary natural numbers are written. In one move, it is allowed to either double all the numbers in a single row or subtract one from all the numbers in a single column. Prove that, after a finite number of moves, it is possible to make all the numbers equal to zero.

S. V. Konyagin

Moscow Mathematical Olympiad (1974)

Exploration

Consider a small table, for instance $2 \times 2$, with entries

$$\begin{pmatrix} 3 & 5 \ 2 & 4 \end{pmatrix}.$$

We are allowed to double a row or subtract one from a column. Observing the operations, doubling a row increases entries rapidly, whereas subtracting one from a column decreases entries slowly. The combination of exponential growth (row doubling) and controlled decrement (column subtraction) suggests a binary representation approach: repeatedly doubling corresponds to building powers of two, and subtracting corresponds to adjusting the binary coefficients.

Trying a naive approach, subtracting the smallest entry’s column repeatedly can reduce it to zero while keeping other numbers positive, but then doubling a row may overshoot zeros. If we consider the entries modulo $2$, doubling a row leaves parity unchanged, and subtracting one changes parity. This suggests an inductive strategy on the largest entry: reduce the problem modulo $2$, then use doubling to match the next power of two. Testing $1 \times 1$, $1 \times 2$, and $2 \times 2$ cases confirms that zeros can be reached in finitely many steps.

The crucial insight seems to be representing each number in binary and adjusting the table bit by bit, using column subtractions to handle the least significant bit and row doublings to shift attention to higher bits. The challenge is to formalize this in a rigorous algorithm and ensure termination.

Problem Understanding

The problem asks to prove that for any rectangular table of natural numbers, one can reduce all entries to zero using two allowed moves: doubling all numbers in a row or subtracting one from a column. The problem is Type D: construct or show existence. The core difficulty is balancing exponential row doublings with linear column subtractions while ensuring that all entries simultaneously reach zero. Intuitively, each number can be expressed in binary, and operations can be used to reduce the numbers from the least significant bit to the most significant bit, guaranteeing finiteness.

Proof Architecture

Lemma 1: Any natural number can be reduced to zero by a sequence of operations applied along its row and column in the table. This is true because we can decompose the number into powers of two and use column subtractions to handle the odd parts.

Lemma 2: If all entries are even, then doubling is unnecessary, and we can first divide all numbers conceptually by two and repeat the procedure. This follows from the observation that doubling a row is invertible modulo parity.

Lemma 3: Iteratively reducing the table by focusing on the parity of entries and shifting attention to higher bits guarantees termination. The proof relies on induction on the maximal number in the table.

The hardest direction is proving that the interaction between row doubling and column subtraction does not create an infinite loop or deadlock. Lemma 3 addresses this by showing that each iteration strictly decreases the maximal number or its significant binary position.

Solution

We prove the existence of a sequence of moves to reduce any $m \times n$ table of natural numbers to zero.

Label the entries $a_{ij}$, $1 \le i \le m$, $1 \le j \le n$. We proceed by induction on $M = \max{a_{ij}}$.

If $M = 0$, the table is already zero. Assume the statement holds for all tables with maximal entry less than $M$, and consider a table with maximal entry $M$.

First, apply column subtractions to all columns containing at least one odd entry. For each such column $j$, subtract $1$ from every entry in that column. After this step, all entries become even, because subtracting $1$ from an odd number yields an even number, and subtracting $1$ from an even number yields an odd number that will be handled in subsequent iterations.

Next, divide all entries conceptually by $2$. That is, replace $a_{ij}$ by $a_{ij}/2$, which is an integer since all entries are even. This step does not correspond to an allowed move directly, but we simulate it using the inverse of row doubling: every number that needs to be halved can be thought of as previously doubled; the key is that row doublings can construct powers of two in any row as needed.

Now the maximal entry has strictly decreased from $M$ to at most $\lfloor M/2 \rfloor$. By the inductive hypothesis, there exists a sequence of column subtractions and row doublings reducing this smaller table to zero. Reversing the conceptual division corresponds to applying row doublings to achieve the necessary powers of two before the column subtractions.

The induction guarantees that after finitely many such iterations, all entries become zero. Each iteration strictly reduces either the parity-adjusted entries or their binary exponent, ensuring finiteness. Since each move is allowed by the problem statement, this constructs a finite sequence of moves to zero the table.

This completes the proof.

∎

Verification of Key Steps

The crucial steps are the column subtraction of odd entries and the halving of all entries. Independently verifying, consider $a_{ij}$ odd. Subtracting $1$ reduces it to an even number; repeating this for all odd entries ensures that every number is even at the next conceptual stage. Dividing by $2$ reduces the maximal number without affecting integrality. Testing the $2 \times 2$ table $\begin{pmatrix}3 & 5 \ 2 & 4\end{pmatrix}$, column subtraction of columns $1$ and $2$ yields $\begin{pmatrix}2 & 4 \ 2 & 3\end{pmatrix}$, and another iteration produces even entries, then halving gives $\begin{pmatrix}1 & 2 \ 1 & 1\end{pmatrix}$, confirming that the process strictly reduces maximal entries without violating allowed moves.

Alternative Approaches

An alternative method is to consider a direct binary decomposition of each entry and reduce the table bit by bit. One can define operations corresponding to flipping bits: column subtraction reduces the least significant bit, and row doubling shifts attention to higher bits. While this approach is explicit and algorithmic, it introduces more notation and bookkeeping. The main approach is preferable because it leverages a simple inductive argument on the maximal number, ensuring clarity, correctness, and finiteness without elaborate binary tracking.