Difference between revisions of "2006 Canadian MO Problems/Problem 3"
(→Solution) |
|||
| Line 6: | Line 6: | ||
==Solution== | ==Solution== | ||
Assume that <math>m</math> does not equal <math>n</math>. WLOG, m < n. Now we proceed by strong induction. We will assume that the statement is true if a < m and b < n. The base case, where either m or n is 1, is clearly true. Consider the bipartite graph between the set of rows and the set of column, with an edge between a row and a column if they intersect in a positive element. | Assume that <math>m</math> does not equal <math>n</math>. WLOG, m < n. Now we proceed by strong induction. We will assume that the statement is true if a < m and b < n. The base case, where either m or n is 1, is clearly true. Consider the bipartite graph between the set of rows and the set of column, with an edge between a row and a column if they intersect in a positive element. | ||
| − | Now, we invoke the Marriage Lemma. Consider any subset S of the rows, and the set C of columns that have an edge between the column and a member of S. If |C| <math>\ge</math> |S| for all such sets S, then there exists <math>V_1, V_2,... V_m</math> such that they are all positive and no two are in the same row or column, and adding them all up, we get that the sum of the numbers of all the rows is the same as the sum of part of the columns, which imply that there are columns with only 0s, a contradiction. So there exist S such that |S| > |C|. We apply the inductive hypothesis to get that this is impossible. | + | Now, we invoke the Marriage Lemma. Consider any subset S of the rows, and the set C of columns that have an edge between the |
| + | |||
| + | column and a member of S. If |C| <math>\ge</math> |S| for all such sets S, then there exists <math>V_1, V_2,... V_m</math> such that they are all | ||
| + | |||
| + | positive and no two are in the same row or column, and adding them all up, we get that the sum of the numbers of all the rows is | ||
| + | |||
| + | the same as the sum of part of the columns, which imply that there are columns with only 0s, a contradiction. So there exist S | ||
| + | |||
| + | such that |S| > |C|. We apply the inductive hypothesis to get that this is impossible. | ||
==See also== | ==See also== | ||
Revision as of 12:43, 15 August 2008
Problem
In a rectangular array of nonnegative real numbers with m rows and n columns, each row and each column contains at least one positive element. Moreover, if a row and a column intersect in a positive element, then the sums of their elements are the same. Prove that m = n.
Solution
Assume thatdoes not equal
. WLOG, m < n. Now we proceed by strong induction. We will assume that the statement is true if a < m and b < n. The base case, where either m or n is 1, is clearly true. Consider the bipartite graph between the set of rows and the set of column, with an edge between a row and a column if they intersect in a positive element. Now, we invoke the Marriage Lemma. Consider any subset S of the rows, and the set C of columns that have an edge between the
does not equal 
. WLOG, m < n. Now we proceed by strong induction. We will assume that the statement is true if a < m and b < n. The base case, where either m or n is 1, is clearly true. Consider the bipartite graph between the set of rows and the set of column, with an edge between a row and a column if they intersect in a positive element.
Now, we invoke the Marriage Lemma. Consider any subset S of the rows, and the set C of columns that have an edge between the
column and a member of S. If |C| 
|S| for all such sets S, then there exists 
such that they are all
positive and no two are in the same row or column, and adding them all up, we get that the sum of the numbers of all the rows is
the same as the sum of part of the columns, which imply that there are columns with only 0s, a contradiction. So there exist S
such that |S| > |C|. We apply the inductive hypothesis to get that this is impossible.
See also
| 2006 Canadian MO (Problems) | ||
| Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 | Followed by Problem 4 |
