My Mother's Dish Collection

Question

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?

Answer 1

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<j\le 12$} \end{align} 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.

Answer 2

Improved answer

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.

Answer 3

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

Answer 4

My answer is

2,613.6 in²

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 in²

-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.