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