Conference rusure::math

This one reminds me of a problem a friend of mine came up with when we were
teaching calculus; it LOOKS like a trivial variation of your standard
minimization problem, but it's actually very hard:

A dog is on one side of a rectangular pool; a piece of meat is on the other.
The dog can swim at rate s, run at rate r, r>s; it wishes to reach the meat in
the minimum time possible.  How does it do this?

There are many problems of this general form in which you know, either as an
arbitrary given, or because of the physical situation, that the path will
consist of three line segments, one at one rate, the other two at some other
rate.  The problem here is that you have to consider paths that, say, lop of
the two corners of the rectangle but run along the edge.  (If the pool is
circular, there's no problem, since no such path can possibly gain; but
for a rectangle, it depends on the details of the sizes and rates.)

I have never seen a satisfactory treatment of this problem.
							-- Jerry

It's clear that the solution curve is 'convex' (otherwise a simple
construction yields a shorter path and a larger area).

It's also clear that the curve meets the x- and y-axes at (1,0) and (0,1),
respectively.  We show this by contradiction.  Assume a curve which maximizes
the ratio A/L does not meet the x-axis at (1,0).  Then construct a line from
(1,0) which is tangent to the curve a point P.  This increases the enclosed
area, while reducing the length.  ... QED.

Corrollary: The minimal curve is tangent to the line x=1 at (1,0).

Consider any segment of a supposed minimal curve that is wholly within the
bounding square.  The ratio of A/L can be increased if that segment were
replaced by an arc of a circle of the same length (or a straight segment --
which is an arc of a circle with infinite radius).  (Actually, some special
care must be taken if this arc extends outside the square).

This simplifies the problem quite a bit.

Stan,

Just off the top of my head:

The curve must touch one of the lines X=1 or Y=1 (or both).
(Assume it didn't.  Then I'd just scale it up around (0,0) until it touched.
The area would go up with the square of the scaling factor while the length
would go up linearly.)

Assume, for concreteness, that the curve starts from (0,a), a<1, and first 
touches the line Y=1 at (b,1).  Now replace that part of the curve with
the line segment from (0,1) to (b,1).  The area goes up and the length goes
down.  Big win.

The region must be convex.  (Hard to believe it's not.  On the other hand, I
can't immediately think of a proof that satisfies me.)

The region must be symmetric about the line through (0,0) and (1,1).
(Assume it's not.  The diagonal line divides it into two halves.  If one
of the halves has a lower A/L ratio than its buddy, replace it with a mirror
image of its better half.  Another win.  [N.B.: this assumes convexity])

The result of all of this is that the problem has just transformed itself into
the identical problem involving a smaller square in the upper right hand 
corner of the original square.

  (0,1)		 (b,1)	  (1,1)
  	+----------.	+ 
	|	   :	
	|	   :..... (1,b)	
	|	 (b,b)	|
	|		|
	|		|
	|		|
  (0,0)	+---------------+ (1,0)


This says to me that there are two possible solutions. One is a curve which
starts from (0,1) and goes to (1,0) without otherwise touching the lines X=1
and Y=1.  This reduces to the well known problem of constant perimeter and
maximum area and the quadrant of a circle is the answer is that case. The
other possibility involves the lines segments from (0,1) to (1,1) to (1,0). 

As you point out, the A/L ratios turn out to be the same for both cases.
Hence, I believe that you've found all of the solutions.

Mike.

Upon reflection, I'd like to retract the last two paragraphs and think about
it some more.

Mike.

Peter Gilbert and I evaluated A/P for a special class of curves
and discovered some intersting things.

Suppose the curve starts at (1,0) and goes up a distance of 1-x
(where 0<x<1).  Then via a quarter circular arc, center at (1-x,1-x), it goes
to (1-x,1), and then a horizontal segment goes to (0,1).


		D	  A
		+---------+-----+ (1,1)
		|	    .	|
		|	      .	|   x
		|	  +	+B
		|	 C	|
		|		|  1-x
		|		|
		+----------+----+
	       O    1-x      x	E


Hard to draw, but basically, there is a semicircle with center at C
and radius x=CA=CB.

Then A=2x(1-x)+(1-x)^2+pi x^2/4   and   P=2(1-x)+pi x/2.

Taking the derivative of A/P with respect to x and setting this to 0
finds that the maximum of A/P occurs when x=(2 sqrt(pi)-4)/(pi-4).
Plugging this value of x back into A/P, shows that the maximum value
that A/P attains is (2 sqrt(pi)-4)/(pi-4)) which is the same as the
value of x at this extremum. (A coincidence!?)

Anyhow, this maximum value is x=A/P=0.5301589042686188... > 1/2.

So we have a curve where A/P>1/2.  There is no reason to believe that
this is the maximum value of A/P over all curves.

For a while, when I still thought A/P<=1/2, I went looking for
results that might let me prove this.  I found the following result,
which, although not useful for this situation, is of interest:

If K is a convex body in Euclidean n-space, and if V is it's volume,
and A it's surface area, then if K contains no lattice points in its interior
(points with integer coordinates), then V/A<=1/2.

			References:

H. Hadwiger, Volumen und Oberflache eines Eikorpers, der keine
	Gitterpunkte Uberdeckte, Mathematische Zeitschrifft 116(1970)191-196.

Edward A. Bender, Area-Perimeter Relations for Two-dimensional Lattices.
	American Mathematical Monthly 69(1962)742-744.

Note that if n=2, i.e. we are working in the plane, this theorem says that
if a convex curve in the plane contains no lattice points in its interior,
then A/P<=1/2, where A is its area and P is its perimeter.

Note that in our present problem, if we reflect the curve in the 2 axes
and around the origin, we obtain a closed convex curve in the square of
side 2.  A problem equivalent to our given problem is then asking for
such curves, what is the maximum value of A/P?  Unfortunately, we can't
apply Hadwiger's result, because the curve contains one lattice point,
namely the origin.

A result of Hammer states that in the plane,
if a convex curve contains G lattice points in the interior,
then G>A-P/2, where the constant 1/2 is best possible. (If G=0, this
is equivalent to Hadwiger's result.) In our case, G=1, and this
inequality doesn't seem to be of any use.

			References:

Jurgen Bokowski, Hugo Hadwiger und Jorg M. Wills, Eine Ungleichung zwischen
	Volumen, Oberflache und Gitterpunktanzahl konvexer Korper im
	n-dimensionalen euklidischen Raum. Mathematische Zeitschrift
	127(1972)363-364.

Wolfgang M. Schmidt, Volume, Surface Area and the Number of Integer Points
	Covered by a Convex Set. Archive der Mathematik 23(1972)537-543.

It was suggested that perhaps some curve of the form x^p+y^p=1
for p>2 would give a ratio A/P that was larger than 1/2.

I tried this for several p and found that it was indeed correct.

Let Ap be the area under the curve from 0 to 1.
Let Pp be the arc length (perimeter).

For p=2 we have:

A2=pi/4,   P2=pi/2, A2/P2=1/2

------------------

For p=3 we have:

A3=GAMMA(1/3)^2/6*GAMMA(2/3)=0.8833192197563367...
P3=1.6862...

A3/P3=0.5238...

------------------

For p=4 we have:

A4=GAMMA(1/4)^2/8*sqrt(pi)=0.9270377474912972...
P4=1.7543...

A4/P4=0.5284...

------------------

For p=5 we have:

A5=GAMMA(1/5)^2/10*GAMMA(2/5)=0.950150717999...
P5=1.7985...

A5/P5=0.5283...

******************************************

In calculating the arc length, I wasn't able to integrate the function
sqrt(1+f'(x)**2) exactly, so I did a numerical approximation by inscribing a
polygon of 10,000 sides in the curve and adding up the lengths of these sides.
So I wouldn't trust the Pn figures to more than about 4 decimal places.

I believe the original problem is equivalent to a problem recently
published by Sidney Kravitz in the August issue of Crux Mathematicorum
9(1983)209:

Problem 870:

	Of all the simple closed curves which are inscribed in a unit
	square (touching all four sides), find the one which has
	the minimum ratio of perimeter to enclosed area.

Mr. Kravitz submitted this problem without a solution.  The solution,
if any readers find one, isn't scheduled to be published until
near the end of 1984.

Just replicate the figure so that you have four squars around a central point.
Now the problem reduces to maximizing the area-to-arc-length ratio of a
closed curve, which has been known for a long time to be a circle. So the
quarter-circle is the best solution to the original problem.

Lynn Yarbrough

No. You miss the point that the curve is restricted to lie
within the square.  Also, as the previous replies show, we've
already found curves that are better than the quarter circle.

The expanding-ballon-in-a-box analogy leads me to look at curves which run
along the boundary to meet a quarter-circle of radius k at a point 1-k
from the sides. The area-to-length ratio of that figure is

a/l=(1-k^2+pi*k^2/4) / (2(1-k)+pi*k/2)

I used vaxima to differentiate this. The numerator of the derivative is
pi^2*k^2 - 4*pi*(2k^2-2k+1) + 16*(k^2-2k+1)
which has a zero at k= .5301589028...
- Lynn Yarbrough

The maximal A/P found by Gilbert, myself, and Yarbrough is indeed correct.
This maximum value is (2 sqrt(pi) - 4)/(pi - 4).  A proof can be found in [1].
In fact, Lin [1] has a more general result:

Let G be a simple closed curve of perimeter P and area A contained
in a polygon of perimeter p which is circumscribable on a circle of
circumference c.  Then the maximum value of A/P is achieved when
P=sqrt(cp), and this maximal value is c sqrt(p)/(2 pi (sqrt(p)+sqrt(c) ).

In our problem, the symmetrized problem is the case where the polygon
is a square with perimeter 8.

A (more difficult) proof for the square case can be found in [2].

The analogous problem when the figure is a rectangle is an unsolved
problem (see [3]).

			References

[1] Tung-Po Lin, Maximum Area Under Constraint. Mathematics Magazine.
	50(1977)32-34.

[2] L. A. Graham, Ingenious Mathematical Problems and Methods. Dover,
	New York: 1959, problem 47, pp 29, 169-173.

[3] Singmaster and Soupporis, A Constrained Isoperimetric Problem.
	Proceedings of the Cambridge Philosophical Society. 83(1978)73-82.

[4] R. F. DeMar, A Simple Approach to Isoperimetric Problems in the Plane.
	Mathematics Magazine 48(1975)1-12.

[5] Bob Osserman, The Isoperimetric Inequality. Bulletin of the AMS.
	84(1978)1132-1238.