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"

(Created page with "Let A = (aij), where i, j = 1, 2, ... , n, be a square matrix with all aij non-negative integers. For each i, j such that aij = 0, the sum of the elements in the ith row and t...")
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
Let A = (aij), where i, j = 1, 2, ... , n, be a square matrix with all aij non-negative integers. For each i, j such that aij = 0, the sum of the elements in the ith row and the jth column is at least n. Prove that the sum of all the elements in the matrix is at least n2/2.
+
==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>.
 +
 
 +
==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}}

Latest revision as of 13: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"