2006 Canadian MO Problems/Problem 3

From AoPSWiki

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