Circles inside a circle

Shape and space, angle and circle properties, ...
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Circles inside a circle

Hi everybody,

We have 20 circles c(i) with i=1 to 20.
The diameter d(1) of c(1) is equal to 1 cm (centimeter)
d(2)=2 cms
d(3)=3 cms
.....
d(19)= 19 cms
d(20)=20 cms

What is the minimal diameter of the circle where you can place all the 20 circles?
No intersection is allowed. Circles can touch each one another.

Thank for any comment

euler
Posts: 3257
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: Circles inside a circle

Finding the optimal arrangement for n unit circles so that they can be packed inside the smallest possible circle is an unsolved problem. Optimal arrangements for n = 1 to 11 have been proved, but for n > 11 it is only possible to cite the best known arrangement. For example, here are the cases for n = 1 to 20:
http://www2.stetson.edu/~efriedma/cirincir/

Unless I'm missing something - and your question is a special case I am unaware of which leads to an elegant solution - then what you're asking for (twenty circles of different sizes) is more than what is currently known about twenty identical unit circles.

impudens simia et macrologus profundus fabulae

Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Circles inside a circle

I know the case you are talking about.
But the 20 circles are not identical.
And the circle where you have to place those circles is not fixed. Not easy to find a solution. We can find bounds (lower and upper) and maybe we can build some algorithm to reach the solution by approximations.

Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Circles inside a circle

The lower bound is easy to find.
Sum the area of the 20 circles divide by pi compute the square root and multiply by 2 to obtain the lower diameter.
Computing the upper bound ?
Pack the circles as squares in some bigger square.
Then it will be easy to pack the square in a circle to obtain the upper diameter.
Compute the upper and the lower bound of the area between 4 circles.
Compute the number of those areas.
Reduce the upper bound until you reach some value (diameter).
Check the diameter obtained by reduction to arrange the circles such as it fits
Repeat the process of reduction until you reach the required solution.

Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Circles inside a circle

I think that if we physical mechanism it will be more easier to find a solution.
You cut 20 circles with diameter ranging from 1 to 20.
You cut k circles with diameter ranging gradually from the lower bound to the lower.
The you start placing the 20 circles using the gravity. You shake the 20 circles inside a big circle and you see if they are packing or no.

What do you think about the idea ?

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Circles inside a circle

I think a simulation using gravity between the circles would be an interesting thing to watch in a GUI. The shaking could be accomplished by varying the masses of the circles -- something which is hard to do in the physical world.

Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Circles inside a circle

It would be more interesting if some programmer produce a software and distribute it freely to all members of Projecteuler. So each one could test on his computer the k circles and send his solution here. The best solution will be published here.
It will attract lot of people.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Circles inside a circle

Alhazen wrote:The lower bound is easy to find.
Sum the area of the 20 circles divide by pi compute the square root and multiply by 2 to obtain the lower diameter.
Pi cancels out of that expression.

sqrt(12+22+32+...+n2) = sqrt((2n3+3n2+n)/6)

For n < 10, the sum of the two largest diameters, 2n-1, is greater. But I guess you're only concerned with n=20.

Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Circles inside a circle

Not specially.
In fact a general formula will be helpful.
I think the more n grows the likely some general formula will work.
I maybe wrong. I'm not so sure.