HMMT-Feb 2011 gen, Problem 27

Alice and Bob play a game in which two thousand and eleven $2011 \times 2011$ grids are distributed between the two of them, 1 to Bob, and the other 2010 to Alice. They go behind closed doors and fill their $\operatorname{grid}(\mathrm{s})$ with the numbers $1,2, \ldots, 2011^{2}$ so that the numbers across rows (left-to-right) and down columns (top-to-bottom) are strictly increasing. No two of Alice's grids may be filled identically. After the grids are filled, Bob is allowed to look at Alice's grids and then swap numbers on his own grid, two at a time, as long as the numbering remains legal (i.e. increasing across rows and down columns) after each swap. When he is done swapping, a grid of Alice's is selected at random. If there exist two integers in the same column of this grid that occur in the same row of Bob's grid, Bob wins. Otherwise, Alice wins. If Bob selects his initial grid optimally, what is the maximum number of swaps that Bob may need in order to guarantee victory?

Solution: Consider the grid whose entries in the $j$ th row are, in order, $2011 j-2010,2011 j-2009, \ldots, 2011 j$. Call this grid $A_{0}$. For $k=1,2 \ldots, 2010$, let grid $A_{k}$ be the grid obtained from $A_{0}$ by swapping the rightmost entry of the $k$ th row with the leftmost entry of the $k+1$ st row. We claim that if $A \in\left\{A_{0}, A_{1}, \ldots, A_{2010}\right\}$, then given any legally numbered grid $B$ such that $A$ and $B$ differ in at least one entry, there exist two integers in the same column of $B$ that occur in the same row of $A$. We first consider $A_{0}$. Assume for the sake of contradiction $B$ is a legally numbered grid distinct from $A_{0}$, such that there do not exist two integers in the same column of $B$ that occur in the same row of $A_{0}$. Since the numbers $1,2, \ldots, 2011$ occur in the same row of $A_{0}$, they must all occur in different columns of $B$. Clearly 1 is the leftmost entry in $B$ 's first row. Let $m$ be the smallest number that does not occur in the first row of $B$. Since each row is in order, $m$ must be the first entry in its row. But then 1 and $m$ are in the same column of $B$, a contradiction. It follows that the numbers $1,2, \ldots, 2011$ all occur in the first row of $B$. Proceeding by induction, $2011 j-2010,2011 j-2009, \ldots, 2011 j$ must all occur in the $j$ th row of $B$ for all $1 \leq j \leq 2011$. Since $A_{0}$ is the only legally numbered grid satsifying this condition, we have reached the desired contradiction. Now note that if $A \in\left\{A_{1}, \ldots, A_{2010}\right\}$, there exist two integers in the same column of $A_{0}$ that occur in the same row of $A$. In particular, if $A=A_{k}$ and $1 \leq k \leq 2010$, then the integers $2011 k-2010$ and $2011 k+1$ occur in the same column of $A_{0}$ and in the same row of $A_{k}$. Therefore, it suffices to show that for all $1 \leq k \leq 2010$, there is no legally numbered grid $B$ distinct from $A_{k}$ and $A_{0}$ such that there do not exist two integers in the same column of $B$ that occur in the same row of $A_{0}$. Assume for the sake of contradiction that there does exist such a grid $B$. By the same logic as above, applied to the first $k-1$ rows and applied backwards to the last $2010-k-1$ rows, we see that $B$ may only differ from $A_{k}$ in the $k$ th and $k+1$ st rows. However, there are only two legally numbered grids that are identical to $A_{k}$ outside of rows $k$ and $k+1$, namely $A_{0}$ and $A_{k}$. This proves the claim. It remains only to note that, by the pigeonhole principle, if one of Alice's grids is $A_{0}$, then there exists a positive integer $k, 1 \leq k \leq 2010$, such that $A_{k}$ is not one of the Alice's grids. Therefore, if Bob sets his initial grid to be $A_{0}$, he will require only one swap to switch his grid to $A_{k}$ after examining Alice's grids. If $A_{0}$ is not among Alice's grids, then if Bob sets his initial grid to be $A_{0}$, he will not in fact require any swaps at all. Algebra \& Combinatorics Individual Test $\fbox{1}$.

Answer: 1