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

## Circles inside a circle

- euler
- Administrator
**Posts:**3634**Joined:**Sun Mar 05, 2006 4:49 pm**Location:**Cheshire, England-
**Contact:**

### Re: Circles inside a circle

Finding the optimal arrangement for n

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.

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

### Re: Circles inside a circle

Thank you for your comment.

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.

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.

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

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.

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

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 ?

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

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

It will attract lot of people.

### Re: Circles inside a circle

Pi cancels out of that expression.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.

sqrt(1

^{2}+2

^{2}+3

^{2}+...+n

^{2}) = sqrt((2n

^{3}+3n

^{2}+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.

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

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.