Olympiad Maths Prep

Track / Stage 7 / 89 of 300 #1489 of 2000

Problem 1489

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.1 Find the answer

There are three flies of negligible size that start at the same position on a circular track with circumference 1000 meters. They fly clockwise at speeds of 2, 6, and kk meters per second, respectively, where kk is some positive integer with 7k20137\le k \le 2013. Suppose that at some point in time, all three flies meet at a location different from their starting point. How many possible values of kk are there?

[i]Ray Li[/i]

Official solution

1. We need to find the values of k k such that the three flies meet at a location different from their starting point. The flies travel at speeds of 2, 6, and k k meters per second, respectively, on a circular track with a circumference of 1000 meters.

2. Let t t be the time in seconds when the flies meet again at a location different from their starting point. The positions of the flies at time t t can be described by the following congruences:
2t6tkt(mod1000) 2t \equiv 6t \equiv kt \pmod{1000}

3. For the flies to meet at the same point, the positions must be congruent modulo 1000. This gives us the system of congruences:
2t6t(mod1000) 2t \equiv 6t \pmod{1000}
6tkt(mod1000) 6t \equiv kt \pmod{1000}

4. From the first congruence, we have:
2t6t(mod1000)    4t0(mod1000)    t0(mod250) 2t \equiv 6t \pmod{1000} \implies 4t \equiv 0 \pmod{1000} \implies t \equiv 0 \pmod{250}
This implies that t t must be a multiple of 250.

5. From the second congruence, we have:
6tkt(mod1000)    t(k6)0(mod1000) 6t \equiv kt \pmod{1000} \implies t(k - 6) \equiv 0 \pmod{1000}
Since t0(mod250) t \equiv 0 \pmod{250} , we can write t=250m t = 250m for some integer m m . Substituting this into the congruence, we get:
250m(k6)0(mod1000) 250m(k - 6) \equiv 0 \pmod{1000}
Dividing both sides by 250, we obtain:
m(k6)0(mod4) m(k - 6) \equiv 0 \pmod{4}

6. For this congruence to hold for any integer m m , k6 k - 6 must be a multiple of 4. Therefore, we can write:
k6=4n    k=4n+6 k - 6 = 4n \implies k = 4n + 6
for some integer n n .

7. Given the constraint 7k2013 7 \le k \le 2013 , we substitute k=4n+6 k = 4n + 6 and solve for n n :
74n+62013 7 \le 4n + 6 \le 2013
Subtracting 6 from all parts of the inequality:
14n2007 1 \le 4n \le 2007
Dividing by 4:
14n501.75 \frac{1}{4} \le n \le 501.75
Since n n must be an integer, we have:
1n501 1 \le n \le 501

8. Therefore, n n can take any integer value from 1 to 501, inclusive. This gives us 501 possible values for n n , and hence 501 possible values for k k .

The final answer is 501\boxed{501}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.