In the lake, there are $23$ stones arranged along a circle. There are $22$ frogs numbered $1, 2, \cdots, 22$ (each number appears once). Initially, each frog randomly sits on a stone (several frogs might sit on the same stone). Every minute, all frogs jump at the same time as follows: the frog number $i$ jumps $i$ stones forward in the clockwise direction. (In particular, the frog number $22$ jumps $1$ stone in the counter-clockwise direction.) Prove that at some point, at least $6$ stones will be empty.
Problem
Source:
Tags: combinatorics
Tintarn
12.08.2021 16:28
The game is periodic with $23$ rounds. Since $23$ is a prime, every two frogs sit on the same stone exactly once in these $23$ rounds.
So there must be one round where this is true for at least $\frac{\binom{22}{2}}{23}>10$, hence at least $11$ of these pairs.
Now the rest is simple: We claim that in this round at least $6$ stones will be empty.
Indeed, suppose that $18$ stones have at least one frog. So we have 4 left-over frogs which we can distribute in four different ways:
$5,1,1,1,\dots$.
$4,2,1,1,\dots$.
$3,3,1,1,\dots$.
$3,2,2,1,\dots$.
In each of the four cases, there are only $10, 7, 6, 5$ pairs of frogs sitting on the same stone, contradicting our assumption of having at least $11$ "collisions".
wassupevery1
12.08.2021 20:02
Let $a_1, a_2, \ldots, a_{22}$ be the position of frogs $1, 2, \ldots, 22$, where $a_1, a_2, \ldots, a_{22}$ are taken from $\{1, 2, \ldots, 22, 23 \}.$ We claim that there exists a positive integer $k$ such that $a_1+k, a_2+2k, \ldots, a_{22}+22k$ produce at most $23-6=17$ remainders, hence implying the conclusion.
We say that two frogs $i, j$ collide if they stand on the same stone.
Note that for any pairs of integers $i \neq j$, there is exactly one positive integer $k \in \{1, 2, \ldots, 23 \}$ such that $a_i+ik=a_j+jk \pmod {23},$ hence for $1 \leq k \leq 23$, there are $\binom{22}{2}=231$ collisions.
Therefore we can guarantee that there is a positive integer $k$ such that at least $11$ collisions.
If for that integer $k$, there are at least $18$ remainders, we can see (by case bash) that there can be at most $\binom{5}{2}=10$ collisions, contradiction. Proof is complete.
The idea is somewhat the same as 2018 USAJMO Problem 5/ 2018 USAMO Problem 4.
sami1618
30.09.2024 02:52
Work in $\mathbb{Z}_{23}$ and let $t$ be the number of minutes that passed. Label the frogs $F_1,F_2,\dots,F_{22}$ and let each frogs position be given by $f_i+ti$, where $f_i$ is its starting position. Call a pair of frogs a good pair if they are sitting on the same stone at a certain time. Claim: For any two frogs, there exists a $t$, $0\leq t \leq 22$, such that they are a good pair at time $t$ It suffices to have that $f_i+ti= f_j+tj$, but as $i\neq j$ this will have a solution for $0\leq t \leq 22$. Now there must exist a $t$, $0\leq t\leq 22$, such that the number of good pairs at time $t$ is at least $$\frac{1}{23}\binom{22}{2}=\frac{231}{23}$$But as this is non integral it has to be at least $11$. Now assume FTSOC that only $5$ stones were empty (or less). Then first drop frogs on the remaining $18$ stones, so far creating no good pairs. Then drop the remaining $4$ frogs one by one. The first will create at most $1$ good pair, the second at most $2$, and so on. As $1+2+3+4<11$, we have a contradiction.
AshAuktober
14.11.2024 08:29
Note that there are exactly $\binom{22}{2}$ pairs of frogs on the same stone in total. At any instant, if there are at least $18$ occupied stones, then there are at most $\binom{5}{2} = 10$ pairs of coinciding frogs. This leads to $230$ pairs in total. But $230 < 231 = \binom{22}{2}$, contradiction. $\square$