Larry and Rob are two robots travelling in one car from Argovia to Zillis. Both robots have control over the steering and steer according to the following algorithm: Larry makes a left turn after every kilometer driving from start; Rob makes a right turn after every kilometer driving from start, where and are relatively prime positive integers. In the event of both turns occurring simultaneously, the car will keep going without changing direction. Assume that the ground is flat and the car can move in any direction.
Let the car start from Argovia facing towards Zillis. For which choices of the pair ( ) is the car guaranteed to reach Zillis, regardless of how far it is from Argovia?
Solution
Let Zillis be kilometers away from Argovia, where is a positive real number. For simplicity, we will position Argovia at and Zillis at , so that the car starts out facing east. We will investigate how the car moves around in the period of travelling the first kilometers, the second kilometers, . . ., and so on. We call each period of travelling kilometers a section. It is clear that the car will have identical behavior in every section except the direction of the car at the beginning.
Case 1: . After the first section, the car has made right turns and left turns, which is a net of right turns. Let the displacement vector for the first section be . Since the car has rotated , the displacement vector for the second section will be , which will take the car back to facing east again. We now have our original situation, and the car has certainly never travelled further than kilometers from Argovia. So, the car cannot reach Zillis if it is further apart from Argovia.
Case 2: . After the first section, the car has made a net of 1 right turn. Let the displacement vector for the first section again be . This time the car has rotated clockwise. We can see that the displacements for the second, third and fourth section will be and , respectively, so after four sections the car is back at facing east. Since the car has certainly never travelled further than kilometers from Argovia, the car cannot reach Zillis if it is further apart from Argovia.
Case 3: . An argument similar to that in Case 2 (switching the roles of left and right) shows that the car cannot reach Zillis if it is further apart from Argovia.
Case 4: . The car makes a net turn of after each section, so it must be facing east. We are going to show that, after traversing the first section, the car will be at . It will be useful to interpret the Cartesian plane as the complex plane, i.e. writing for , where . We will denote the -th kilometer of movement by ,
which takes values from the set , depending on the direction. We then just have to show that
which implies that the car will get to Zillis no matter how far it is apart from Argovia.
Case 4a: . First note that for ,
since and are the exact numbers of left and right turns before the st kilometer, respectively. Let and be the remainders of when divided by and , respectively. Then, since
we have and . We therefore have
As and are relatively prime, by Chinese Remainder Theorem, there is a bijection between pairs and the numbers . Hence
as required because .
Case 4b: . In this case, we get
where and for . Then we can proceed analogously to Case 4a to obtain
as required because .
Now clearly the car traverses through all points between and during the first section and, in fact, covers all points between and during the -th section. Hence it will eventually reach for any positive .
To summarize: satisfies the required conditions if and only if