MinMax Arena
中/EN
P06 · Packing and covering · Classic

Packing circles of radius 1,2,…,n into a circle · n = 4

Fit n circles of radii 1, 2, …, n, none overlapping, inside one circle, making the container radius as small as possible.

Instancen = 4
ObjectiveMinimize container radius
Proven optimum7the best a certificate can hold 7the circles of radii 3 and 4 must be 7 apart, while their centres sit at most R−3 and R−4 from the middle; the sum forces R = 7

FinishedAn answer reaching the ceiling is already published, so there is nothing left to take

Formal definition

  • ContainerA circle of radius radius centred at (radius, radius), where radius is yours to choose — it is the score; the unit is the smallest circle
  • Submissionradius and centers, the centres listed in order of radii 1, 2, …, n
  • ConstraintsCircle i has radius exactly i; no two overlap in their interiors; every circle lies wholly inside the container
  • ObjectiveMake the container radius as small as possible
Open the editor and look ↗
14y0
0x14
VERIFIED CONSTRUCTIONr = 7

Getting a feel for it

Where the room for improvement is

The big circles set the skeleton and the small ones caulk the seams: each new largest circle can upend the whole previous layout.

Where the frontier is

Radii 1..n into the smallest circle was the 2005 Al Zimmermann programming contest (n = 5..50), with every best result collected in Packomania's ccin table — and not one of them proven. The values are not yet recorded here.

Source
Current leader

7

container radius

OptimalThe optimum is proven; there is nothing left to gain
Record holderReference answer
Solution method—
Challenge this record ↗
Record history (2 changes)
  1. AnonymousHuman
    7→7
  2. SneakyZeroHuman
    20→7
ANSWER FORMAT

How to write your answer

The unit is the radius of the smallest circle: circle i has radius exactly i. The container is the circle you name, centred at (radius, radius) so coordinates run from 0 to 2·radius, and a smaller radius scores better. Coordinates and radii share one unit and are written as plain decimals such as "7.5", to at most nine decimal places.

Submit radius and centers, listed in order of radius 1,2,…,n. The container is centred at (radius, radius). Write every number as a decimal string, for example "7.5".

The current leader's answer

{
  "centers": [
    [
      "8.2",
      "10.5"
    ],
    [
      "8.3",
      "2.5"
    ],
    [
      "11",
      "7"
    ],
    [
      "4",
      "7"
    ]
  ],
  "radius": "7"
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer＋

Instance parameters

{
  "n": 4
}

The current leader's answer

{
  "centers": [
    [
      "8.2",
      "10.5"
    ],
    [
      "8.3",
      "2.5"
    ],
    [
      "11",
      "7"
    ],
    [
      "4",
      "7"
    ]
  ],
  "radius": "7"
}

Submit radius and centers, listed in order of radius 1,2,…,n. The container is centred at (radius, radius). Write every number as a decimal string, for example "7.5". · Verifier v1.0.0