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.
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.
Sunday, 17 May 2020
A puzzle about disease transmission
I heard this puzzle over 30 years ago when it was circling in North American Computer Science academic circles. The current pandemic and how to stem its spread reminded me of the puzzle. It concerns three sailors, one prostitute and two condoms. Stop reading now if you find that scenario too unsavoury.
The four characters have agreed that each sailor will have intercourse with the prostitute and the problem is to do this safely with only the two condoms at their disposal. What does "safely" mean here? Certainly they wish to guard against the sexual acts resulting in conception but they are all aware that, given the company they have been keeping, one or more of them may have one or more STDs and they don't want any further infection to be transmitted. There is a short discussion of the problem in this Reddit thread.
The solution is not that hard although it is quite easy to find convincing "almost" solutions. Here is one. Sailor Donald wears the first condom and has his wicked way. Then sailor Eric puts on the second condom and then the first condom over it and does the deed. Finally sailor Jared turns the second condom inside out, puts it on, then puts on the first condom over it and completes the action.
This fails in one respect only: Donald has infected the inner surface of the first condom; during the second act this infection is transmitted to the outer surface of the second condom, and so Jared can become infected by Donald's poison. A further incorrect solution appears in the Reddit thread (and then corrected).
The true solution is very similar. Donald uses both condoms (the second inside the first); Eric uses the first condom, Jared turns the second condom inside out and then dons the first condom.
In each sexual act the prostitute is only in contact with the outer surface of the first condom and so she cannot contract a fresh infection. Each man's member touches a condom surface untainted by any infection. All quite easy and possibly a puzzle and solution known to many.
I offer one final twist. Suppose there are 2n+1 sailors and n+1 condoms (but still one prostitute). How about safe sex now?
Let's number the sailors 0 to 2n and the condoms 0 to n.
For each i = 0 to n-1 sailor i wears condom i and also condom 0 over it
Sailor n just uses the single condom 0
For each i = 1 to n sailor n+i wears condom i inside out and also condom 0 over it.
The four characters have agreed that each sailor will have intercourse with the prostitute and the problem is to do this safely with only the two condoms at their disposal. What does "safely" mean here? Certainly they wish to guard against the sexual acts resulting in conception but they are all aware that, given the company they have been keeping, one or more of them may have one or more STDs and they don't want any further infection to be transmitted. There is a short discussion of the problem in this Reddit thread.
The solution is not that hard although it is quite easy to find convincing "almost" solutions. Here is one. Sailor Donald wears the first condom and has his wicked way. Then sailor Eric puts on the second condom and then the first condom over it and does the deed. Finally sailor Jared turns the second condom inside out, puts it on, then puts on the first condom over it and completes the action.
This fails in one respect only: Donald has infected the inner surface of the first condom; during the second act this infection is transmitted to the outer surface of the second condom, and so Jared can become infected by Donald's poison. A further incorrect solution appears in the Reddit thread (and then corrected).
The true solution is very similar. Donald uses both condoms (the second inside the first); Eric uses the first condom, Jared turns the second condom inside out and then dons the first condom.
In each sexual act the prostitute is only in contact with the outer surface of the first condom and so she cannot contract a fresh infection. Each man's member touches a condom surface untainted by any infection. All quite easy and possibly a puzzle and solution known to many.
I offer one final twist. Suppose there are 2n+1 sailors and n+1 condoms (but still one prostitute). How about safe sex now?
Let's number the sailors 0 to 2n and the condoms 0 to n.
For each i = 0 to n-1 sailor i wears condom i and also condom 0 over it
Sailor n just uses the single condom 0
For each i = 1 to n sailor n+i wears condom i inside out and also condom 0 over it.
Subscribe to:
Posts (Atom)