Friday, 22 May 2020
Joining points and sums of squares
This posting is an extended comment on another entry in R J Lipton's blog Gödel's lost letter and P=NP. Lipton's post is entitled A Math Gift for All and is a clever but simple solution to a geometric problem wrapped in a deceptive narrative. You might enjoy reading the post before proceeding here although that is not necessary provided you accept my spoiling the joke. My commentary is on both the solution and the numerical deception.
First the problem (which came from Shmuel Weinberger's book) and Lipton's solution. You are given 2n points in the plane no three of which are collinear, n of which are coloured red and n are coloured blue. Do there exist n straight line segments each joining a unique red point to a unique blue point (as in a matching) in which no two line segments cross?
Lipton teases us with this (see below) but to cut to the chase the answer is Yes by the following argument. Among all the ways of joining the red points to the blue points in a matching consider one where the total length of the n line segments is the smallest. In this matching no two line segments cross because if two lines R1B1 and R2B2 cross then R1, R2, B1, B2 are adjacent points in a quadrilateral and if we replace the diagonal crossing of R1B1 and R2B2 by the line segments R1B2 and R2B1 we will have another matching with smaller total length of segments.
I showed the problem to my son James, a high school math teacher, who found another argument. Begin by choosing a point P not one of the given 2n points but within the cloud of such points and consider any directed straight line L through P. Because of the choice of P not all the 2n points lie on side of L. For any such line L let RL and BL denote the number of red points on the left of P and number of blue points on the left of P. If these numbers are equal then we have divided the set of 2n points into two sets - one set on the left, one set on the right - each containing equal numbers of red and blue points; then we can solve the problem on either side and get a solution to the original problem. But if RL and BL are not equal we can rotate L about P. As we do so RL and BL change by 1 every time L passes past one of the given points and after 180 degrees of rotation the values of RL and BL will have exchanged; so at some stage we shall have RL = BL and can proceed as before.
Both solutions can be made constructive but James' solution seems to lead to a more efficient algorithm (although it may well depend on how much ingenuity you are prepared to use).
The second topic I want to discuss derives from the trick Lipton played on his readers. He introduced a constant c whose value was 102+112+122-132-142, drew the readers in for a few lines and then pointed out that c=0. This identity between consecutive squares is the second in a sequence of identities the first of which is 32+42=52. There is a sequence of similar identities in which k+1 consecutive squares add up to the sum of the following k squares; the next identity (k=3) is 212+222+232+242=252+262+272. In general the middle square of the kth identity is the square of 2k(k+1) which is readily proved by elementary algebra.
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)