Person A has a piece of string exactly one meter long.
geometry/worm.blanket New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Person A has a piece of string exactly one meter long. He can lay it in any configuration he desires (as long as it stays in one piece), for example in a circle, a square, part of a sine wave or a figure of eight. Person B has a piece of card of some fixed shape with which he must try to completely cover the line. The original puzzle does not say whether or not he is allowed to turn the card over, but he can certainly rotate it and move it to any position. Puzzle 1: What shape must B's card be, to guarantee a win, no matter what A does? (Easy: a circle with a diameter of one meter would do.) Puzzle 2: Of all possible solutions to puzzle 1, what is the shape of the one with the minimum area? -- Paul Davies <pkd@delcam.co.uk>, August 1993 I believe this is the 'worm' puzzle, where the mother worm wanted to knit a blanket that could always cover her baby worm. -- Ted Schuerzinger <zed@Dartmouth.EDU>
Show solution
[ Editor: the minimum area is not found in the collected postings; the
best blanket mentioned has area about 0.286. ]
It is indeed the worm puzzle, and was discussed last December. I've
dug out my best effort at the time, which does better than a semicircle
of radius 0.5 (area PI/8 = 0.392699...). Here's the relevant part of
what I posted then:
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 >= x^2 - 1/4 [ Editor: "y >= 1/4 - x^2" in the original ]
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.
-- David Seal <dseal@armltd.co.uk>, August 1993, quoting his posting of
"last December" [ Editor: December 1992 ]