Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1971 IMO Problems/Problem 6"
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Let <math>A = (a_{ij})(i, j = 1, 2, \cdots, n)</math> be a square matrix whose elements are non-negative integers. Suppose that whenever an element <math>a_{ij} = 0</math>, the sum of the elements in the <math>i</math>th row and the <math>j</math>th column is <math>\geq n</math>. Prove that the sum of all the elements of the matrix is <math>\geq n^2 / 2</math>.
 
Let <math>A = (a_{ij})(i, j = 1, 2, \cdots, n)</math> be a square matrix whose elements are non-negative integers. Suppose that whenever an element <math>a_{ij} = 0</math>, the sum of the elements in the <math>i</math>th row and the <math>j</math>th column is <math>\geq n</math>. Prove that the sum of all the elements of the matrix is <math>\geq n^2 / 2</math>.
 +
 +
==Solution 1==
 +
Take the the row or column (without loss of generality, a row) with the minimum possible sum <math> S</math> of its elements. Let <math> z</math> be the number of zeros in this row. We will assume <math> S < \frac{n}{2}</math> once the other case is obvious. Clearly <math> S \ge n - z \Rightarrow z \ge n - S</math>. The total sum <math> T</math> of all elements of the matrix is at least the number of zeros in this row multiplicated by <math> n - S</math> (because the sum of the elements of a row and a column meeting in a zero is <math> \ge n</math>) plus the number of nonzero elements times <math> S</math> (that is the minimum possible sum), it is,<cmath> z(n - S) + (n - z)S.</cmath>Note that, being <math> z \ge n - S</math> and <math> n - S \ge S</math>, we can put <math> z - 1</math> instead of <math> z</math> and <math> n - z + 1</math> instead of <math> n - z</math> until we get <math> z = n - S</math>, what makes the sum become smaller. So we have<cmath> T \ge (n - S)^2 + S^2 \ge 2(\frac{n - S + S}{2})^2 = \frac{n^2}{2}</cmath>by AM - QM inequality.
 +
 +
The above solution was posted and copyrighted by Renan. The original thread for this problem can be found here: [https://aops.com/community/p1074433]
 +
 +
==Solution 2==
 +
Denote <math>\ell_i,c_i</math> the <math>i</math>th line and column and <math>s(\ell_i), s(c_i)</math> the sum of the elements on that row. Let <math>M=\max_{\sigma \in S_n} | \{ 1\le i\le n| a_{i\sigma(i)}=0\} |</math>. For each permutation <math>\sigma\in S_n</math>, assign to it the number<cmath>\displaystyle\sum\limits_{a_{i\sigma(i)=0}} \left ( s(\ell_i)+s(c_{\sigma(i)}) \right  )</cmath>Now pick a permutation <math>\sigma</math> such that it generates <math>M</math> and its assigned number is minimal. Suppose wlog that <math>\{ 1\le i\le n| a_{i\sigma(i)}=0\}=\{1,2,..,k\}</math>. If <math>k=n</math>, we are done as twice the sum of all elements is<cmath>\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</cmath>
 +
So suppose <math>k<n</math> and look at a <math>j</math> such that <math>k+1\le j\le n</math>. By the maximality of <math>M</math>, <math>\ell_j</math> can have <math>0</math> only on the columns <math>\sigma(1),...,\sigma(k)</math>. Note that if <math>\ell_j</math> has a <math>0</math> on <math>c_{\sigma(r)}</math> with <math>r\le k</math>, i.e. <math>a_{j\sigma(r)}=0</math>, by the minimality of the assigned number of <math>\sigma</math>, we have that <math>s(\ell_j)\ge s(\ell_r)</math>. However, if the column <math>c_{\sigma(j)}</math> has a <math>0</math> on <math>\ell_r</math>, i.e. <math>a_{r\sigma(j)}=0</math>, by the same argument we have <math>s(c_\sigma(j))\ge s(c_\sigma(r))</math>, hence <math>s(\ell_j)+s(c_{\sigma(j)})\ge s(r)+s(c_{\sigma(r)})\ge n</math>.
 +
 +
Suppose that <math>0</math> appears exactly <math>t</math> times on <math>\ell_j</math>. This means that <math>s(\ell_j)\ge n-t</math>. Suppose that the <math>0</math>s of <math>\ell_j</math> appear on the columns <math>c_{\sigma(i_1)},...,c_{\sigma(i_t)}</math>. We have seen earlier that if <math>c_\sigma(j)</math> has a <math>0</math> on <math>i_1,..,i_t</math> we have that <math>s(\ell_j)+s(c_{\sigma(j)})\ge n</math>. So suppose that it doesn't have <math>0</math> on these lines. However, <math>c_{\sigma(j)}</math> has <math>0</math>s only on the lines <math>\ell_1,..,\ell_k</math> by the maximality of <math>M</math>, hence <math>c_{\sigma(j)}</math> has at most <math>k-t</math> zeroes, so <math>s(c_{\sigma(j)})\ge n-k+t</math>. We thus infer that<cmath>s(\ell_j)+s(c_{\sigma(j)})\ge (n-t)+(n-k+t)=2n-k\ge n</cmath>so <math>s(\ell_j)+s(c_{\sigma(j)})\ge n,\ \forall j\ge k+1</math>. By the hypothesis this is also true for <math>j\le k</math> so summing over all values of <math>j</math> we get that the sum is at least <math>\dfrac{n^2}{2}</math>.
 +
 +
The above solution was posted and copyrighted by Aiscrim. The original thread for this problem can be found here: [https://aops.com/community/p5910485]
 +
 +
==Solution 3==
 +
If the main diagonal contains all zeroes, we can immediately deduce from the condition that the sum <math>S</math> of the elements is at least <math>n^2/2</math>. 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 <math>k</math>. (If there is no such subset, <math>S\ge n^2</math>.)
 +
 +
Since the condition is invariant under the operation of switching rows or columns, we may rearrange the matrix such that these <math>k</math> entries are on the main diagonal of the matrix, i.e. <math>a_{11}=a_{22}=\dots=a_{kk}=0</math>. Let <math>X=\sum_{1\le i,j\le k}a_{ij}</math>, <math>Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij}</math> and <math>Z=\sum_{k<i,j\le n}a_{ij}</math>. Then applying the condition to <math>a_{11},\dots,a_{kk}</math>, we get <math>2X+Y\ge kn</math>.
 +
 +
If <math>i\le k<j</math>, then if <math>a_{ij}=a_{ji}=0</math>, then we may toss <math>a_{ii}</math> out of our set and replace it with <math>a_{ij}</math> and <math>a_{ji}</math>, to form a larger feasible set of elements, contradiction. Consequently, <math>a_{ij}+a_{ji}\ge 1</math> for <math>i\le k<j</math>, which upon summation yields <math>Y\ge k(n-k)</math>. Finally, <math>Z\ge (n-k)^2</math>, trivially. Therefore,
 +
<cmath>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.</cmath>
 +
 +
The above solution was posted and copyrighted by randomusername. The original thread for this problem can be found here: [https://aops.com/community/p5612817]
 +
 +
== See Also == {{IMO box|year=1971|num-b=5|after=Last Question}}

Revision as of 14:14, 29 January 2021

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]

See Also

1971 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1971_IMO_Problems/Problem_6&oldid=143820"