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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment