Subject: puzzle du jar
Date: Tue, 14 Feb 1995 12:30:02 MST
From: "Richard Schroeppel"
I was stuffing soft drinks into my refrigerator door, shuffling around
the mayonnaise; reminded me of a puzzle I've meant to present for years:
Suppose we consider a restricted packing problem: The area to be packed is
a refrigerator-door shelf-with-guard-rail. Idealize it as a one-ended
infinite strip, say of height 1. The things to be packed are circles
(soda cans, mayonnaise jar, jelly, grated parmesan cheese, beer, etc.).
You have a specific finite set of these objects; lots of soda, only one
cheese, two beers, ...
The goal is to use the smallest amount of the infinite strip as possible;
the criterion is the maximum X-coordinate of the rightmost point of the
circles. (I.e., will everything fit on the shelf?)
Assume that all the circles are fairly large, so that the only reasonable
packing is to push alternate circles to the back and the front of the
shelf (top and bottom of the strip). This is true if the smallest radius
exceeds 1/(1+1+sqrt3) = 2 - sqrt3 = .2679...
________________
| / \
| _( )_
| / \__/ \ ....
|( )( )
|_\__/__\__/_____
The computational problem is to find the best ordering of the circles.
My experience seems to show you should alternate big and little, but
I haven't done the numbers. If you pick a particular ordering, then
you can compute the amount of space required easily enough - it only
depends on the adjacencies of the circles. So the problem is at worst
NP (blatantly ignoring some fine points about the difficulty of comparing
sums of algebraic numbers).
Is there some rule or heuristic that cuts down on the amount of search?
(Beyond the dynamic-programming rule that the placement of any 4+
set of circles must have an optimal interior, and the same for any
3+ set of circles at either end. This gives a reduction similar to
the traveling salesman, from around N! to around 2^N. In fact, the
problem could be recast as a TSP, with each circle being a city, and
the edge lengths equal to the amount of horizontal space needed between
the centers of adjacent circles.)
Rich
SPOILER: by Dean Hickerson --------------------------------------------------
rcs> Suppose we consider a restricted packing problem: The area to be packed
> is a refrigerator-door shelf-with-guard-rail. Idealize it as a one-ended
> infinite strip, say of height 1. The things to be packed are circles
> (soda cans, mayonnaise jar, jelly, grated parmesan cheese, beer, etc.).
> ...
> Is there some rule or heuristic that cuts down on the amount of search?
drh> I looked at this problem about 10 years ago. As I recall, the optimal
> placement is as follows: Put the largest circle at one end, the next
> largest at the other end, the third largest next to the largest, the
> fourth next to the second, and so on. E.g. if there are 10 circles
> A >= B >= C >= ... >= J, place them as shown below:
>
> C G J F B
> A E I H D
>
> I'll see if I can reconstruct the proof.
I should have said "AN optimal placement". If the radii are
distinct, then the arrangement is unique, but if they're not then
it needn't be. For example, if the radii are r, r, r, r, and s, with
r!=s, then the arrangements (r s r r r) and (r r s r r) give the same
size rectangle. To keep things simple, I'm going to assume that all
the radii are distinct. (If they're not, then we can change them all
by some very small amounts to make them distinct, apply the result
for distinct radii, and change them back to show that the arrangement
described above is optimal. Details are left to the reader.)
First consider 2 adjacent circles, of radii a and b. The distance
between their centers is a+b. The vertical distance between their
centers is 1-a-b. Hence the horizontal distance between their
centers is sqrt((a+b)^2 - (1-a-b)^2) = sqrt(2a+2b-1).
Now suppose the radii of the circles, in order from one end of
the rectangle to the other, are a_0, a_1, ..., a_n. Then the
length of the rectangle is
a + sqrt(2 a + 2 a - 1) + ... + sqrt(2 a + 2 a - 1) + a .
0 0 1 n-1 n n
Suppose that the circles are arranged so that this is minimal.
Let's consider the effect of reversing various subsequences of the
sequence of radii.
First, I claim that the largest 2 circles must be at the ends. For
suppose not. Then one end circle will have radius, say a, that's
smaller than the radius of some non-end circle, say r. Let s be
the radius of the circle adjacent to r on the other side from a.
Thus the sequence of radii looks like (a ... r s ...), with a= 0.
I claim that this condition, together with the fact that the largest
2 radii are at the ends, forces the ordering of the radii to be as
stated earlier.
Let the radii, listed in nonincreasing order, be b_0 > ... > b_n.
Wlog a_0 = b_0 and a_n = b_1. Suppose that a_1 != b_2. Let
b_2 = a_i, where 2 <= i <= n-1. Now applying the condition above
with a = a_0, b = a_1, c = a_i, and d = a_(i+1) gives a
contradiction: In
(a - d) (b - c) = (a - a ) (a - a ) >= 0,
0 i+1 1 i
the first factor is positive but the second is negative. Therefore
a_1 = b_2. So the arrangement looks like this:
b b ... b ,
0 2 1
where we don't yet know the ordering between b_2 and b_1.
At this point we use induction on the number of circles. If the
ordering between b_2 and b_1 isn't optimal for the set of radii
{b_1, ..., b_n}, then we could rearrange it and get a better
ordering of {b_0, ..., b_n}. Hence the ordering between b_2 and
b_1 must be (b_2 b_4 b_6 ... b_5 b_3 b_1), and the proof is
complete.
Dean Hickerson
drhickerson@ucdavis.edu