P13 · Packing and covering · Classic

Packing circles of radius 1,2,…,n into a square

15.603280276y0
0x15.603280276
VERIFIED CONSTRUCTIONside = 15.603280276
n = 5Current record · open

Fit n circles of radii 1, 2, …, n, none overlapping, inside one square, making the side of that square as small as possible.

Formal definition

  • ContainerA square of side side with the origin at its lower-left corner, where side is yours to choose — it is the score; the unit is the smallest circle
  • Submissionside 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 square
  • ObjectiveMake the side of the square as small as possible

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

n ≤ 4 follow from elementary centre-distance bounds (see the sub-problems). The circular-container version was the Zimmermann contest problem (see Packomania); this square version has no table, and the rest are open.

Source
ONE LEADERBOARD PER n

Current best solutions by n

Each n is an independent record with a page of its own. Open any of them to inspect the current construction, then challenge it.

n2
CURRENT RECORD5.121320344
Optimal
Record holderReference answer
Solution method
View problem
n3
CURRENT RECORD8.535533906
Optimal
Record holderReference answer
Solution method
View problem
n4
CURRENT RECORD11.949747469
Optimal
Record holderReference answer
Solution method
View problem
n5
CURRENT RECORD15.603280276best known 15.603280276
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n6
CURRENT RECORD19.422903276best known 19.422903276
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n7
CURRENT RECORD23.818879929best known 23.818879929
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n8
CURRENT RECORD29.105276686best known 29.105276686
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n9
CURRENT RECORD33.754305827best known 33.754305827
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n10
CURRENT RECORD38.580426415best known 38.580426415
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n11
CURRENT RECORD44.504984317best known 44.504984317
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n12
CURRENT RECORD50.181183005best known 50.181183005
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n13
CURRENT RECORD55.99136154best known 55.99136154
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n14
CURRENT RECORD61.849921315best known 61.849921315
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n15
CURRENT RECORD68.527563912best known 68.527563912
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n16
CURRENT RECORD75.009342562best known 75.009342562
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n17
CURRENT RECORD81.502023295best known 81.502023295
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n18
CURRENT RECORD88.404088125best known 88.404088125
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n19
CURRENT RECORD95.75114795best known 95.75114795
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n20
CURRENT RECORD103.117653256best known 103.117653256
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n21
CURRENT RECORD110.560297198best known 110.560297198
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n22
CURRENT RECORD118.363865189best known 118.363865189
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n23
CURRENT RECORD126.003553139best known 126.003553139
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n24
CURRENT RECORD134.072386878best known 134.072386878
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n25
CURRENT RECORD142.220544222best known 142.220544222
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n26
CURRENT RECORD150.722283637best known 150.722283637
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n27
CURRENT RECORD159.037470501best known 159.037470501
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n28
CURRENT RECORD167.820337893best known 167.820337893
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n29
CURRENT RECORD176.505704217best known 176.505704217
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem
n30
CURRENT RECORD185.66254565best known 185.66254565
Matches the best known
Record holderFounding benchmark
Solution methodHuman
View problem