Track / Stage 6 / 78 of 400 #1078 of 1964

Problem 1078

National olympiad, first round

Combinatorics Difficulty 6.1 Prove it

Consider a $M \times N$ table (with $M$ rows and $N$ columns), which contains more columns than rows $(N>M)$ . We place stars in some cells of the table, and assume that each row and each column contains at least one star. Show that there exists a cell containing a star such that the number of stars on its row is strictly greater than the number of stars on its column.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

We number all the starred cells $\mathrm{E}_{1}, \mathrm{E}_{2}, \ldots, \mathrm{E}_{\mathrm{p}}$ and for each cell $E_{i}$ we denote $c_{i}$ as the number of starred cells in its column and $l_{i}$ in its row. Suppose by contradiction that for all $i, c_{i} \geqslant l_{i}$ . We will then consider the two sums:

$\sum_{i=1}^{p} \frac{1}{c_{i}} \leqslant \sum_{i=1}^{p} \frac{1}{l_{i}}$

We calculate the first sum according to the columns.

$\sum_{i=1}^{p} \frac{1}{c_{i}}=\sum_{k=1}^{N}\left(\sum_{E_{i} \in k^{\text{th}} \text{ column }} \frac{1}{c_{i}}\right)=\sum_{k=1}^{N} 1=N$

where the penultimate equality follows from the definition of $c_{i}$ and the fact that each column contains at least one star.

Similarly, we calculate the sum of $1 / l_{i}$ , which allows us to write:

$N=\sum_{i=1}^{p} \frac{1}{c_{i}} \leqslant \sum_{i=1}^{p} \frac{1}{l_{i}}=M$

This constitutes the desired contradiction.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.