Imagine a $9 \times 9$ square array of pigeonholes, with one pigeon in each pigeonhole. Suppose that all at once, all the pigeons move up, down, left, or right by one hole. (The pigeons on the edges are not allowed to move out of the array.) Show that some pigeonhole winds up with two pigeons in it.
Let each side of the square be n. There are $n^2$ pigeons and pigeonholes. If the pigeons are shifted in any direction, then there will be n empty pigeonholes on the side opposite to the direction. Furthermore, now $n^2$ pigeons are trying to fit into $n^2 – n$ pigeonholes. We can invoke the pigeon hole principle as follows: Let the entire set of pigeons be $X$ and the set of pigeonholes to be populated after the shift be $Y$. For $X$ and $Y$ and for some integer $k$, if $X > k Y$, and $f X: \to Y$, then $f(x) = \ldots = f(x {\rm till\ index}\ k+1)$.
So, $81 > 72 k$ which means $k > 1.125$ which means $k = 2$. This means that there are at least $3$ instances with $2$ pigeons in it.
Now intuitively I know there ought to be $9$ instances. Where did I go wrong? Forgive me if I have butchered the whole thing. I am new to this type of math.
Best Answer
A hint: Color the $9^2$ squares checkerboard like!