An easy pigeonhole principle problem: Please critique my mathematical reasoning.

Question

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.

Answer 1

A hint: Color the $9^2$ squares checkerboard like!

Answer 2

Hint: This figure suggests why you cannot do it with $9 \times 9$ but (modified) shows you can with $8 \times 8$.

Answer 3

Label each pigeon as $(a,b)$ where $a$ is the column number and $b$ is the row number. Each pigeon must move to a square that has the same column or row number but the row or column number is off by $1$.

So if $(a,b)$ is the square the pigeon start at, and $(a',b')$ is the square they move to, then $a+b = a' + b' \pm 1$. So if $a+b$ is even, then $a'+b'$ is odd, and vice versa.

So all the pigeons with an even sum must move to a square with odd sum and vice versa. As there are $41$ squares with even sums and only $40$ with odd sums we will end up with $41$ pigeons in the $40$ squares with odd sums, and $40$ pigeons in the $41$ squares with even sums.

So at least one of the squares with odd sums will have two pigeons, and at least one of the squares with even sums will be empty.