Maths Olympiad Prep

Library / /86 of 94

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Hong Kong

Given a 2023×20232023 \times 2023 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 20222+1=40884852022^2 + 1 = 4088485.
First we show that 202222022^2 is insufficient. Suppose there are 202222022^2 beetles in the top left 2022×20222022 \times 2022 square grid. This square grid can be partitioned into many 2×22 \times 2 square grids in the natural way. If the beetles in each 2×22 \times 2 square grid move in the anticlockwise direction as shown, then no beetle will ever meet.

Figure 1

Next, suppose there are at least 20222+12022^2 + 1 beetles. We label all the unit squares as follows. In the odd rows, we label the unit squares ABABABABAABABAB\cdots ABA. In the even rows, we label the unit squares CDCDCDCDCCDCDCD\cdots CDC. Note that there are 101121011^2 unit squares with label DD.
As there are at least 20222+12022^2+1 beetles in total, we can always find at least 10112+11011^2+1 beetles lying in unit squares with the same label by the pigeonhole principle. In each move, either all beetles move in the order ABDCAA \to B \to D \to C \to A or all beetles move in the order ACDBAA \to C \to D \to B \to A. In any case, these 10112+11011^2 + 1 beetles must move to unit squares with label DD simultaneously in a certain move. As there are only 101121011^2 unit squares with label DD, two of the beetles must meet at a certain unit square. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.