From: Clive Tooth <clive@pisquaredoversix.force9.co.uk>
Subject: Re: Packing Rectangles of Decreasing Size (Longish)
Date: Sun, 14 Nov 1999 11:39:22 +0000
Newsgroups: sci.math
Keywords: Packing rectangles to demonstrate famous infinite sums

DWCantrell wrote:

> Congratulations, Clive, on your success at packing! (See end of post.)
> 
> When you started the tread "Zeta(2) packing", I immediately stated a conjecture
> that the squares of sides 1/n [n=1,2,3,...] could be packed in a rectangle of
> dimensions 1 and pi^2/6. (I hope that perhaps my comment helped to encourage
> you in your packing effort!) However, I did not explain in full why I thought
> the conjecture to be a good one. Let me do so now. In the process I will give a
> very simple algorithm which works remarkably well in many similar packing
> problems.
> 
> Several years ago, I became interested in the unsolved problem of packing the
> rectangles of dimensions 1/n and 1/(n+1) [n=1,2,3,...] in the unit square. One
> of the first packing algorithms which I tried by hand seemed to work well. I
> then programmed this algorithm (in Mathematica) using precise rational
> arithmetic. Much to my joy, my PC (very slow and small by today's standards)
> packed thousands of the rectangles in the unit square, dramatically improving
> on the then-current best such published packing. My guess is that, had I
> allowed the program to continue running, it would have continued packing such
> rectangles until hardware limitations caused termination. Why did I not let the
> program run longer? Because I felt that I already had enough evidence to
> indicate it was quite likely that the algorithm would in fact allow all of the
> rectangles to be packed, and I wanted to *prove* that they could *all* be
> packed by the algorithm. It seemed that merely running the program longer would
> not have given me any additional insight which would assisted in finding a
> proof. Why did I not publish the partial packing I had then? Because I felt
> that any publication would be premature. I wanted to publish a proof that the
> algorithm would pack all of the rectangles, not merely to exhibit a partial
> packing obtained by the algorithm. But alas, I have never been able to prove
> that the algorithm will pack all of the rectangles. I now give this extremely
> simple algorithm.
> 
> ALGORITHM for packing rectangles of dimensions 1/n and 1/(n+1) [n=1,2,3,...] in
> the unit square:  Pack the rectangles in decreasing order according to size
> (that is, first pack the rectangle 1 by 1/2, then the rectangle 1/2 by 1/3, and
> so on). Thinking of the unit square oriented so that its sides are vertical and
> horizontal, pack the nth rectangle with its longer (1/n) sides vertical so that
> (primary criterion) it is as far to the left as possible. In the event that a
> rectangle's position is not uniquely determined by the primary criterion, the
> rectangle should be packed so that (secondary criterion) it is as far down as
> possible. (Concisely put: Pack the rectangles as far left and down as
> possible!)
> 
> I have given this trivial but effective algorithm (1) in the hope that others
> (perhaps with larger and faster computers) will program the algorithm and
> confirm its efficacy in packing the 1/n by 1/(n+1) rectangles in the unit
> square and, more importantly, (2) in the hope that someone will eventually be
> able to prove that it will pack all of the rectangles.
> 
> The same algorithm can be used in many similar packing problems. For example,
> the reason that I was able to quickly state the conjecture that the squares of
> sides 1/n [n=1,2,3,...] could be packed in a rectangle of dimensions 1 and
> pi^2/6, so soon after Clive began the "Zeta(2) packing" tread, was that I had
> investigated this packing problem using my algorithm years ago, shortly after
> my success with using it in packing many of the 1/n by 1/(n+1) rectangles in
> the unit square. The packing given by my
> as-far-to-the-left-and-down-as-possible algorithm for the squares of sides 1/n
> looks similar to Clive's packing,
> http://www.pisquaredoversix.force9.co.uk/Tiling.htm, but it is not the same. My
> packing looks exactly like his, turned upside down, for the first 6 squares.
> Then, where Clive has square 8, my algorithm puts square 7. Where he has
> successively squares 7, 10, 12, 13, and 14, my algorithm places successively
> squares 8, 9, 10, and 11. Etc.
> 
> Although I have not been able to tell from Clive's description precisely how
> his algorithm determines the position of a given square, my guess is that our
> algorithms are of similar efficiency. I think it likely that both algorithms
> will pack all of the squares 1/n in the 1 by pi^2/6 rectangle, but that such
> will perhaps be difficult to prove. I also investigated several packing
> algorithms, other than the one detailed above, which seem to work equally well.
> For example, for the problem of packing the 1/n by 1/(n+1) rectangles in the
> unit square, it also works well to pack the rectangles either (1) so that their
> lower left corners are as close to the lower left corner of the unit square as
> possible or (2) so that their upper right corners are as far from the upper
> right corner of the unit square as possible. I favor the algorithm which I gave
> originally, simply because it is slightly easier conceptually and from the
> standpoint of implementation.
> 
> Questions and comments are welcomed.
> 
> Cheers,
>    David W. Cantrell
> -----------------------------
> 
> P.S. I strongly recommend using precise rational arithmetic when implementing
> algorithms for packing problems similar to those discussed above!
> 
> In article <382B3A3C.44BA20B2@pisquaredoversix.force9.co.uk>, Clive Tooth
> <clive@pisquaredoversix.force9.co.uk> writes:
> 
> >> Is there a convex set in R^2, with area pi^2/6, which can be tiled with
> >> a set of square tiles with sides 1, 1/2, 1/3, etc?
> >
> >I have written a program which attempts to pack the tiles into a 1 by
> >pi^2/6 rectangle (with the sides of the squares parallel to the sides of
> >the rectangle). The program has packed the first 1,000 tiles into the
> >rectangle successfully. See
> >http://www.pisquaredoversix.force9.co.uk/Tiling.htm
> >
> >1) The program uses double precision floating point, rather than
> >unlimited precision rational arithmetic, for determining the positions
> >of the squares. However, I have been careful with the coding.
> >
> >2) The program puts the squares in in decreasing order of size. Every
> >time it places a square it effectively appends the coordinates of its
> >bottom left hand corner and its top right hand corner to a list of trial
> >points.  [Initially this list contains just one point: the top left hand
> >corner of the rectangle.] When the program wants to add a new square it
> >scans that list from the start, determining if the new square can be
> >placed with its top left hand corner at each trial point. The square
> >will be placed at the first trial point for which placement of the
> >square is possible.
> >
> >3) I am not really sure if the tiles should be considered open, closed
> >or something in between. Perhaps the conditions are best stated as:
> >    i) all the tiles to be open
> >    ii) the intersection of any two tiles to be empty
> >    iii) all tiles to lie within the open rectangle.
> >Thus, I suppose, the tiling will cover the open rectangle except
> >possibly for some set of measure zero.
> >
> >4) I have no idea whether the tiling process can be carried on beyond
> >1,000 tiles - but it looks hopeful.

=========================================================

I have changed my packing algorithm somewhat. The new form of the
algorithm just _might_ be more amenable to being the basis of a proof
than my previous one or David's as-far-to-the-left-and-down-as-possible
method.

Using the new algorithm I have been able to pack 100,000 squares into a
1 by pi^2/6 rectangle in about 25 minutes. The new method works by
sub-dividing the remaining part of the original rectangle into
sub-rectangles and then, when a new square is to be inserted, choosing
one of the subrectangles which will completely hold the square and then
positioning the square at the top left hand corner of the rectangle. The
remaining L-shaped part of the rectangle is then partitioned into two
rectangles. Occasionally one of the two new rectangles may have a zero
height or zero width, but this does not matter. Thus at each stage one
rectangle is used and replaced by two smaller rectangles. Thus, just
before inserting piece n, the remaining space will have been split into
n rectangles. So, we would need to prove that at that stage at least one
of the rectangles had a short side of least 1/n.

Choosing a rectangle at stage n
===============================

I have tried three methods:

1) First fit: Using the first suitable rectangle that the program
happens to find given the way I have stored the table of rectangles.
This method works perfectly, I have never known it to fail to pack as
many squares as I have wanted to pack.

2) Best fit: Using the a rectangle whose short side is 1/n or exceeds
1/n by the smallest amount. This method also works perfectly, and
happens to give a different packing to method (1).

3) Worst fit: Using a rectangle with the longest short side. This method
does not work. It fails on inserting the square with side 1/109 (!)

Partitioning the L-shaped part into two rectangles
==================================================

Having inserted a square at the top left hand corner of a rectangle

+-------+-------------------+
|       |                   |
|       |                   |
|       |                   |
+-------+                   |
|                           |
|                           |
+---------------------------+

we can divide the remaining part into rectangles like this (A)

+-------+-------------------+
|       |                   |
|       |                   |
|       |                   |
+-------+-------------------+
|                           |
|                           |
+---------------------------+

or like this (B)

+-------+-------------------+
|       |                   |
|       |                   |
|       |                   |
+-------+                   |
|       |                   |
|       |                   |
+-------+-------------------+

Method (B) looks more sensible: always dividing the _longer_ side of the
original rectangle.

I have tried "always dividing the _longer_ side" and "always dividing
the _shorter_ side". The latter method just does not work: it cannot
place the square with side 1/4. So I always use the first method (which
I call "squarish").

An example
==========

Here is the program packing the first 20 squares into the rectangle,
using best fit and squarish:

Rectangle 0:
  (0.000000, 0.000000) = (0, 0)  The coordinates of the top
                                 left hand hand corner.
                                 The y-axis runs _downwards_.
                                      
  1.644934x1.000000 = WxH        The width and height.

Inserting square number 1 in rectangle 0
at (0.000000, 0.000000) = (0, 0)
Rectangle 0:                     Rectangle 0 is replaced by:
  (1.000000, 0.000000) = (0+1/1, 0)
  0.644934x1.000000 = W-1/1xH
Rectangle 1:                     And a new rectangle is created:
  (0.000000, 1.000000) = (0, 0+1/1) This has zero height, as the
  1.000000x0.000000 = 1/1xH-1/1     fit was exact.

Inserting square number 2 in rectangle 0
at (1.000000, 0.000000) = (0+1/1, 0)
Rectangle 0:
  (1.500000, 0.000000) = (0+1/1+1/2, 0)
  0.144934x0.500000 = W-1/1-1/2x1/2
Rectangle 2:
  (1.000000, 0.500000) = (0+1/1, 0+1/2)
  0.644934x0.500000 = W-1/1xH-1/2

Inserting square number 3 in rectangle 2
at (1.000000, 0.500000) = (0+1/1, 0+1/2)
Rectangle 2:
  (1.333333, 0.500000) = (0+1/1+1/3, 0+1/2)
  0.311601x0.500000 = W-1/1-1/3xH-1/2
Rectangle 3:
  (1.000000, 0.833333) = (0+1/1, 0+1/2+1/3)
  0.333333x0.166667 = 1/3xH-1/2-1/3

Inserting square number 4 in rectangle 2
at (1.333333, 0.500000) = (0+1/1+1/3, 0+1/2)
Rectangle 2:
  (1.583333, 0.500000) = (0+1/1+1/3+1/4, 0+1/2)
  0.061601x0.250000 = W-1/1-1/3-1/4x1/4
Rectangle 4:
  (1.333333, 0.750000) = (0+1/1+1/3, 0+1/2+1/4)
  0.311601x0.250000 = W-1/1-1/3xH-1/2-1/4

Inserting square number 5 in rectangle 4
at (1.333333, 0.750000) = (0+1/1+1/3, 0+1/2+1/4)
Rectangle 4:
  (1.533333, 0.750000) = (0+1/1+1/3+1/5, 0+1/2+1/4)
  0.111601x0.250000 = W-1/1-1/3-1/5xH-1/2-1/4
Rectangle 5:
  (1.333333, 0.950000) = (0+1/1+1/3, 0+1/2+1/4+1/5)
  0.200000x0.050000 = 1/5xH-1/2-1/4-1/5

Inserting square number 6 in rectangle 3
at (1.000000, 0.833333) = (0+1/1, 0+1/2+1/3)
Rectangle 3:
  (1.166667, 0.833333) = (0+1/1+1/6, 0+1/2+1/3)
  0.166667x0.166667 = 1/3-1/6xH-1/2-1/3
Rectangle 6:
  (1.000000, 1.000000) = (0+1/1, 0+1/2+1/3+1/6)
  0.166667x0.000000 = 1/6xH-1/2-1/3-1/6

Inserting square number 7 in rectangle 0
at (1.500000, 0.000000) = (0+1/1+1/2, 0)
Rectangle 0:
  (1.642857, 0.000000) = (0+1/1+1/2+1/7, 0)
  0.002077x0.142857 = W-1/1-1/2-1/7x1/7
Rectangle 7:
  (1.500000, 0.142857) = (0+1/1+1/2, 0+1/7)
  0.144934x0.357143 = W-1/1-1/2x1/2-1/7

Inserting square number 8 in rectangle 7
at (1.500000, 0.142857) = (0+1/1+1/2, 0+1/7)
Rectangle 7:
  (1.625000, 0.142857) = (0+1/1+1/2+1/8, 0+1/7)
  0.019934x0.125000 = W-1/1-1/2-1/8x1/8
Rectangle 8:
  (1.500000, 0.267857) = (0+1/1+1/2, 0+1/7+1/8)
  0.144934x0.232143 = W-1/1-1/2x1/2-1/7-1/8

Inserting square number 9 in rectangle 4
at (1.533333, 0.750000) = (0+1/1+1/3+1/5, 0+1/2+1/4)
Rectangle 4:
  (1.644444, 0.750000) = (0+1/1+1/3+1/5+1/9, 0+1/2+1/4)
  0.000490x0.111111 = W-1/1-1/3-1/5-1/9x1/9
Rectangle 9:
  (1.533333, 0.861111) = (0+1/1+1/3+1/5, 0+1/2+1/4+1/9)
  0.111601x0.138889 = W-1/1-1/3-1/5xH-1/2-1/4-1/9

Inserting square number 10 in rectangle 9
at (1.533333, 0.861111) = (0+1/1+1/3+1/5, 0+1/2+1/4+1/9)
Rectangle 9:
  (1.633333, 0.861111) = (0+1/1+1/3+1/5+1/10, 0+1/2+1/4+1/9)
  0.011601x0.100000 = W-1/1-1/3-1/5-1/10x1/10
Rectangle 10:
  (1.533333, 0.961111) = (0+1/1+1/3+1/5, 0+1/2+1/4+1/9+1/10)
  0.111601x0.038889 = W-1/1-1/3-1/5xH-1/2-1/4-1/9-1/10

Inserting square number 11 in rectangle 8
at (1.500000, 0.267857) = (0+1/1+1/2, 0+1/7+1/8)
Rectangle 8:
  (1.590909, 0.267857) = (0+1/1+1/2+1/11, 0+1/7+1/8)
  0.054025x0.090909 = W-1/1-1/2-1/11x1/11
Rectangle 11:
  (1.500000, 0.358766) = (0+1/1+1/2, 0+1/7+1/8+1/11)
  0.144934x0.141234 = W-1/1-1/2x1/2-1/7-1/8-1/11

Inserting square number 12 in rectangle 11
at (1.500000, 0.358766) = (0+1/1+1/2, 0+1/7+1/8+1/11)
Rectangle 11:
  (1.583333, 0.358766) = (0+1/1+1/2+1/12, 0+1/7+1/8+1/11)
  0.061601x0.141234 = W-1/1-1/2-1/12x1/2-1/7-1/8-1/11
Rectangle 12:
  (1.500000, 0.442100) = (0+1/1+1/2, 0+1/7+1/8+1/11+1/12)
  0.083333x0.057900 = 1/12x1/2-1/7-1/8-1/11-1/12

Inserting square number 13 in rectangle 3
at (1.166667, 0.833333) = (0+1/1+1/6, 0+1/2+1/3)
Rectangle 3:
  (1.243590, 0.833333) = (0+1/1+1/6+1/13, 0+1/2+1/3)
  0.089744x0.166667 = 1/3-1/6-1/13xH-1/2-1/3
Rectangle 13:
  (1.166667, 0.910256) = (0+1/1+1/6, 0+1/2+1/3+1/13)
  0.076923x0.089744 = 1/13xH-1/2-1/3-1/13

Inserting square number 14 in rectangle 13
at (1.166667, 0.910256) = (0+1/1+1/6, 0+1/2+1/3+1/13)
Rectangle 13:
  (1.238095, 0.910256) = (0+1/1+1/6+1/14, 0+1/2+1/3+1/13)
  0.005495x0.071429 = 1/13-1/14x1/14
Rectangle 14:
  (1.166667, 0.981685) = (0+1/1+1/6, 0+1/2+1/3+1/13+1/14)
  0.076923x0.018315 = 1/13xH-1/2-1/3-1/13-1/14

Inserting square number 15 in rectangle 3
at (1.243590, 0.833333) = (0+1/1+1/6+1/13, 0+1/2+1/3)
Rectangle 3:
  (1.310256, 0.833333) = (0+1/1+1/6+1/13+1/15, 0+1/2+1/3)
  0.023077x0.066667 = 1/3-1/6-1/13-1/15x1/15
Rectangle 15:
  (1.243590, 0.900000) = (0+1/1+1/6+1/13, 0+1/2+1/3+1/15)
  0.089744x0.100000 = 1/3-1/6-1/13xH-1/2-1/3-1/15

Inserting square number 16 in rectangle 15
at (1.243590, 0.900000) = (0+1/1+1/6+1/13, 0+1/2+1/3+1/15)
Rectangle 15:
  (1.306090, 0.900000) = (0+1/1+1/6+1/13+1/16, 0+1/2+1/3+1/15)
  0.027244x0.062500 = 1/3-1/6-1/13-1/16x1/16
Rectangle 16:
  (1.243590, 0.962500) = (0+1/1+1/6+1/13, 0+1/2+1/3+1/15+1/16)
  0.089744x0.037500 = 1/3-1/6-1/13xH-1/2-1/3-1/15-1/16

Inserting square number 17 in rectangle 2
at (1.583333, 0.500000) = (0+1/1+1/3+1/4, 0+1/2)
Rectangle 2:
  (1.642157, 0.500000) = (0+1/1+1/3+1/4+1/17, 0+1/2)
  0.002777x0.058824 = W-1/1-1/3-1/4-1/17x1/17
Rectangle 17:
  (1.583333, 0.558824) = (0+1/1+1/3+1/4, 0+1/2+1/17)
  0.061601x0.191176 = W-1/1-1/3-1/4x1/4-1/17

Inserting square number 18 in rectangle 12
at (1.500000, 0.442100) = (0+1/1+1/2, 0+1/7+1/8+1/11+1/12)
Rectangle 12:
  (1.555556, 0.442100) = (0+1/1+1/2+1/18, 0+1/7+1/8+1/11+1/12)
  0.027778x0.057900 = 1/12-1/18x1/2-1/7-1/8-1/11-1/12
Rectangle 18:
  (1.500000, 0.497655) = (0+1/1+1/2, 0+1/7+1/8+1/11+1/12+1/18)
  0.055556x0.002345 = 1/18x1/2-1/7-1/8-1/11-1/12-1/18

Inserting square number 19 in rectangle 8
at (1.590909, 0.267857) = (0+1/1+1/2+1/11, 0+1/7+1/8)
Rectangle 8:
  (1.643541, 0.267857) = (0+1/1+1/2+1/11+1/19, 0+1/7+1/8)
  0.001393x0.052632 = W-1/1-1/2-1/11-1/19x1/19
Rectangle 19:
  (1.590909, 0.320489) = (0+1/1+1/2+1/11, 0+1/7+1/8+1/19)
  0.054025x0.038278 = W-1/1-1/2-1/11x1/11-1/19

Inserting square number 20 in rectangle 5
at (1.333333, 0.950000) = (0+1/1+1/3, 0+1/2+1/4+1/5)
Rectangle 5:
  (1.383333, 0.950000) = (0+1/1+1/3+1/20, 0+1/2+1/4+1/5)
  0.150000x0.050000 = 1/5-1/20xH-1/2-1/4-1/5
Rectangle 20:
  (1.333333, 1.000000) = (0+1/1+1/3, 0+1/2+1/4+1/5+1/20)
  0.050000x0.000000 = 1/20xH-1/2-1/4-1/5-1/20


Notes
=====

1) I have experimented with trimming a little off the edge of the
starting rectangle - making the packing impossible, of course. Trimming
10^-5 off the 1-edge causes best fit to fail on square 37,295.

2) I have tried using rectangles with area pi^2/6, but with the short
side longer that 1. None of the rectangles I have tried have been
tilable by my program. For example 1.0001 by pi^2/6.0006 fails with best
fit on square 1,540. 1.5 by pi^2/9 fails on square 8.

3) I have got nowhere with a proof that 1 by pi^2/6 is fully tilable by
my method.

-- 
 
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
==============================================================================

From: dwcantrell@aol.com (DWCantrell)
Subject: Re: Packing Rectangles of Decreasing Size (Was: Zeta(2) packing)
Date: 15 Nov 1999 05:58:43 GMT
Newsgroups: sci.math

Let me now make some additional comments which should be of interest. At the
end I will present some new conjectures. (All rectangles in this post will be
thought of as oriented so that their sides are vertical or horizontal.
Rectangles will be packed in order of decreasing size.)

1. Packing rectangles 1/n by 1/(n+1) [n=1,2,3,...] in the unit square.

For this classic problem, I presented a very simple algorithm in a previous
post; specifically, the algorithm packs the rectangles with their longer sides
being vertical so that, primarily, they are as far to the left as possible and,
secondarily, they are as far down as possible. I stopped my computer program
after it had packed 2^12 squares. Having packed this number of squares is
substantially better than any previously published result of which I am aware.
(For example, V. Balint packed 499 of the rectangles in the unit square [Two
packing problems, Discrete Math., 178 (1998) 233-236].) Although I conjecture
that the simple algorithm which I have given above (along with several other
algorithms which I have investigated) can be used to pack any desired number of
the rectangles, I have no hope of being able to prove this conjecture in the
near future.

I appreciate that skeptical readers may well distrust that my algorithm packed
2^12 squares. Therefore I encourage interested parties to program the simple
algorithm themselves, preferably using precise rational arithmetic, in order to
confirm (and also easily improve on) my result. Balint states that "The
demonstration of a packing of many such rectangles into a unit square requires
either _one_very_great_ sketch or _many_ smaller figures." But of course,
figures themselves do not constitute proof, but rather indicate only how a
claim of a proof can be confirmed. In my opinion, full specification of an
algorithm, as I have done, should serve much the same purpose as figures and is
perhaps preferable to them.

2. Packing squares of sides 1/n [n=1,2,3,...] in the rectangle 1 by pi^2/6.

In the "Zeta(2) packing" tread I stated the conjecture that such a packing was
possible, and in my previous post in this tread I conjectured that my simple
as-far-left-and-down-as-possible algorithm would allow as many squares as
desired to be packed. (BTW, although I initially did the packing into the
rectangle with its longer side horizontal, the algorithm also seems to work
well with the longer side vertical.) As with problem 1. above and with the
problems below, I encourage others to confirm (or improve on) my results using
my simple algorithm or to try other algorithms. Of course, readers of this
tread already know of Clive Tooth's packing of 100,000 squares using another
algorithm!

3. Packing squares of sides 1/n [n=2,3,4,...] in some rectangle of area
pi^2/6-1.

This is almost as classic as problem 1. The rectangle which is normally
suggested has sides of lengths 5/6 and (pi^2-6)/5. (These dimensions give a
rectangle which is as close to being a square as possible for such a packing.)
Interestingly, if the rectangle is oriented with the side of length 5/6
vertical, then my simple as-far-left-and-down-as-possible algorithm fails after
packing the square of side length 1/10. But, if the rectangle is oriented with
the side of length 5/6 horizontal, then my algorithm seems to work well. I
terminated the program after 2^10 squares had been packed. This result is
better than those previously published. [See K. Ball, On Packing Unequal
Squares, J. of Combinatorial Theory, Series A, 75 (1996) 353-357.]  I
conjecture that my as-far-left-and-down-as-possible algorithm can pack as many
squares of sides 1/n [n=2,3,4,...] as desired in the rectangle with sides of
lengths 5/6 (horizontal) and (pi^2-6)/5.

4. Packing squares of sides 1/n [n=3,4,5,...] in the square S of area
pi^2/6-5/4.

Although I do not recall this problem from the literature (but would be a bit
surprised if it were not there somewhere), it seemed reasonable to conjecture
that such a packing could be done. Since my as-far-left-and-down-as-possible
algorithm had worked so well in previous packing problems, I decided to try it
on this one. It did not work, failing after packing the square of side length
1/78. So I tried another algorithm, slightly less simple, and it worked
beautifully: Pack the squares so as to minimize the distances in the taxicab
metric from their lower left corners to the lower left corner of S. (In the
event of a tie for where to pack a given square, choose the leftmost spot.) I
stopped the program after 2^10 squares had been packed. I conjecture that this
taxicab algorithm can be used to pack as many squares of sides 1/n
[n=3,4,5,...] as desired in the square of area pi^2/6-5/4.

5. Packing squares of sides 1/(2n+1) [n=1,2,3,...] in some rectangle of area
pi^2/8-1.

This problem can be found in the literature. (See Balint.) Using the
as-far-left-and-down-as-possible algorithm, I chose to pack the rectangle R
with sides of lengths 1/3 (horizontal) and 3(pi^2/8-1), but there are other
choices for the dimensions which would work just as well I think. I stopped the
program after 2^10 squares had been packed, giving a result better than those
in the literature. I conjecture that my simple algorithm can be used to pack as
many squares of sides 1/(2n+1) [n=1,2,3,...] as desired in R.

6. Packing squares of sides 1/(2n+1) [n=2,3,4,...] in the square S of area
pi^2/8-10/9.

Mutatis mutandis, comments as given for problem 4. Taxicab algorithm packed
2^11 squares before I terminated the program.

---------------------
Now for the really interesting part!

The more elegant packings are perhaps those into regions with smallest possible
perimeter. (In this sense, the rectangle I chose in problem 5 was surely not
the best.) It then dawned on me that, if a suitable number of the larger
squares or rectangles where removed from consideration, the remaining ones
could perhaps be packed in a circle!

7. Packing squares of sides 1/n [integer n>some integer N] in a circle of area
equal to the total area of the squares.

Not in the literature, I believe!

The algorithm I used was not elegant at all, but is simple to describe. Let the
circle be centered at the origin of a rectangular coordinate system, and think
of the circle as divided into quadrants. Pack a square in a quadrant of the
circle so as to minimize the distance (Euclidean) between the origin and the
square's nearest corner. (In the event of ties, choose the position reached
first in rotating counterclockwise from the positive x-axis.)

Using this algorithm I packed more than 1400 squares of sides 1/n
[n=8,9,10,...] in the circle of appropriate area, pi^/6-266681/176400. (The
packing looks rather beautiful to my prejudiced eyes!) Of course, while I do
conjecture that as many squares as desired can be packed in the circle by this
algorithm, I can't imagine a proof.

How small can N be? I would guess that perhaps the squares of sides 1/n
[n=6,7,8,..] can in fact be packed in the appropriate circle, but not by an
algorithm as crude as mine.

I hope that this part of my post will open a small, new branch of inquiry:
finding regions of minimum perimeter which can be used for certain packing
problems. For example, I think that the rectangles in problem 1. can be packed
in a region of perimeter < 4 (but how much less?) and that the squares in
problem 2. can be packed in a region of perimeter < 2+pi^2/3 (but, again, how
much less?).

---------------------
Now I'm technically off-topic for this tread, but I can't resist!  

8. Packing the circles of radii 1/n [integer n>some integer N] in a circle of
area equal to the total area of the circles.

I can not claim to have investigated this problem. However, I will take a
totally wild guess and say that perhaps this would possible for N=5. I would
love to see the diagram for such a packing!

Cheers,
  David W. Cantrell