Show that there is a star for which there are less stars in its column than in its row.

Question

In a table there are n columns and m rows, n > m. Some cells are marked by stars, and in each column there's at least one star. Show that there is a star for which there are less stars in its column than in its row.

Answer 1

First,  

$\underline{Note}$: If the result holds for a matrix $A^{m, m +k}:=B$, it holds for $A^{m, m+k + 1}:=C$, for $k \ge 1$, the same matrix $B$ with a column added.  

This is obvious: there is at least one row-column combination in $B$ where the result holds. Adding one or more stars in a new column cannot change this.  

So, wlog, one can assume in what follows that the matrix is of form $$A \in M^{m, m+1}.$$ Note next that the sum of stars $r_i$ in row $i$ and the sum of stars $r^j$ in column $j$ must satisfy.  $$\sum_{i = 1}^m r_i = \sum_{j=1}^{m+1} r^j \quad (1),$$ and that, by construction, $$r^j \geq 1 \text{ for all j} \quad (2).$$ Now, assume to the contrary that the claim is wrong.  Then  $$r_i \leq r^i \text{ for all i} \quad (3)$$ But then:   $$\begin{align} \sum_{j=1}^{m+1} r^j & = r^{m+1} + \sum_{j=1}^m r^j \\ & \geq r^{m+1} + \sum_{i=1}^m r_i \quad \text{using (3)} \\ & \gt \sum_{i=1}^m r_i \quad \text{using (2), } \\ \end{align}$$ which contradicts (1). So there is at least one $i$ for which (3) is false, which was to be shown. 

Edit (03/04): See Macavity's comment below for how to complete the argument (thank you!).

Answer 2

While completing @gnometorule's argument was easier, I thought the following approach is also worth mentioning:

Let $S(i, j)$ denote a function which gives $1$ if there is a star in cell from column $i$ and row $j$, and $0$ otherwise. Then we have,

$\sum_{i, j} S(i, j) = X$, the total number of stars.

Also if $C_i$ denotes the number of stars in column $i$ and $R_j$ denotes the number of stars in row $j$, we have
$\sum_{i=1}^n C_i = \sum_{j=1}^m R_j = X$

Further, it can be noted that $\sum_j S(i,j) = C_i$ and $\sum_i S(i,j) = R_j$

If all starred cells $(i, j)$ are such that $C_i \ge R_j$, then summing over all cells we have:
$\sum_{i, j} (C_i - R_j) S(i, j) \ge 0$

$\implies \sum_{i, j} C_i S(i, j) \ge \sum_{i, j} R_j S(i, j) $

$\implies \sum_{i} C_i C_i \ge \sum_{j} R_j R_j $

$\implies \sum_{i=1}^n C_i^2 \ge \sum_{j=1}^m R_j^2 $

Now, I believe the above inequality is not possible for such column and row sums, i.e. if:
$0 < C_i \le m$ and $0 \le R_j \le n$ with $n > m$, but have not been able to prove it.