Given an $m \times n$ table, where $m<n$, each cell is colored Red or Blue. Suppose that every column contains at least one Red cell. Prove that there is a Red cell such that the number of Red cells in its row is larger than the number of red cells in it column.
I think this involves the pigeonhole principle, but I'm just not sure how to go about it. Any tips or help is appreciated. Thanks!
On
Let $R_i$ be the number of red cells in row $i$ and $R_j$ the number of red cells in column $j$.
Now suppose the negation of the statement were true. Then, for every red cell, if its location on the grid is $(i, j)$, $R_i \leq R_j$.
Form the sequence $(i_j)$ by choosing a row index for each column in the following way: if the column $j$ contains a red cell at $(i, j)$ whose row index, $i$, is not already in the sequence, choose $i$. If all of the row indices corresponding to cells in the column $j$ are already in the sequence, choose any $i$. This ensures that for every row containing at least one red cell, its index will appear in the sequence. Furthermore, since $n>m$, there is a row containing at least one red cell whose index will appear more than once in the sequence.
Since we assumed that $R_i \leq R_j$ for all red cells $(i, j)$, the total number of red cells must then satisfy:
$R_{i_1} + R_{i_2}+...+R_{i_n} \leq R_{tot}$
where we have counted the total red cells by the column in which they appear. But if we count the cells by the row in which they appear:
$R_1 + R_2 + ... + R_m = R_{tot}$
But since at least one index corresponding to a row with at least one red cell will appear twice in the sequence $(i_j)$, $R_{p_0}+R_{p_1}+...+R_{p_k} \leq 0$ for some indices $p_l$ such that $R_{p_l}$ is at least one, a contradiction.
Note that in the last part, we have removed the terms corresponding to rows with no red cells, if there are any, which leaves the sum unchanged.
Let $X$ be the set of rows, $Y$ the set of columns: $|X|=m\lt n=|Y|$.
Let $E\subseteq X\times Y$ be the set of red cells.
For $x\in X$ let $d(x)=|\{y\in Y:(x,y)\in E\}|$, the number of red cells in row $x$.
For $y\in Y$ let $d(y)=|\{x\in X:(x,y)\in E\}|$, the number of red cells in column $y$.
Let $X_0=\{x\in X:d(x)\ne0\}\subseteq X$ and $Y_0=\{y\in Y:d(y)\ne0\}=Y$.
I have to prove that $d(x)\gt d(y)$ for some $(x,y)\in E$. Assume for a contradiction that $d(x)\le d(y)$ whenever $(x,y)\in E$; in other words, $\frac1{d(y)}\le\frac1{d(x)}$ whenever $(x,y)\in E$. (Note that $d(x),d(y)\gt0$ when $(x,y)\in E$.) Then $$\sum_{(x,y)\in E}\frac1{d(y)}\le\sum_{(x,y)\in E}\frac1{d(x)}.$$ Since $$\sum_{(x,y)\in E}\frac1{d(x)}=\sum_{x\in X_0}\frac{d(x)}{d(x)}=|X_0|\le|X|=m$$ and $$\sum_{(x,y)\in E}\frac1{d(y)}=\sum_{y\in Y_0}\frac{d(y)}{d(y)}=|Y_0|=|Y|=n$$ it follows that $n\le m$, contradiction the assumption that $m\lt n$.
Remark. This puzzle is a lemma from matching theory in disguise. Namely, this is how you show that, if $G$ is a bipartite graph with partite sets $X,Y$, if there are no isolated vertices in $Y$, and if $\deg(x)\le\deg(y)$ whenever $x\in X$, $y\in Y$, and $(x,y)\in E(G)$, then thee is a matching in $G$ which covers $Y$.