Show that there is a star for which there are less stars in its column than in its row. 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.
 A: 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!).
A: 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.
