An interesting math problem -- any ideas?

[Alex Franke]

This is an academic question, really, because I wrote some code to figure it out using a sort-of genetic algorithm. But it seems like there should be an easier way to figure this out with straight math. I know there are some math geeks on this forum, so I thought I'd post the question. (It came up as I was designing a hole test pattern for metric drill bit sizes to be produced by a 3D printer.)

Suppose you have 100 marbles, with sizes ranging from 100mm diameter all the way down to 1mm, and you wanted to organize them into the smallest area flat surface as possible, arranged roughly in rows of 10 in order of size -- so 1-10 in the first row, 11-21 in the second, etc. [edit: The smallest area of a plane on which all the spheres are centered, not tangent. Thanks, Sid!)

Is there an easier way (without doing what I ended up doing) to calculate the ideal positions?

As an example, here's what I came up with in code for a 7x12 arrangement (12 because the drill bits include 1/4 measurement in addition to 1/10: 3.0, 3.1, 3.2, 3.25, 3.3, 3.4, 3.5, 3.6, 3.7, 3.75, 3.8, 3.9 -- but that's really beside the point.) I also added in some padding between the circles in this example.

[radhak]

Without doing any calculations, wouldn't the best arrangement be alternating the largest-to-smallest with the smallest-to-largest rows? ie, the first two rows would be
100, 99, 98, 97, 96, 95, 94, 93, 92, 91
001, 02, 03, 04, 05, 06, 07, 08, 09, 10

so essentially, any two adjoining circles/spheres in a pair of such rows would add up to 101mm in total space covered, with minimal wastage of space.

But, I gotta add, it would be counterproductive for practical purposes : if my drill bits were so arranged, it would be a pain to pick the right size by trial-and-error.

[Sid]

Three dimensions?

By restating the problem as arranging marbles (spheres) instead of holes, on a flat surface, you've gone from two to three dimensions. Smaller marbles could be placed, wholly or partially, within the vertical projections of the larger ones--a much more difficult problem. I suspect that was not your intention.

Not that I have a solution for the simpler problem,
Sid

[Alex Franke]

Without doing any calculations, wouldn't the best arrangement be alternating the largest-to-smallest with the smallest-to-largest rows?

That was my first thought, actually, but I'm not sure if it gains you anything because the circles like to neighbor six others of similar size. (I think the more similar the size the better.)

By restating the problem as arranging marbles (spheres) instead of holes, on a flat surface, you've gone from two to three dimensions. Smaller marbles could be placed, wholly or partially, within the vertical projections of the larger ones--a much more difficult problem. I suspect that was not your intention.

Yes, excellent point. You're right; it was not my intention. The spheres would all have to be centered on the same plane, not tangent to the same plane. I'll go back and clarify that in the OP.

[gsmittle]

You guys make my brain hurt.

g.

[stocktr8er]

What about starting with the smallest in center and wrap around. Natural spiral

[Uncle Cracker]

On a Saturday?? Geez... Do you guys want to make my head explode??