My Mother's Dish Collection

From every trip she makes, my mother brings as a souvenir a well-decorated dish to hang in a wall. She now has a collection of 12 dishes, all disks, of radii 1, 2, 3, ..., 12 inches respectively.

What is the least area of a rectangular portion of a wall she needs to set aside in order to hang all 12 dishes, naturally no two of them overlapping?

I used a nonlinear optimization solver, with variables $$x_i$$, $$y_i$$, $$w$$, $$h$$. The problem is to minimize $$w\cdot h$$ subject to: \begin{align} i \le x_i &\le w - i &&\text{for i\in\{1,\dots,12\}}\\ i \le y_i &\le h - i &&\text{for i\in\{1,\dots,12\}}\\ (x_i - x_j)^2 + (y_i - y_j)^2 &\ge (i + j)^2 &&\text{for 1\le i The first two constraints make sure each circle is contained in the rectangle, and the third constraint prevents circles $$i$$ and $$j$$ from overlapping.

The resulting $$x$$ and $$y$$ coordinates returned by the solver are:

 1  1.2569 19.0521
2 20.7748  2.3556
3 55.5650 24.8786
4 39.3096 26.9070
5 24.1421 36.9762
6 35.0966 35.9762
7 28.5499  7.0000
8 49.1419 33.9063
9 26.8502 23.1972
10 10.0000 31.9762
11 11.0000 11.0000
12 46.6740 12.7025


The resulting plot looks very similar to @2012rcampion's, but my rectangle is smaller in both dimensions, my circle 12 does not touch the bottom, and my circle 3 is adjacent to 8 and 12 instead of 10 and 11. These changes allow other perturbations that decrease the area.

• Hi, Rob, and welcome to PSE! Would you mind adding a description of the process through which you arrived at this answer? – Brandon_J Jan 28 at 23:22
• I improved my answer before noticing this one is smaller... My program reports collisions between dishes 4 & 6, 4 & 9, 5 & 10 and 7 & 11. You have only posted to 4 decimal places, and the distances I get are off in the 5th decimal place such as: Dishes 5 and 10 distance should be 15 but is 14.999966413629064. – Weather Vane Jan 29 at 18:00
• I plotted an arrangement of this which does work without collisions, as the slightly larger 41.976177 x 58.739116 = 2465.64351726052973390324. I did this by placing 10 above 11 with their left edges aligned, 7 right of 11 with bottom edges aligned, and placing the rest each touching two dishes in the following obvious sequence: 2, 9, 5, 6, 4, 12, 8, 3. Using double precision arithmetic. – Weather Vane Jan 29 at 18:27

Area of 41.976177 x 58.870371 = 2471.15311908389276140952

With these positions:

1 1.000000 4.843750
2 2.000000 2.000000
3 3.522008 24.934399
4 19.499239 26.693782
5 34.713947 36.935578
6 23.780082 35.731170
7 30.255856 7.294753
8 9.900886 33.895978
9 32.020172 23.197180
10 48.870371 31.976177
11 47.870371 11.000000
12 12.000000 12.560084

This is similar to another answer but with a smaller area. I worked it out completely independently, then noticed its similarity. The 3" dish is in a different place, and it is not an adjustment based on that answer. It was generated by a C program I wrote for this purpose. It gave my previous answers and has been spitting out smaller results since and is still running.

My method is to:

Permute three of the dishes all touching. Then a recursive approach to place every dish touching two other dishes, in all their permutations, with or without gaps between it and other nearby dishes. When all dishes have been legally placed, I rotate the arrangement to find the minimum enclosing orthoganal area, and compare that with the previous best result. Repeat with the next set of three dishes.

There is space for some of the dishes to move, so the packing is not "tight" and perhaps there is a smaller result yet to be found.

I also spent some quality time on advanced research in the manner shown below...

Notice that I didn't research the 1" or 2" dishes, nor consider them in my C program. The 1" dish will fit almost anywhere so there is no point bogging down the attempt at a solution. Likewise the 2" dish will fit at the edge between any of 13 pairs of the larger dishes, as can be found by implementing Descartes' theorem. The 2" dish will also fit in a corner, but only with the 12" dish. So I fitted them after finding solutions.

Work in progress (may not be optimal)

Area:  2473.592325980820677329192630787413
Width:   58.880231554607604147164965389745
Height:  42.010574019002012267977540104353
Density: 82.553426584700634823250418092061

Picture:

Diagram of contacts:

Note that circle 9 has > 0.05 of space around it.

Coordinates (unconstrained circles at reduced precision):

 1  35.850063145444700000000000000000  31.544914406884400000000000000000
2   2.641501452602700000000000000000  23.853309646642000000000000000000
3  55.880231554607604147164965389745  22.489125293076057319701222936438
4  17.702494624525237853037620652988  26.949299483830697762652394604450
5  32.886993504649567609226398184286  37.010574019002012267977540104353
6  21.932542354546245340087002528270  36.010574019002012267977540104353
7  30.330302779823360026352188774912   7.000000000000000000000000000000
8   8.000000000000000000000000000000  34.010574019002012267977540104353
9  30.197611627225600000000000000000  23.054281315130800000000000000000
10  47.029129128380518097243285426383  32.010574019002012267977540104353
11  47.880231554607604147164965389745  11.000000000000000000000000000000
12  12.000000000000000000000000000000  12.000000000000000000000000000000

2,613.6 in2

Because

I put 12 circles into a space using MS Paint (no math skills used, just trial and error).

I tried to leave as few gaps as I could. So, here's what I did.

conversion: 12 in radius = 120 pixels, 1 in radius = 10 pixels, etc...So, had to multiply by 2 for diameter (edit)

So, 39.6 in X 66.0 in = 2,613.6 in2

-EDIT- Reconfigured circles based on Weather Vane's theorem conclusion that (3) would not actually fit between (11) and (12) as positioned. Also moved other things around a bit.

I'm confident this could be tweaked even more to find a tighter fit.

• It's a nice try, but I think I my calculation is right giving the largest radius dish you can get between touching 11" and 12" dishes and an edge as 2.87" – see Descartes' theorem. However, it looks as if there is room to move the 4, 5, 6, 9, and 11 inch dishes to the right, which might make enough room. – Weather Vane Jan 23 at 14:52
• Sorry, I just realized what you were talking about. I saw "theorem" and went, "oh boy, I'm in over my head." So, I'll look at a little bit tomorrow. Paint is a little blocky when it comes to small circles. Or we can pretend I moved the 9 and 11 over a bit :) thank you. – MacGyver88 Jan 24 at 2:50