1971 IMO Problems/Problem 6

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$ .

Solution 1

Take the the row or column (without loss of generality, a row) with the minimum possible sum $S$ of its elements. Let $z$ be the number of zeros in this row. We will assume $S < \frac{n}{2}$ once the other case is obvious. Clearly $S \ge n - z \Rightarrow z \ge n - S$ . The total sum $T$ of all elements of the matrix is at least the number of zeros in this row multiplicated by $n - S$ (because the sum of the elements of a row and a column meeting in a zero is $\ge n$ ) plus the number of nonzero elements times $S$ (that is the minimum possible sum), it is, $z(n - S) + (n - z)S.$ Note that, being $z \ge n - S$ and $n - S \ge S$ , we can put $z - 1$ instead of $z$ and $n - z + 1$ instead of $n - z$ until we get $z = n - S$ , what makes the sum become smaller. So we have $T \ge (n - S)^2 + S^2 \ge 2(\frac{n - S + S}{2})^2 = \frac{n^2}{2}$ by AM - QM inequality.

The above solution was posted and copyrighted by Renan. The original thread for this problem can be found here: [1]

Solution 2

Denote $\ell_i,c_i$ the $i$ th line and column and $s(\ell_i), s(c_i)$ the sum of the elements on that row. Let $M=\max_{\sigma \in S_n} | \{ 1\le i\le n| a_{i\sigma(i)}=0\} |$ . For each permutation $\sigma\in S_n$ , assign to it the number $\displaystyle\sum\limits_{a_{i\sigma(i)=0}} \left ( s(\ell_i)+s(c_{\sigma(i)}) \right )$ Now pick a permutation $\sigma$ such that it generates $M$ and its assigned number is minimal. Suppose wlog that $\{ 1\le i\le n| a_{i\sigma(i)}=0\}=\{1,2,..,k\}$ . If $k=n$ , we are done as twice the sum of all elements is $\displaystyle\sum\limits_{i=1}^{n} s(\ell_i) +\displaystyle\sum\limits_{i=1}^{n} s(c_i)=\displaystyle\sum\limits_{i=1}^{n} (s(\ell_i)+s(c_{\sigma(i)}))\ge n^2$ So suppose $k<n$ and look at a $j$ such that $k+1\le j\le n$ . By the maximality of $M$ , $\ell_j$ can have $0$ only on the columns $\sigma(1),...,\sigma(k)$ . Note that if $\ell_j$ has a $0$ on $c_{\sigma(r)}$ with $r\le k$ , i.e. $a_{j\sigma(r)}=0$ , by the minimality of the assigned number of $\sigma$ , we have that $s(\ell_j)\ge s(\ell_r)$ . However, if the column $c_{\sigma(j)}$ has a $0$ on $\ell_r$ , i.e. $a_{r\sigma(j)}=0$ , by the same argument we have $s(c_\sigma(j))\ge s(c_\sigma(r))$ , hence $s(\ell_j)+s(c_{\sigma(j)})\ge s(r)+s(c_{\sigma(r)})\ge n$ .

Suppose that $0$ appears exactly $t$ times on $\ell_j$ . This means that $s(\ell_j)\ge n-t$ . Suppose that the $0$ s of $\ell_j$ appear on the columns $c_{\sigma(i_1)},...,c_{\sigma(i_t)}$ . We have seen earlier that if $c_\sigma(j)$ has a $0$ on $i_1,..,i_t$ we have that $s(\ell_j)+s(c_{\sigma(j)})\ge n$ . So suppose that it doesn't have $0$ on these lines. However, $c_{\sigma(j)}$ has $0$ s only on the lines $\ell_1,..,\ell_k$ by the maximality of $M$ , hence $c_{\sigma(j)}$ has at most $k-t$ zeroes, so $s(c_{\sigma(j)})\ge n-k+t$ . We thus infer that $s(\ell_j)+s(c_{\sigma(j)})\ge (n-t)+(n-k+t)=2n-k\ge n$ so $s(\ell_j)+s(c_{\sigma(j)})\ge n,\ \forall j\ge k+1$ . By the hypothesis this is also true for $j\le k$ so summing over all values of $j$ we get that the sum is at least $\dfrac{n^2}{2}$ .

The above solution was posted and copyrighted by Aiscrim. The original thread for this problem can be found here: [2]

Solution 3

If the main diagonal contains all zeroes, we can immediately deduce from the condition that the sum $S$ of the elements is at least $n^2/2$ . This motivates us to consider the largest possible subset of elements, all zero, which are pairwise in different rows of columns - let the size of this subset be $k$ . (If there is no such subset, $S\ge n^2$ .)

Since the condition is invariant under the operation of switching rows or columns, we may rearrange the matrix such that these $k$ entries are on the main diagonal of the matrix, i.e. $a_{11}=a_{22}=\dots=a_{kk}=0$ . Let $X=\sum_{1\le i,j\le k}a_{ij}$ , $Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij}$ and $Z=\sum_{k<i,j\le n}a_{ij}$ . Then applying the condition to $a_{11},\dots,a_{kk}$ , we get $2X+Y\ge kn$ .

If $i\le k<j$ , then if $a_{ij}=a_{ji}=0$ , then we may toss $a_{ii}$ out of our set and replace it with $a_{ij}$ and $a_{ji}$ , to form a larger feasible set of elements, contradiction. Consequently, $a_{ij}+a_{ji}\ge 1$ for $i\le k<j$ , which upon summation yields $Y\ge k(n-k)$ . Finally, $Z\ge (n-k)^2$ , trivially. Therefore, $2S=2(X+Y+Z)\ge 2X+Y+Y+Z\ge kn+k(n-k)+(n-k)^2=k^2+2k(n-k)+(n-k)^2=n^2.$

The above solution was posted and copyrighted by randomusername. The original thread for this problem can be found here: [3]

1971 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search

1971 IMO Problems/Problem 6

Contents

Problem

Solution 1

Solution 2

Solution 3

See Also