Problem

Source: 2023 Hong Kong TST 3 (CHKMO)

Tags: combinatorics



Given a $2023 \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. 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.