Maths Olympiad Prep

Library / /5 of 6

Number theory Difficulty 6.5 National olympiad Prove it Brazil

Providence Ave. has infinitely many traffic lights, all equally spaced and synchronized. The distance between any two consecutive ones is 15001500 m. The traffic lights stay green 1.51.5 minute, red 11 minute, then green again 1.51.5 minute, and so on. Suppose that a car is passing through Providence Ave. at constant speed, equal to vv m/s. For which values for vv is it possible for the car to pass through an arbitrarily large number of traffic lights without stopping?

Solution

Suppose that at instant 00 the traffic lights turn green and the car passes through the first light at instant t00t_0 \ge 0 (time is measured in seconds). The traffic lights will stay green between the time instants 150k+90150k + 90 and 150(k+1)150(k+1), for each integer kk. The car will pass through the lights at the instants t0+1500vrt_0 + \frac{1500}{v} r, for each nonnegative integer rr.

Therefore, a necessary and sufficient condition for a non-stopping trip is that, for every integer rr, t0150+10v\frac{t_0}{150} + \frac{10}{v} equals an integer plus a number between 00 and 35\frac{3}{5}. This is clearly possible if 10v\frac{10}{v} is an integer (with any t0t_0 between 00 and 9090) or if 10v\frac{10}{v} is half of an odd integer (with any t0t_0 between 00 and 1515).

Let's show that these are the only possible situations. If 10v\frac{10}{v} is irrational then by Kronecker theorem the fractional part of t0150+10v\frac{t_0}{150} + \frac{10}{v} is dense in (0,1)(0, 1) and thus admits values between 35\frac{3}{5} and 11. If 10v\frac{10}{v}, say, 10v=pq\frac{10}{v} = \frac{p}{q}, gcd(p,q)=1\gcd(p, q) = 1, then the fractional part of 10v\frac{10}{v} is prq\frac{pr}{q} takes all values of the form sq\frac{s}{q}, 0sq10 \le s \le q-1 (for instance, consider r=sp1modqr = s \cdot p^{-1} \mod q). So consecutive values of the fractional part of t0150+10v\frac{t_0}{150} + \frac{10}{v} are 1q\frac{1}{q} apart; the fractional part of t0150+10v\frac{t_0}{150} + \frac{10}{v} takes values between 35\frac{3}{5} and 11 if 1r135    r3\frac{1}{r} \le 1 - \frac{3}{5} \iff r \ge 3. Thus r2r \le 2, that is, 10v\frac{10}{v} is an integer or half of an odd integer.

We conclude that the possible values for the speed of the car are 20k\frac{20}{k} m/s, for every positive integer kk.

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 and solution reproduced as published; topic and difficulty added by this site.