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...