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.
Problem
Source: 2023 Hong Kong TST 3 (CHKMO)
Tags: combinatorics
04.12.2022 05:38
In my opinion very high quality. Color the grid in a checkerboard pattern. Let a beetle be happy if it is in a black cell whose row has $1012$ black cells, sad if in a black cell whose row has $1011$ black cells. A beetle in a black cell must alternate between happy and sad every two moves, so we can have at most $1011^2\cdot 2$ black beetles if the problem condition is not satisfied. Similarly, we can have $1011^2\cdot 2$ white beetles, and thus at most $2022^2$ beetles. $2022^2$ is not enough for the problem condition, consider a $2022\cdot 2022$ subgrid with all of them beetles as the starting positions.
04.08.2024 02:24
This is also Dutch TST 2024 3.1.
08.10.2024 06:20
PikaNiko wrote: 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. What if 2023 is replaced with an even number?
26.01.2025 23:36
shanelin-sigma wrote: What if 2023 is replaced with an even number? Then the answer is just $n^2$, right? Every square can have a beetle and they just move in $2 \times 2$ cycles...