Given a square grid, there are beetles on some of the unit squares, with at most one beetle on each unit square. In the first minute, every beetle will move one step to its right or left adjacent square, or to its top or bottom adjacent square. In the second minute, every beetle will move again, only this time, in case the beetle moved right or left in the previous minute, it moves to top or bottom in this minute, and vice versa, and so on. What is the minimum number of beetles on the square grid to ensure that, no matter where the beetles are initially, and how they move in the first minute, but after finitely many minutes, at least two beetles will meet at a certain unit square?
Solution
The answer is .
First we show that is insufficient. Suppose there are beetles in the top left square grid. This square grid can be partitioned into many square grids in the natural way. If the beetles in each square grid move in the anticlockwise direction as shown, then no beetle will ever meet.

Next, suppose there are at least beetles. We label all the unit squares as follows. In the odd rows, we label the unit squares . In the even rows, we label the unit squares . Note that there are unit squares with label .
As there are at least beetles in total, we can always find at least beetles lying in unit squares with the same label by the pigeonhole principle. In each move, either all beetles move in the order or all beetles move in the order . In any case, these beetles must move to unit squares with label simultaneously in a certain move. As there are only unit squares with label , two of the beetles must meet at a certain unit square. This completes the proof.