Browse · MathNet
PrintXXII OBM
Brazil number theory
Problem
Providence Ave. has infinitely many traffic lights, all equally spaced and synchronized. The distance between any two consecutive ones is m. The traffic lights stay green minute, red minute, then green again minute, and so on. Suppose that a car is passing through Providence Ave. at constant speed, equal to m/s. For which values for is it possible for the car to pass through an arbitrarily large number of traffic lights without stopping?
Solution
Suppose that at instant the traffic lights turn green and the car passes through the first light at instant (time is measured in seconds). The traffic lights will stay green between the time instants and , for each integer . The car will pass through the lights at the instants , for each nonnegative integer .
Therefore, a necessary and sufficient condition for a non-stopping trip is that, for every integer , equals an integer plus a number between and . This is clearly possible if is an integer (with any between and ) or if is half of an odd integer (with any between and ).
Let's show that these are the only possible situations. If is irrational then by Kronecker theorem the fractional part of is dense in and thus admits values between and . If , say, , , then the fractional part of is takes all values of the form , (for instance, consider ). So consecutive values of the fractional part of are apart; the fractional part of takes values between and if . Thus , that is, is an integer or half of an odd integer.
We conclude that the possible values for the speed of the car are m/s, for every positive integer .
Therefore, a necessary and sufficient condition for a non-stopping trip is that, for every integer , equals an integer plus a number between and . This is clearly possible if is an integer (with any between and ) or if is half of an odd integer (with any between and ).
Let's show that these are the only possible situations. If is irrational then by Kronecker theorem the fractional part of is dense in and thus admits values between and . If , say, , , then the fractional part of is takes all values of the form , (for instance, consider ). So consecutive values of the fractional part of are apart; the fractional part of takes values between and if . Thus , that is, is an integer or half of an odd integer.
We conclude that the possible values for the speed of the car are m/s, for every positive integer .
Final answer
All speeds of the form 20/k meters per second for positive integers k.
Techniques
Inverses mod n