Circles in a long small rectangle:
It's easy to accommodate 2*n circles of diameter 1
inside a rectangle with dimensions 2 and n.
Which is the smallest rectangle (2xn)
such that 2*n+1 circles can be acommodated?
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
In a rectangle 2*166 it is possible to put 333 circles.
The secret is put the circles in triangular formation and each group of
3 is the in alternate way upon and lower part against the walls of the
rectangle. In the scheme that follows ABC represent the center of a group
of 3 circles.
|------------------------------//---|
| A A B A B // |
| A C A C // A |
| B C B C // B |
|--------------------------//-------|
1,2,3,4,5...... ....332,333
From: Dario Uri
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
From - Thu Jul 30 23:29:40 1998
From: Nick Baxter
Newsgroups: rec.puzzles
Subject: Re: Rectangles and Circles
Date: Thu, 30 Jul 1998 01:32:12 -0700
Organization: Inprise Corp
Lines: 68
Message-ID: <35C02F8C.21272DE3@inprise.com>
Reply-To: nick@visigenic.com
NNTP-Posting-Host: 143.186.37.83
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Glenn Rhoads wrote:
>
> Dario Uri writes:
>
> >> >Which is the smallest rectangle (2xn) such that 2*n+1 circles can
> >> >be acommodated?
>
> >In a rectangle 2*166 is possible to put 333 circles.
> >The secret is put the circles in triangular formation and each group of
> >3 is the in alternate way upon and lower part against the walls of the
> >rectangle.
>
> >|------------------------------//---|
> >| A A B A B // |
> >| A C A C // A |
> >| B C B C // B |
> >|--------------------------//-------|
>
> > 1,2,3,4,5...... ....332,333
>
> That's fine but as others have already pointed out, the real problem is
> to show that this is minimal. Finding optimal packings is in general
> an extremely difficult problem. I know very little about packings but
> even I can see that it is next to impossible to prove that a packing
> involving this many circles is optimal. There are simply too many
> potential packings to account for.
How right you are!! The solution that Dario describes was
the best known, published solution as of 5 years ago. About
3 years ago, a solution of n=165 was given in a recreational
math journal; and just this evening I found a solution for
n=164. (And of course, I am just as confident as the previous
solvers that this one is optimal!)
>
> Also, there is no reason to suppose that the optimal packing involves
> any repeating pattern; optimal packings are often weird and non-intuitive.
> For some examples, check out "Erich's Packing Center" at (this is a
> really excellent page)
>
> http://www.stetson.edu/~efriedma/packing.html
There is another sort of 2D packing puzzle that is even
weirder and less intuitive than those on Erich's page --
where the puzzle is to find an unknown shape that gives
optimal covering.
For example, given a 3-4-5 right triangle, you are to find
the shape and size of 2 congruent tiles that give maximum
coverage - without any overlap or overhang. Rotation and
reflection are encouraged. The best solution ia about 98%
coverage.
Two other more difficult challenges are to cover a 30-60-90
triangle with 2 tiles (~98%), and to cover an equilateral
triangle with 5 tiles (~99%).
> If anybody really does know how to prove an optimal answer for the
> original problem, I definitely would like to know the optimal packing
> (even if I can't understand the proof.).
Obviously, no proof, but I do have a diagram if you're interested.
Nick Baxter
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
RIHess@compuserve.com: the sphere-packing story (Sep. 1998)
You wrote about packing 2n+1 circles in a 2xn rectangle and I thought I
would tell you of latest results (and improvements). All solutions use the
repeated triangular pattern of circles with some adjustments at each end.
The most found "solution" has 333 circles in a 2x166 rectangle and is given
as the solution to the problem presented in the Technology Review Puzzle
Corner, Jan. 1989. The problem was presented again in the Pi Mu Epsilon
Journal (1995, problem 860) with the same solution published. A reader
noticed a posible improvement by adjusting the 5 circles on each end of the
pattern and achieved 331 circles in a 2x165 rectangle. More recently, Nick
Baxter improved it again by adjusting 7 circles at each end to achieve 329
circles in a 2x164 rectangle. Nick and I each examined things more
completely, trying up to 35 adjusted circles on each end. the most
efficient case is 13 circles on each end, giving 329 circles in a
2x163.9973967.. rectangle. We then tracked down a note by Hiroshi Yabe of
Kyoto University who displayed the same result about 8-10 years ago.
All the best, Dick Hess