Kvant Math Problem 348
The numbers in the table are
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m51s
Source on kvant.digital
Problem
In the table $10\times10$, the numbers from 1 to 100 are written in order. Then, in each row and each column, exactly half of the numbers are marked with a minus sign. Prove that in the resulting table, the sum of all the numbers is zero.
S. M. Ageev
Exploration
The numbers in the table are
$$\begin{matrix} 1&2&\cdots&10\ 11&12&\cdots&20\ \vdots\ 91&92&\cdots&100 \end{matrix}.$$
Let the sign attached to the entry in row $i$, column $j$ be $s_{ij}\in{1,-1}$. The condition says that in every row exactly five entries receive a minus sign and five do not. Hence each row contains five $+1$'s and five $-1$'s, so
$$\sum_{j=1}^{10}s_{ij}=0$$
for every row $i$. The same reasoning gives
$$\sum_{i=1}^{10}s_{ij}=0$$
for every column $j$.
The entry in row $i$, column $j$ equals
$$10(i-1)+j.$$
The signed sum is therefore
$$\sum_{i,j}s_{ij}\bigl(10(i-1)+j\bigr).$$
This expression separates into a row part and a column part. If that works, the row condition should annihilate the first part and the column condition should annihilate the second.
To test the idea, consider a $2\times2$ table
$$\begin{matrix} 1&2\ 3&4 \end{matrix}$$
with one minus sign in each row and column. Taking signs
$$\begin{matrix} +&-\ -&+ \end{matrix}$$
gives $1-2-3+4=0$. The decomposition yields
$$\sum s_{ij}(2(i-1)+j) = 2\sum (i-1)s_{ij} +\sum j s_{ij},$$
and each term vanishes for the same reason. The mechanism is consistent.
The step most likely to hide an error is the passage from the combinatorial condition on minus signs to the equations $\sum_j s_{ij}=0$ and $\sum_i s_{ij}=0$. Once those identities are established, the algebra is straightforward.
Problem Understanding
The table consists of the integers from $1$ to $100$ written in the usual $10\times10$ order. Some entries are multiplied by $-1$ so that in every row exactly five entries become negative and in every column exactly five entries become negative. We must prove that the total sum of all signed entries equals $0$.
This is a Type B problem, a pure proof.
The core difficulty is to convert the condition on the distribution of signs into algebraic identities that force the weighted sum of the entries to vanish.
Proof Architecture
Define $s_{ij}\in{1,-1}$ to be the sign of the entry in row $i$, column $j$; then for every row $i$,
$$\sum_{j=1}^{10}s_{ij}=0,$$
because each row contains five $+1$'s and five $-1$'s.
For every column $j$,
$$\sum_{i=1}^{10}s_{ij}=0,$$
because each column contains five $+1$'s and five $-1$'s.
The number in position $(i,j)$ equals $10(i-1)+j$.
Writing the total signed sum as
$$\sum_{i,j}s_{ij}\bigl(10(i-1)+j\bigr)$$
and separating the two terms produces a sum annihilated by the row identities and a sum annihilated by the column identities.
The lemma most likely to fail under scrutiny is the derivation of the row and column identities from the condition on minus signs.
Solution
Let $s_{ij}\in{1,-1}$ denote the sign attached to the number in row $i$ and column $j$. Thus $s_{ij}=-1$ if that number is marked with a minus sign and $s_{ij}=1$ otherwise.
Since each row contains exactly five minus signs and five plus signs, every row contains five entries with sign $-1$ and five entries with sign $+1$. Hence, for every $i$,
$$\sum_{j=1}^{10}s_{ij} = 5-5 = 0.$$
Similarly, each column contains exactly five minus signs and five plus signs, so for every $j$,
$$\sum_{i=1}^{10}s_{ij} = 0.$$
The number in row $i$, column $j$ is
$$a_{ij}=10(i-1)+j.$$
Let $S$ be the total sum of all signed entries. Then
$$S = \sum_{i=1}^{10}\sum_{j=1}^{10} s_{ij}a_{ij} = \sum_{i=1}^{10}\sum_{j=1}^{10} s_{ij}\bigl(10(i-1)+j\bigr).$$
Separating the two terms gives
$$S = 10\sum_{i=1}^{10}(i-1)\sum_{j=1}^{10}s_{ij} + \sum_{j=1}^{10}j\sum_{i=1}^{10}s_{ij}.$$
For every $i$,
$$\sum_{j=1}^{10}s_{ij}=0,$$
so the first sum is $0$. For every $j$,
$$\sum_{i=1}^{10}s_{ij}=0,$$
so the second sum is also $0$. Therefore
$$S=0.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is proving
$$\sum_{j=1}^{10}s_{ij}=0.$$
A careless argument might count only the minus signs. The actual computation is that a row contains five occurrences of $+1$ and five occurrences of $-1$, hence the sum of the ten signs is $5-5=0$.
The second delicate step is the decomposition
$$a_{ij}=10(i-1)+j.$$
This formula must be checked against the layout of the table. Row $i$ contains the integers from $10(i-1)+1$ through $10(i-1)+10$, so the entry in column $j$ is indeed $10(i-1)+j$.
The third delicate step is the separation
$$\sum_{i,j}s_{ij}\bigl(10(i-1)+j\bigr) = 10\sum_i (i-1)\sum_j s_{ij} + \sum_j j\sum_i s_{ij}.$$
Each coefficient $10(i-1)$ depends only on $i$, allowing it to be factored out of the inner sum over $j$; similarly, $j$ depends only on $j$. After this rearrangement, the row and column identities apply directly and force both terms to vanish.
Alternative Approaches
Let $r_i=10(i-1)$. Then the entry in position $(i,j)$ is $r_i+j$. The total signed sum can be interpreted as the sum of two tables: one whose $i$-th row is constantly $r_i$, and one whose $j$-th column is constantly $j$. In the first table, the contribution of row $i$ is $r_i\sum_j s_{ij}$, which is $0$ because each row contains equally many positive and negative signs. In the second table, the contribution of column $j$ is $j\sum_i s_{ij}$, which is $0$ because each column contains equally many positive and negative signs. Adding the two contributions gives total sum $0$.
This approach is essentially the same linear decomposition as the main proof, but expressed as a decomposition of the numerical table itself rather than of the final sum.