Valid placement of pebbles on board. Graph theory problem that everyone in my class got wrong Can someone please help with this? I’ve worked on it for a few hours but can’t come up with a proof. Thanks!
Consider a $2n\times 2n$ board (namely a board with $2n$ rows and $2n$ columns for a total of $4n^2$ squares) for $n\ge 1$. We place pebbles on squares (at most one per square). The placement of the pebbles ensures that each column and each row contains exactly $n$ pebbles. Consider the coordinates of a placed pebble to be $x : y$, with $x,y \in\{1,2,\ldots,2n\}$, where $x$ is the row number and $y$ is the column number. Show that for any possible valid placement of the pebbles, there is a subset of $2n$ pebbles such that the row numbers are not the same and the column numbers are not the same for any pair of those $2n$ pebbles.
 A: Here's a combinatorial solution with minimal pre-requisites. Suppose that you're given a configuration $A$ of pebbles. Let the rows and columns of the grid both be numbered from $1$ to $2n$. We define the "configuration obtained by swapping columns $c_1,c_2$" as the configuration obtained on moving every pebble at  $(r,c_1)$ for some $r\in\{1,2,\ldots,2n\}$ to the coordinate $(r,c_2)$ and vice versa simultaneously. On a technical note, we don't require $c_1,c_2$ to be distinct. We define configurations obtained by swapping two rows similarly. Observe that we can find a subset of $2n$ pebbles satisfying the given conditions for the given configuration if and only if we can do the same for a configuration obtained by swapping two rows (analogously columns). Inductively, we can find a subset of $2n$ pebbles satisfying the given conditions for the given configuration if and only if we can do the same for a configuration obtained after a series of row swaps and column swaps.
Suppose that we start with an arbitrary configuration $A$ of pebbles. Let $\mathcal{T}$ denote the collection of all configurations obtained by performing series of row swaps and/or column swaps on $A$. For a configuration $B\in\mathcal{T}$, let $d(B)$ denote the greatest natural number $m\leq2n$ such that $B$ has a pebble on each coordinate in the set $\{(j,j)|j\leq m\}$. Let $A'\in \mathcal{T}$ such that $d(A')\geq d(B)$ for all $B\in \mathcal{T}$. Suppose towards contradiction that $d(A')=m<2n$. Unless otherwise mentioned, we shall henceforth work with the configuration $A'$. If there is a pebble on a coordinate in the set $\{(i,j)|m<i,j\leq2n\}$, then define the configuration obtained by swapping rows $i,m+1$ and then swapping columns $j,m+1$ to be $B_1$. Then, $B_1\in \mathcal{T}$ and $d(B_1)\geq d(A')+1$. This is a contradiction. Hence, at each point in the set $\{(i,j)|m<i,j\leq2n\}$ (Marked with a red fill in fig.), there is no pebble (wrt $A'$). Now, consider the $(m+1)^{st}$ row and column. The $n$ pebbles on the $(m+1)^{st}$ row (resp. column) are present on $n$ coordinates in the set $\{(m+1,j)|j\leq m\}$ (resp. $\{(j,m+1)|j\leq m\}$). So, by pigeon hole principle, there exists $x\in\{1,2,\ldots,m\}$ such that there is a pebble at each of the coordinates $(m+1,x),(x,x)$ and $(x,m+1)$. Define $B_2$ to be the configuration obtained by swapping rows $x,m+1$. Now, $B_2\in \mathcal{C}$ and $d(B_2)\geq d(A')+1$. This is a contradiction. Hence, we conclude that $d(A')=2n$. Then the set of pebbles on $\{(j,j)|j\leq 2n\}$ satisfies the given conditions for the configuration $A'$. Thus, a set of $2n$ pebbles satisfying the given conditions in the configuration $A$ also exists as specified earlier.

