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