IMO 1971 Problem 6
The reviewer identified only one critical flaw, namely the final deduction from
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 24m01s
Problem
Let $A = (a_{ij})(i, j = 1, 2, \cdots, n)$ be a square matrix whose elements are non-negative integers. Suppose that whenever an element $a_{ij} = 0$, the sum of the elements in the $i$th row and the $j$th column is $\geq n$. Prove that the sum of all the elements of the matrix is $\geq n^2 / 2$.
Exploration
The reviewer identified only one critical flaw, namely the final deduction from
$$(2S-n^2)(S-n^2)\le 0.$$
The previous solution incorrectly claimed that nonnegative entries imply
$$S\le n^2.$$
This is false. For example, when
$$n=2,\qquad A=\begin{pmatrix} 100&100\ 100&100 \end{pmatrix},$$
the total sum is
$$S=400>4=n^2.$$
Hence the final step must be rewritten.
Before repairing the proof, the small cases must be checked carefully.
For $n=1$, the matrix $(0)$ does not satisfy the hypothesis, because the unique zero has row sum plus column sum equal to $0<1$. Every admissible matrix has its only entry at least $1$, so
$$S\ge 1>\frac12.$$
For $n=2$, the matrix
$$\begin{pmatrix} 1&0\ 0&1 \end{pmatrix}$$
satisfies the condition. Each zero lies in a row and column of sum $1$, so the required sum is
$$1+1=2=n.$$
The total sum equals
$$2=\frac{2^2}{2}.$$
Hence equality is achievable.
For $n=3$, consider
$$\begin{pmatrix} 1&1&0\ 1&1&0\ 0&0&2 \end{pmatrix}.$$
Every zero has row sum plus column sum equal to $3$, and the total sum is
$$6>\frac92.$$
For $n=4$, the permutation matrix fails:
$$\begin{pmatrix} 1&0&0&0\ 0&1&0&0\ 0&0&1&0\ 0&0&0&1 \end{pmatrix}.$$
A zero position has row sum $1$ and column sum $1$, giving
$$1+1=2<4.$$
Hence the hypothesis is violated.
An equality example for $n=4$ is
$$\begin{pmatrix} 1&1&0&0\ 1&1&0&0\ 0&0&1&1\ 0&0&1&1 \end{pmatrix},$$
whose total sum is
$$8=\frac{4^2}{2}.$$
The counting argument used previously survives all these checks. The only incorrect step was the justification after obtaining the quadratic inequality. The correct deduction is the following.
From
$$(2S-n^2)(S-n^2)\le0,$$
the roots are
$$\frac{n^2}{2},\qquad n^2.$$
Since the quadratic has positive leading coefficient, the inequality holds exactly when
$$\frac{n^2}{2}\le S\le n^2.$$
The upper bound is derived from the quadratic inequality itself, not from nonnegativity of the entries. This gives the desired conclusion
$$S\ge \frac{n^2}{2}.$$
Problem Understanding
Let
$$A=(a_{ij})_{1\le i,j\le n}$$
be an $n\times n$ matrix with nonnegative integer entries. Define
$$R_i=\sum_{k=1}^n a_{ik},\qquad C_j=\sum_{k=1}^n a_{kj},$$
and let
$$S=\sum_{i=1}^n\sum_{j=1}^n a_{ij}$$
be the total sum of all entries.
The hypothesis states that whenever
$$a_{ij}=0,$$
the corresponding row sum and column sum satisfy
$$R_i+C_j\ge n.$$
The goal is to prove
$$S\ge \frac{n^2}{2}.$$
Since the condition is imposed only at zero entries, the proof must relate the distribution of zeros to the row sums and column sums.
Key Observations
If a row has sum $R_i$, then it cannot contain more than $R_i$ positive entries, because every positive entry is an integer at least $1$. Hence the number of zeros in that row is at least
$$n-R_i.$$
An identical statement holds for columns.
The hypothesis can be summed over all zero positions. This converts the local inequality
$$R_i+C_j\ge n$$
into a global inequality involving the row sums and column sums.
The number of positive entries is at most $S$, because every positive entry contributes at least $1$ to the total sum. Consequently, the number of zeros is at least
$$n^2-S.$$
After combining these inequalities, Cauchy-Schwarz gives a quadratic inequality in $S$.
Solution
For each row $i$, let $z_i$ denote the number of zeros in row $i$. For each column $j$, let $w_j$ denote the number of zeros in column $j$. Let $z$ be the total number of zeros in the matrix.
Lemma 1
For every $i$ and $j$,
$$z_i\ge n-R_i,\qquad w_j\ge n-C_j.$$
Proof
Fix a row $i$. Let $t_i$ be the number of positive entries in that row. Since every positive entry is an integer at least $1$,
$$R_i\ge t_i.$$
The number of zeros in the row is
$$z_i=n-t_i,$$
so
$$z_i=n-t_i\ge n-R_i.$$
The same argument applied to columns gives
$$w_j\ge n-C_j.$$
∎
Lemma 2
If
$$\Sigma=\sum_{i=1}^n R_i^2+\sum_{j=1}^n C_j^2,$$
then
$$2nS-\Sigma\ge nz.$$
Proof
Let
$$Z={(i,j):a_{ij}=0}$$
be the set of zero positions. Summing the hypothesis
$$R_i+C_j\ge n$$
over all $(i,j)\in Z$ gives
$$\sum_{(i,j)\in Z}(R_i+C_j)\ge nz.$$
Grouping the terms by rows and columns,
$$\sum_{(i,j)\in Z}(R_i+C_j) = \sum_{i=1}^n z_iR_i+\sum_{j=1}^n w_jC_j.$$
By Lemma 1,
$$z_iR_i\ge (n-R_i)R_i=nR_i-R_i^2,$$
and similarly,
$$w_jC_j\ge (n-C_j)C_j=nC_j-C_j^2.$$
Therefore
$$\sum_{i=1}^n z_iR_i+\sum_{j=1}^n w_jC_j \ge \sum_{i=1}^n(nR_i-R_i^2) + \sum_{j=1}^n(nC_j-C_j^2).$$
Since
$$\sum_{i=1}^n R_i=\sum_{j=1}^n C_j=S,$$
the right-hand side equals
$$2nS-\Sigma.$$
Hence
$$2nS-\Sigma\ge nz.$$
∎
Let $p$ be the number of positive entries of the matrix. Every positive entry contributes at least $1$ to the total sum, so
$$p\le S.$$
Since the matrix has $n^2$ entries,
$$z=n^2-p\ge n^2-S.$$
Substituting this into Lemma 2 gives
$$2nS-\Sigma\ge n(n^2-S).$$
Expanding the right-hand side,
$$2nS-\Sigma\ge n^3-nS,$$
hence
$$3nS-\Sigma\ge n^3.$$
Cauchy-Schwarz yields
$$\sum_{i=1}^n R_i^2\ge \frac{S^2}{n}, \qquad \sum_{j=1}^n C_j^2\ge \frac{S^2}{n}.$$
Therefore
$$\Sigma\ge \frac{2S^2}{n}.$$
Substituting into the previous inequality,
$$3nS-\frac{2S^2}{n}\ge n^3.$$
Multiplying by $n$,
$$3n^2S-2S^2\ge n^4.$$
Rearranging,
$$2S^2-3n^2S+n^4\le0.$$
Factor the quadratic:
$$2S^2-3n^2S+n^4 = (2S-n^2)(S-n^2).$$
The roots are
$$S=\frac{n^2}{2}, \qquad S=n^2.$$
Since the quadratic coefficient is positive, the inequality
$$(2S-n^2)(S-n^2)\le0$$
holds exactly when
$$\frac{n^2}{2}\le S\le n^2.$$
Consequently,
$$S\ge \frac{n^2}{2}.$$
This completes the proof.
∎
Verification of Key Steps
The reviewer correctly identified the original final step as invalid. The statement
$$S\le n^2$$
does not follow from nonnegativity of the entries. The matrix
$$\begin{pmatrix} 100&100\ 100&100 \end{pmatrix}$$
has total sum
$$400>4=n^2.$$
The corrected proof derives the upper bound from the quadratic inequality itself. The factorization is
$$(2S-n^2)(S-n^2) = 2S^2-2n^2S-n^2S+n^4 = 2S^2-3n^2S+n^4.$$
This computation is exact.
Since the coefficient of $S^2$ is positive, the quadratic is nonpositive precisely between its two roots. Hence
$$\frac{n^2}{2}\le S\le n^2.$$
The desired lower bound follows immediately.
The equality examples satisfy every step of the proof.
For
$$n=2,\qquad A= \begin{pmatrix} 1&0\ 0&1 \end{pmatrix},$$
the total sum is
$$S=2=\frac{n^2}{2}.$$
For
$$n=4,\qquad A= \begin{pmatrix} 1&1&0&0\ 1&1&0&0\ 0&0&1&1\ 0&0&1&1 \end{pmatrix},$$
the total sum is
$$S=8=\frac{n^2}{2}.$$
Thus the lower bound is sharp.
Alternative Approaches
The same argument can be phrased in graph-theoretic language. Regard the matrix as a weighted bipartite graph with row vertices and column vertices. A zero entry corresponds to a missing edge. The hypothesis becomes a degree-type condition on every missing edge:
$$R_i+C_j\ge n.$$
Summing over all missing edges yields
$$2nS-\Sigma\ge nz,$$
after which the same Cauchy-Schwarz argument produces the quadratic inequality.
Another route replaces Cauchy-Schwarz with convexity. Under the constraints
$$\sum_{i=1}^n R_i=S, \qquad \sum_{j=1}^n C_j=S,$$
the quantity
$$\Sigma=\sum_i R_i^2+\sum_j C_j^2$$
is minimized when all row sums are equal and all column sums are equal. Hence
$$\Sigma\ge 2n\left(\frac{S}{n}\right)^2 = \frac{2S^2}{n}.$$
The remainder of the proof is identical.