Wednesday 20 May 2020

Beetles around a circle

I recently came across a lovely combinatorial problem in R J Lipton's blog Gödel's lost letter and P=NP. You can read about it in that blog, together with its provenance, and its beautiful solution. However, in order for my comments on it to make any sense I need to recap the problem and its solution.

9 beetles are placed around a circle and the distances between them are the prime numbers 2, 3, 5, 7, 11, 13, 17, 19, 23. They start walking around the circle at the speed of 1 unit of distance per second but their directions are chosen randomly. When two beetles collide they reverse their directions but maintain their same speed. After 50 seconds and many collisions what are the distances between the beetles?

The remarkable answer is that the set of distances is still that same set of prime numbers.

The red herring in the problem is that the presence of prime numbers is irrelevant: no matter what the initial distances are the set of distances returns to that initial set after 50 seconds. The only thing that matters is that the sum of the distances is 100 which is therefore the length of the circle's circumference. The key insight is to imagine that each beetle carries a flag and whenever two beetles collide they exchange flags. Thus each flag continues to travel in the same direction it began with and so, after 50 seconds, it has travelled 50 units of distance and therefore has travelled halfway around the circle to the antipodal point. Since the final position of the flags is a reflection in a centre point mirror of the initial position, the set of distances between the flags is is the same as the original set of distances. However every flag has a beetle on it and therefore this is also true of the set of distances between the beetles.

Of course after 100 secs every flag has returned to its starting position and again the original distances are restored. However it is hardly ever the case that the beetles themselves have returned to their original positions. My friend Dennis McCaughan asked "When do the beetles get back to their original position?" and he and I quickly worked out the answer.

It is obvious that the relative order of the beetles around the circle never changes (as two beetles never swap places). After 100 seconds each beetle has moved to one of the original beetle positions, say through t original clockwise beetle positions, and t is the same for every beetle; t can be positive or negative. The clockwise distance a beetle has travelled is its clockwise drift, a sum of t original consecutive distances.  The total clockwise drift is the sum of the individual drifts and in this sum each original distance occurs t times. So the total clockwise drift is 100t. 

Initially let there be x beetles moving clockwise and y=9-x beetles moving anticlockwise. Since every collision is between a clockwise beetle and an anticlockwise beetle (turning a clockwise beetle into an anticlockwise one and vice versa) x and y do not change. We can think of d=x-y as the speed of clockwise "drift", the amount of clockwise distance consumed per second. Therefore the total clockwise drift after 100 seconds must be 100d. Hence 100d = 100t and so d = t.

We can now determine when the beetles will all return to their original positions. If d=9 or -9 then, after 100 secs, the beetles will be back in place after 100 seconds since each beetle will have moved through 9 original beetle positions. If d=3  or -3 then after 100 seconds each beetle will have moved through 3 original beetle positions clockwise or anticlockwise. So 300 seconds brings them back to place. For other values of d, a full 900 seconds is required.

No comments:

Post a Comment