Maths Olympiad Prep

Library / /356 of 462

Number theory Difficulty 6.5 National Olympiad Prove it Ireland

A pond has 20202020 lily pads arranged in a circle. At time zero, two frogs (Anthony and Clare) share the same lily pad. Every minute, Anthony jumps over 9999 lily pads in an anti-clockwise direction, to land on a pad 100100 removed from where the jump started. At the same time, Clare jumps over 100100 lily pads in a clockwise direction, to land on a pad 101101 removed from where the jump started.
What is the first time that Anthony and Clare are again within five lily pads of each other?

Solution

Solution 1. As we are concerned with the relative position of Anthony and Clare, the answer is unchanged if Anthony remains stationary and Clare jumps 201201 lily pads to the right.
When does Clare next come close to Anthony? She makes one circuit of the pond after roughly 2020/201102020/201 \approx 10 jumps, but in fact after those 1010 jumps she has travelled 20102010 pads so is 1010 lily pads short of Anthony. After 2020 jumps, she is 2020 lily pads short of Anthony, and so on. Each circuit her shortfall relative to Anthony goes up by 1010, until after 100100 jumps she is 100100 short of Anthony. But then after one more jump (101101 in total) she is 101101 lily pads past Anthony.

And so it goes on; with each further loop Clare overshoots Anthony by 1010 pads less than the previous loop; after 111111 jumps, Clare overshoots Anthony by 9191; after 121121 Clare overshoots Anthony by 8181 and so on until after 201201 jumps, Clare overshoots Anthony by 11 and they are on adjacent pads. Although the question asks for the first time Clare and Anthony are five or fewer pads apart, it turns out that the first time they are in this range, they are one pad apart.

Solution 2. After tt jumps, Clare is 201t201t pads clockwise from Anthony, measured modulo 20202020, so we have to solve:
201t{5,4,3,2,1,0,1,2,3,4,5}(mod2020). 201t \in \{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5\} \pmod{2020}.
We notice that 2012=404011(mod2020)201^2 = 40401 \equiv 1 \pmod{2020} and so we can multiply both sides by 201201, to give:
t{1005,804,603,402,201,0,201,402,603,804,1005}(mod2020) t \in \{-1005, -804, -603, -402, -201, 0, 201, 402, 603, 804, 1005\} \pmod{2020}
The smallest t>0t > 0 in this set is t=201t = 201 and this solves the problem.

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.