From: dseal@armltd.co.uk (David Seal)
Newsgroups: rec.puzzles,sci.math
Subject: Re: Can You Divide a Square ?
Date: 25 Feb 92 15:37:12 GMT

In article <7538@dutrun2.tudelft.nl> ottens@dutiba.tudelft.nl (Arlet Ottens)
writes:

>How do you cut a unit square into three arbitrary pieces in such a way
>that the greatest circumference is as small as possible.
>
>This is a possible way to cut the unit square into three pieces:
>
>	+------------+
>	|     A      | 1/3
>	+------------+
>	|     B      | 1/3
>	+------------+
>	|     C      | 1/3
>	+------------+	
>      
>The circumference of each piece is 2 * (1 + 1/3) = 2.6667, can you
>do better ? You don't have to restrict yourself to straight lines !
>
>How about the general case, dividing the square in n pieces ?

A nice problem. I'm crossposting this to sci.math - I think the problem may
be of interest there as well.

My best efforts are:


n=3
---

  +-------------C-+     A at (0, 1/2)          = (0.0000,    0.5000)
  |            /  |
  |           /   |     B at ((5+SQR(2))/8, 0) = (0.8017..., 0.0000)
  |          /    |
  A---------D     |     C at ((5+SQR(2))/8, 1) = (0.8017..., 1.0000)
  |          \    |
  |           \   |     D at (5/8, 1/2)        = (0.6250,    0.5000)
  |            \  |
  +-------------B-+     Maximum perimeter = (7+2*SQR(2))/4 = 2.4571...

  The maximum perimeter is in fact the perimeter of all three pieces. This
  is the optimal placing of the points for this particular diagram (i.e. I
  optimised the case of A at (0,1/2), B at (Y,0), C at (Y,1), D at (X,1/2)).


n=4
---

  Somewhat surprisingly, the optimal arrangement is *not* simply to divide
  the square into quarters in the obvious way, leading to a maximum
  perimeter of 2. The following arrangement does better:

  +------D--------+     A at (X,0)     = (0.5313..., 0.0000)
  |      |        |     B at (0,X)     = (0.0000,    0.5313...)
  |       \       |     C at (1,1-X)   = (1.0000,    0.4686...)
  |        |      |     D at (1-X,1)   = (0.4686..., 1.0000)
  B--__   _F--__  |     E at (Y,Y)     = (0.4557..., 0.4557...)
  |    --E      --C     F at (1-Y,1-Y) = (0.5442..., 0.5442...)
  |      |        |     Maximum perimeter = 1.9865...
  |       \       |     
  |        |      |     All lines are straight - I just can't draw them
  +--------A------+       that way!

            SQR(2) + SQR(10 - 7*SQR(2))       2 + SQR(2) - 2*SQR(2)*Y
  where Y = ---------------------------,  X = -----------------------.
                  14*SQR(2) - 16                         4

  Again, this placing of the points is optimal for this particular topology,
  and all the regions have the same perimeter.


n=5
---

  The best I've come up with so far is:

  +--------D--------+     A at (1/2,0)   = (0.5000,    0.0000)
  |        |        |     B at (0,1/2)   = (0.0000,    0.5000)
  |        H        |     C at (1,1/2)   = (1.0000,    0.5000)
  |      /   \      |     D at (1/2,1)   = (0.5000,    1.0000)
  |    /       \    |     E at (1/2,X)   = (0.5000,    0.1796...)
  B---F         G---C     F at (X,1/2)   = (0.1796..., 0.5000)
  |    \       /    |     G at (1-X,1/2) = (0.8203..., 0.5000)
  |      \   /      |     H at (1/2,1-X) = (0.5000,    0.8203...)
  |        E        |     where X = (11 - 6*SQR(2))/14.
  |        |        |     
  +--------A--------+     Maximum perimeter = (24 - 8*SQR(2))/7 = 1.8123...

  Again, I've optimised this particular topology and all regions have the
  same perimeter.


Some questions:

(A) Do all regions always have the same perimeter in any optimal arrangement
    for this problem? Intuitively, it looks likely, because if they don't,
    one should be able to perturb the arrangement so as to decrease the
    larger perimeters at the expense of increasing the smaller ones. But I
    haven't been able to work out how to convert this idea into a proof!

(B) Is it possible for more than three regions to meet at a vertex inside an
    optimal arrangement? The fact that the obvious arrangement for n=4 can
    be improved by splitting the degree 4 vertex at the centre into two
    slightly displaced degree-3 vertices suggests that such an improvement
    may always be possible if the arrangement contains a vertex of degree 4
    or more. But again I can't see how to get a proof - it's not as simple
    as the standard "minimise the total length of the lines joining N
    points" problem, where the only allowed vertices are of degree 3, with
    the three lines at each vertex meeting at angles of 120 degrees. As
    another poster calculated, insisting that the three lines in the n=3
    case above meet at 120 degree angles results in a less-than-optimal
    perimeter of (21 + 5*SQR(3))/12 = 2.4716...

David Seal
dseal@armltd.co.uk

All opinions are mine only...