You have a wire (of unit length) with a finite number of ants arbitrarily placed on it, each facing an arbitrary direction to start.
Each ant has negligible size and travels at the same, constant speed along the length of the wire.
When an ant reaches the end of the wire, it turns around instantaneously and continues moving.
If two ants ‘collide’, they both turn around instantaneously and continue moving. After a certain amount of time, the state of the wire with ants is exactly the same as it started, with each ant in its original location facing its original direction.
What is the shortest distance the ants must travel such that a wire with any number of ants in any starting position will have returned to its starting position?
Send your solutions (with proof) to midnight.math@outlook.com. If you are correct, you will be given the highest of accolades: your name mentioned here, next issue.
Correct answers to last month’s puzzle:
Arash Ushani
Thomas Pandolfo
Berit Johnson
(See the solutions at https://franklyspeakingnews.com/node/134)
———————————————————
Solutions:
Berit Johnson
The answer is 2 unit lengths
Consider a wire with a single ant.
Let the wire be aligned with the interval [0,1] and without loss of generality, suppose the ant is at point x and facing the increasing direction. In order to get back to its starting position, the ant must travel 1-x distance to the end of the wire, turn, travel a distance of 1 to the beginning, passing through its starting point but facing the opposite direction, turn, and travel a distance of x to its starting position, for a total distance of 2. We thus have a lower bound on the shortest distance the ants must travel to return to their starting positions.
Now consider a wire with an arbitrary number of ants. Since all ants travel at the same speed and turn instantaneously upon collision, the wire looks as though the ants are effectively passing through one another without interacting, though the identity of the ants may change. Because of this, after the ants have all traveled a distance of two, there will be an ant matching the starting position and direction of every ant in the initial configuration. Because the ants cannot actually pass through one another, the order of the ants must be preserved. Thus, after the ants walk a distance of 2 unit lengths, the configuration of the wire must be identical to its initial configuration. This gives us an upper bound on the shortest distance the ants must travel to return to their starting positions.
Because the upper and lower bounds are equal, the shortest distance the ants must travel such that any configuration of ants will return to its starting position is 2.
<3,
Berit
—
Arash Ushani
We will show that the shortest distance the ants must travel such that a wire with any number of ants in any starting position will have returned to its starting position is 2 wire lengths. We will do so by showing the following two things.
• There exists a configuration (a given number of ants in a given starting location) where the ants will not return to their starting positions until they have traveled a distance of 2 wire lengths.
• In any configuration, after the ants have traveled a distance of 2 wire lengths, they will have returned to their starting positions.
Consider the trivial case where there is one ant traveling along the wire. He travels a distance of x to the end of the wire, turns around and travels a distance of 1 wire length back along the wire to the opposite, and then resumes traveling for a further distance of (1-x). Now, for the first time, he has come back to his starting position. By now, he has traveled a total distance of x + 1 + (1-x) = 2 wire lengths. Therefore, the shortest distance must be at least 2 (since we just demonstrated a configuration where a distance of 2 wire lengths is necessary).
Consider an arbitrary number of ants n in any starting configuration. We can very creatively number these ants from left to right, starting with Ant 1 on the very left, all the way to Ant n on the very right.
Note that the ordering of ants left to right along the wire cannot change. When two ants collide, each turns around instantaneously and starts moving the opposite direction. Never do they move past one another.
Give each ant one of n batons A, B, C, .. etc, such that Ant 1 starts with Baton A, Ant 2 starts with Baton B, etc. Each ant always carries a baton with it along its journey.
When two ants collide, the ants swap batons. For example, consider Ant 1 with Baton A and a Ant 2 with Baton B. When Ant 1 meets Ant 2, Ant 1 gives Ant 2 Baton A, and Ant 2 gives Ant 1 Baton B. After their collision, Ant 1 has Baton B, and Ant 2 has Baton A. Note that each ant always carries a baton.
Consider the movement of the batons. Because each baton is swapped whenever two ants collide and no other time, the only way for a baton to reverse direction is when the ant carrying it reverses direction without colliding, ie, at the end of the wire. Therefore, each baton moves along the wire, being passed off by each successive ant, until it reaches the end of the wire and turns around.
Consider any given baton. It moves along the length of the wire until it reaches the end of the wire. Call this distance x. Then, the baton turns around and travels a distance of 1 wire length until it reaches the other end of the wire. Here, it turns around again. When it has traveled a distance of (1-x) further, it has reached its original starting position (location and direction).
Each baton travels in the described way, and all batons move at the same speed (namely, the speed of the ants). Therefore, all of the batons are back at their starting position at the same time, after they have each traveled a distance of 2 wire lengths (equivalently, after the ants have moved a distance of 2 wire lengths as well, because both ants and batons travel at the same speed).
Consider the batons as a whole at this time. Every baton has returned to its starting location, which means that the order of the batons left to right is the same as it was at the start. Because the order of the ants left to right never changes as shown above, this means the ant which now holds each baton is the same ant that originally held the baton in its starting position.
For example, consider ants 1, 2, 3 and batons A, B, C. Ant 1 starts with Baton A, Ant 2 starts with Baton B, and Ant 3 starts with Baton C. The ants across left to right are always Ant 1, Ant 2, Ant 3. As demonstrated above, after the batons have traveled a distance of 2 wire lengths, they have all returned to their original position, and so their order left to right is Baton A, Baton B, and Baton C. Therefore, Ant 1 must hold Baton A, Ant 2 must hold Baton B, and Ant 3 must hold Baton C.
Because the batons are at their starting positions, and that each ant is holding the baton it started with, that means ant is at the position it started at.
Recall that the speed that a baton travels at is the same speed that an ant travels at. Therefore, after a baton has traveled a distance of 2 wire lengths, so has each ant.
Thus, we have demonstrated that after each ant has traveled a distance of 2 wire lengths, each ant has returned to its original starting position.
We have now shown that a distance of 2 wire lengths is necessary, and that a distance of wire lengths is sufficient. Therefore, we have shown that the shortest distance that the ants must travel to guarantee that any number of ants in any starting position will return to their starting position is 2 wire lengths.
-Arash
