James Tanton (@jamestanton) tweeted the following problem:

“25 people stand in a 5×5 grid of squares,1 per cell. At blow of whistle each is to take one step L, R ,U or D to a new cell, 1 per cell. How?”

The problem does not state the grid is in a plane, but if, for example, it were on a cylinder or a torus then everyone could just move left, so that would easily solve the problem.

Let’s look at a possibly easier version of the problem using a 3 x 3 gird:

Here the columns are labeled A, B, C and the rows labeled 1, 2, 3.

The person at B2 has to move somewhere – so let’s assume that person moves to B1; the other cases will be dealt with in an exactly similar way. Now the person at B1 has to move either to A1 or to C1. Let’s assume it’s to A1: the other case is dealt with similarly.

Now the person at A1 can only move to A2. What about the person at C1? That person can only move to C2. But someone has to move to C1, and the only person who can now do that is at C2, so C1 and C2 swap places. Now the person at C3 has to move to B3, and there is no-one who can move to C3, since C2 has already moved to C1.

In other words, on a 3 x 3 grid, it is not possible to move the 9 people up, down, left or right, so that each moves to a new square, occupied by only 1 person.

This reasoning applied to a 5 x 5 grid would lead to many more possibilities.

When we get into this situation of having to consider many branching possibilities, one trick to help us is to put some extra structure on the problem. This extra structure cannot change the problem statement, but can add a dimension, such as color, that allows us to see more clearly what can and cannot happen.

So let’s color a 5 x 5 grid as follows:

Every person is on either a red or a yellow square.

When a person moves they move to a square of a different color.

There are 13 red squares.

Each of the 13 people on these red squares will move to a yellow square.

But there are only 12 yellow squares.

So 2 people on a red square before the whistle blows will have to occupy the same yellow square after they move.

So the proposed move is not possible.

This is an example of Dirichlet’s pigeon hole principle.

The added coloration – not originally part of the problem – allows us to see finer detail through the colored lens, and allows us to solve the problem relatively easily.

A lot of mathematical problem solving is like this: finding extra structure that adds fine detail, so allowing us to more easily solve a problem.

Now that we can see what happens when we color the 5 x 5 grid we can also see that the number 5 is not important; what is important is that 5 is odd. So the same conclusion would apply to a (2n+1) x (2n+1) grid.

Of course on an even grid – a 2n x 2n grid – we can move in 2 x2 , 4 x 4, 6 x 6 … circles, so it IS possible for the people to move on a 2n x 2n grid.

Postscript

James Tanton shows another use of Dirichlet’s pigeon-hole principle to show that some power of 3 must end in the digits 01.

He also gives an answer to his own problem analyzed in this post.