From: dseal@armltd.co.uk (David Seal)
Newsgroups: rec.puzzles
Subject: Re: The Worm and the Blanket Problem
Date: 16 Dec 92 20:19:09 GMT
Distribution: rec
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK

In article <1992Dec12.194815.16303@CSD-NewsHost.Stanford.EDU>
snewman@Xenon.Stanford.EDU (Steven Newman) writes:

>Here is a new upper bound for the worm-and-blanket problem.  The
>blanket consists of a rectangle with width 2/3 and height 1/3,
>semicircular caps on the left and right ends, and a "bump" on the top
>side consisting of the upper half of a circle with radius 1/3 and
>centered at the center of the rectangle.  More precisely, if the
>rectangle is centered at (0,0), the blanket consists of the union
>of the following objects:
>
>  A rectangle extending from x=-1/3 to x=+1/3 and y=-1/6 to x=+1/6
>
>  A circle with radius 1/6 and center (-1/3, 0)
>
>  A circle with radius 1/6 and center (+1/3, 0)
>
>  The upper half of a circle with radius 1/3 and center (0,0).
>
>...
>
>The area of this figure is 2/9 + pi/36 + (pi/27 - sqrt(3)/36) or
>rougly 0.3777.

I've managed better than that - about 0.317, but the book "Unsolved Problems
in Geometry" by Croft, Falconer and Guy quotes an even better result (about
0.286). They give no proof - just a diagram plus a reference to a paper I
haven't looked up. The diagram is of a truncated rhombus:

            A
           /|\
          / | \
         /  |  \
        /   |   \
       /    |    \
      /     |     B
     /      |     |\
    C-------D-----E-F
     \      |     |/
      \     |     G
       \    |    /
        \   |   /
         \  |  /
          \ | /
           \|/
            H

Each of the triangles ACE and CEH is equilateral, of side 1/SQR(3). (This
makes the distance AH equal to 1.) The distance DE is 1/4, the line BEG is
vertical, and the truncated rhombus which is claimed to be an adequate worm
blanket is the 5-sided polygon ACHGB. I can't prove this.

The best I've managed to prove comes from the following: start by supposing
that the two ends of the worm are A and B, and the halfway point along it is
C. We're allowed to rotate and translate the blanket until its X-axis is the
line AB, then to translate it in the X-direction until C is on the Y-axis.
This gives us the following diagram:

               |
               |
            ...C..
           .   |  ...
          .    |     .
          .    |     .
           .   |      ..
  -----A---.---+--------B----
        ...    |
               |
               |
               |
               |
               |
               |

where half the worm is the curve AC and the other half is the curve CB.

Now, where do we need to have some blanket material? The answer is any point
of the plane such that its distance from the X-axis plus its distance from
the Y-axis is at most 1/2. For the first quadrant, this is clearly the
points where x+y <= 1/2 - i.e. the triangle with corners at (0,0), (1/2,0)
and (0,1/2). The worm is also confined to similarly placed triangles in the
other three quadrants, which gives us the following blanket:

                       |(0,1/2)
                       *
                      /|\
                    /  |  \
                  / ...C..  \
                /  .   |  ... \
              /   .    |     .  \
            /     .    |     .    \
  (-1/2,0)/        .   |      ..    \ (1/2,0)
        -*-----A---.---+--------B----*-
          \     ...    |            /
            \          |          /
              \        |        /
                \      |      /
                  \    |    /
                    \  |  /
                      \|/
                       *
                       |(0,-1/2)

This is a square with diagonal 1, with area 1/2 = 0.500.

But we can do better than this. By rotating the blanket through 180 degrees
if necessary, we can insist that the point C is on the *positive* Y-axis.
This makes no difference to the points where we need some blanket material
in the positive Y half-plane, but now a point in the negative Y half-plane
is only needed if its distance from the X-axis and its distance from the
positive Y-axis sum to at most 1/2. Its distance from the X-axis is simply
ABS(y) = -y, while its distance from the positive Y-axis is its distance
from the origin, i.e. SQR(x^2+y^2). So we need to solve the inequality:

  SQR(x^2+y^2) - y <= 1/2

in the negative Y half-plane.

This gives us:

  SQR(x^2+y^2) <= y + 1/2

Clearly, we must have y >= -1/2, so both sides of this are positive and we
can square to get:

  x^2 + y^2 <= y^2 + y + 1/4

Or:

  y >= 1/4 - x^2

So this gives us the following blanket:

                       |(0,1/2)
                       *
                      /|\
                    /  |  \
                  / ...C..  \
                /  .   |  ... \
              /   .    |     .  \
            /     .    |     .    \
  (-1/2,0)/        .   |      ..    \ (1/2,0)
        -*-----A---.---+--------B----*-
          \     ...    |            /
            - _        |        _ -
                - _    |    _ -
                    - -*- -
                       |(0,-1/4)
                       |

where the lower boundary of the blanket is the parabolic arc y = x^2 - 1/4
for values of x from -1/2 to +1/2. This blanket has area 5/12 = about 0.417.

To bring this down to about 0.317, we instead choose point A to be a
distance D along the worm, point C to be a distance 1/2 along the worm and
point B to be a distance 1-D along the worm. Also let point P be the
endpoint of the worm nearest A and point Q be the endpoint nearest B. Choose
the co-ordinate system based on A, B and C as above. A diagram:

               |
               |
            ...C..
           .   |  ...
       P  .    |     .
      .   .    |     .
      .    .   |      ..
  -----A---.---+--------B----
        ...    |         ... 
               |            Q
               |
               |
               |
               |
               |

Now, we can cover the segment ACB of the worm with a blanket of the shape
found above, but reduced by a factor of length(ACB) = 1-2*D:

                         |(0,1/2-D)
                         *
                        /|\
                      /  |  \
                    / ...C..  \
                  /  .   |  ... \
                /P  .    |     .  \
              / .   .    |     .    \
  (-1/2+D,0)/   .    .   |      ..    \ (1/2-D,0)
          -*-----A---.---+--------B----*-
            \     ...    |         .../
              - _        |        _ - Q
                  - _    |    _ -
                      - -*- -
                         |(0,-1/4+D/2)
                         |

And we can cover the segments PA and BQ with a rectangle of width 2*D and
length 1-2*D, capped with semicircles of radius D:

                         |
                      ...C..
        _--*---------.---*--...--------*--_
       /   |     P  .    |(0,D).       |   \
      /    |    .   .    |     .       |    \
     |(-1/2+D,0).    .   |      .. (1/2-D,0) |
   --*-----*-----A---.---+--------B----*-----*--
 (-1,0)    |      ...    |         ... |     |(1,0)
      \    |             |            Q|    /
       \_  |             |             |  _/
         --*-------------*-------------*-- 
                         |(0,-D)
                         |

So the union of these two blankets will cover the entire worm. I believe an
exact solution for the minimal area of this blanket involves solving a
quartic or worse - in any case, I haven't done it. But trial and error have
given a minimum area of about 0.317, achieved when D is approximately 0.118.

The shape of the blanket is then a rectangle of height about 0.236, width
about 0.764, with semicircular caps of radius about 0.118 on its left and
right ends, a 45/90/45 isosceles triangular cap of height about 0.264
centred on its top edge and a parabolic arc cap centred on its bottom edge.
This last cap extends down to about (0,-0.191) and its parabolic edge has
formula approximately y = x^2/0.764 - 0.191.

>Let R be any point on the [1/6,5/6] segment of the worm; then
>PR + QR <= 2/3.  I claim that R must lie within distance 1/3 of
>(0,0); this proves that R is inside the blanket, since if it
>isn't in the rectangle then it must be above the x axis and hence
>lie inside the semicircular cap.
>
>I suspect there is a trivial proof that shows RC <= 1/3 given
>PQ + QR <= 2/3 and C is the midpoint of P and Q, but the only
>proof I've come up with so far uses hairy calculus (I had to
>prove that the distance from R as you slide along the line from
>P to Q is a convex function).  Geometry buffs may know a better
>one.

Here's a geometrical proof: any point R on the worm has combined distance to
P and Q less than or equal to 2/3. It must therefore lie within an ellipse
with foci P and Q, sum of distances to boundary 2/3. This ellipse has centre
equal to the midpoint of P and Q, i.e. C, major axis on the line PQ and
minor axis passing through C and perpendicular to PQ. All you need to do is
solve to find out how far out you can go along each of the axes and you have
fully characterised the ellipse. I'll leave this as an exercise for the
reader: the answers are that the semi-major axis has length 1/3, the
semi-minor axis length SQR((1/3)^2 - (dist(PC))^2) <= 1/3. So this ellipse
always lies within the circle of radius 1/3 centred on C, and so R lies
within 1/3 of C.

David Seal
dseal@armltd.co.uk

All opinions are mine only...
Newsgroups: rec.puzzles.crosswords