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!
Best Answer
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$.