4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I read the questions as saying they each move independently in some direction (i.e. not all in the same direction, which is what it looks to me like you're assuming). Apologies if I'm misreading your argument. $\endgroup$ – user113102 Apr 1 at 19:12
  • 1
    $\begingroup$ Also another remark, your proof will somehow need to use the fact that the square has odd-length sides right? If it had even length sides, a covering of the large square by 2x2 squares which are then "rotated" gives a counterexample to the analogous questions for even-length sides. $\endgroup$ – user113102 Apr 1 at 19:18
  • $\begingroup$ "If the pigeons are shifted in any direction, then there will be n empty pigeonholes on the side opposite to the direction." But the pigeons don't have to all be shifted in the same direction. The $n$ pigeons on the edge can move in, while all the pigeons next to them can move to the edge. In fact just have every pigeon pick one neighbor and have them switch places.... oh, wait... there are an odd number of pigeons.... $\endgroup$ – fleablood Apr 1 at 20:04
15
+50
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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

enter image description here

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have misinterpreted the question. Thank you for your help! $\endgroup$ – SensualSensuality Apr 2 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.