Difference between revisions of "2006 Canadian MO Problems/Problem 3"
m (→See also: ................................................ need to learn to count) |
(→Solution) |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| − | In a rectangular array of nonnegative real numbers with | + | 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== | ==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. | ||
| + | |||
| + | 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== | ||
Latest 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 that 
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 |
