Iranian Combinatorics Olympiad 2021 - Advanced level - Problem 1 - Frogs on the stone

For discussing Olympiad Level Combinatorics problems
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Iranian Combinatorics Olympiad 2021 - Advanced level - Problem 1 - Frogs on the stone

Unread post by Anindya Biswas » Thu Aug 26, 2021 2:55 am

In the lake, there are $23$ stones arranged along a circle. There are $22$ frogs numbered $1,2,\dots,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.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Iranian Combinatorics Olympiad 2021 - Advanced level - Problem 1 - Frogs on the stone

Unread post by Mehrab4226 » Sat Sep 04, 2021 7:56 pm

Let, $k_i$ be the stone on which ith frog was initially sitting on. Let's say all move M times. Then each frog will naturally go from $k_i \to k_i +M$(Mod 23). We can work on (Mod 23)

Now if 2 or more frogs sit on the same stone then we will call one(any) of them 'domain' and the rest 'refugees'. (I know I am bad at making names). It will be sufficient if we prove that at some point there will be at least 5 refugees.

Now, the value of M(the number of moves) is between (1-23) as after 23 moves all will again come at the same initial position. So we only need to think about (1-23) values of M.

Claim-1: Each pair of frogs will have a value M(1-23) such that after M moves that pair will be on the same stone.
Proof:
To make our claim true the congruence must hold in (mod 23) of course.
$k_i+iM \equiv k_j +jM$
Or,$k_i - k_j \equiv (j-i)M$
The second form holds as $(k_i - k_j) \neq 0$ and is in the complete residue class of $23$ and so is $j-i$. So we can find a value M for which the congruence holds. And M will also be in (1-23). Note this holds only because 23 is prime. $\square$

Now, there are $\binom{22}{2}=231$ pairs of frogs. And each pair will have a value M. Since there are 23 different possible values of M(or at least the ones we need to look at, by PHP we get, $\left\lceil \frac{231}{23} \right\rceil = 11$. So 11 pairs must have the same value of M.

Claim-2: There will be at least 5 refugees at some point
Proof:
Let's say after $M_1$ moves [Let $M_1$ be the value of the 11 pairs] 11 of the pairs will sit on the same stone. If there were less than 5 refugees at that time we cannot find 11 pairs who sit on the same stone. A contradiction. So there must be at least 5 refugees at that time.$\square$

So there will be at least 6 stones empty at some point. $\square$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply