# 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?

• Do they need to be whole? (Kidding.) Jan 22, 2020 at 12:38
• @GarethMcCaughan I only have an estimate which I doubt is optimal. There are indeed multiple previous attempts to tackle this type of problem (for example :www2.stetson.edu/~efriedma/mathmagic) but, as far as I am aware, not precisely my mother's conundrum. Jan 22, 2020 at 13:59
• See The end of open-ended puzzles. This is an optimization problem, for which the community has reached a consensus that "answers should come with justification of why they are optimal; an answer without this is not a full answer." Answers should give some reasoning as to why they are indeed THE best answer, by showing they reach the theoretical bound possible for any solution, or by showing why the theoretical bound is unattainable and why they come as close as possible to it.
– Rubio
Jan 22, 2020 at 17:59
• An upper bound can be found here: a square of side length 50.1812 and area 2518.16. A simple lower bound is the areas of the disks, 2042.03 Jan 22, 2020 at 18:05
• Rob Pratt has posted in mathoverflow the following improved solution: mathoverflow.net/questions/351125/… Jan 26, 2020 at 2:46

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? Jan 28, 2020 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. Jan 29, 2020 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. Jan 29, 2020 at 18:27
• Since $w \cdot h$ (objective function) is being minimized, what would be added to $w \cdot h$ to penalize the objective function when each of the 3 constraints are violated? What would the constraints look like if they were re-written using $r_i$, the radius of the $i$th circle, and what are the equations for $w$ and $h$, which change at each iteration? May 24, 2023 at 18:35

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. Jan 23, 2020 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. Jan 24, 2020 at 2:50