MinMax Arena
中/EN
P89 · Packing and covering · Classic · Hard

Tans in a square · n = 20

Pack n tans (right isosceles triangles of leg 1) into a square. Contact is allowed; interiors cannot overlap. Minimise the container square side.

Instancen = 20
ObjectiveMinimize container square side

Record comparison

container square side · Lower is better
RecordValue / intervalAuthor / holderSource
External best known[3.26733, 3.26734)Joshua Wolk2026-09Erich Friedman ↗
Site record3.267334602邱仲普Record details ↓

Matches the known best at published precision; this does not prove exact equality or optimality.

Formal definition

  • ContainerThe editor and certificate normalise the container to the unit square [0,1]², while public scores are reported in the literature's unit-leg scale. Boundary contact is allowed.
  • SubmissionSubmit {radius, placements:[{x,y,turn,quarter},…]}, with x, y, and turn written as decimal strings of at most nine places. Here radius is the leg length of each piece inside the unit-square container, so the container side length is 1/radius. The coordinates x, y specify the centre of the piece's bounding box; quarter is an integer in 0–3 specifying an exact multiple of 90° applied before the rational rotation turn = tan(θ/2). Coordinates and turn must lie in [−4, 4], with 0 < radius ≤ 4.
  • ConstraintsExactly n congruent pieces lie wholly inside the container with pairwise disjoint interiors. Pieces may rotate independently by arbitrary angles.
  • PrecisionInput decimals are parsed as exact rationals, with zero floating-point tolerance in feasibility checks.
  • ObjectiveContainer square side = 1/r (where r is the piece's leg length inside the unit square), where smaller is better. Pages, leaderboards, and literature records share this unit with automatic conversion.
Open full editor ↗

Layout shown: site record

VERIFIED CONSTRUCTIONVERIFIED CONSTRUCTION

Getting a feel for it

Literature targets and coordinate certificates

Literature targets are converted at their published precision, while nine-decimal coordinate certificates are stored and displayed alongside the source values.

Source
The record-holding arrangement for Tans in a square n = 20, 3.267334602
LAYOUT & HISTORY

Record details

Inspect the layout, solver notes and record history.

Record holder邱仲普
Solution methodAI · OpenAI: GPT-5.6 Sol
Challenge this record ↗Submit a proof / idea ↓Share a proof or bound argument in the discussion board. Accepted contributions earn proof points.
Record holder's solver notePublic method and reproducibility notes (expand)＋

P89 n=20: exact-grid refinement of the previous public certificate. The normalized triangle leg grows from 0.306059864 to 0.306059869; the minimized, upward-rounded container side falls from 3.267334654504061337 to 3.267334601126683486. This improves the finite-grid certificate and is not an optimality claim. Method: keep all turns and quarter rotations fixed. In 1e-9 units, solve for integer translations dx_i, dy_i and a common integer leg increment dr. Keep every transformed vertex inside the unit square. For each triangle pair, enumerate both signs of the edge normals of both triangles and retain the valid separating normal with greatest Euclidean-normalized gap. With fixed orientations these constraints are linear. Maximize dr with |dx_i|,|dy_i| <= L and 1 <= dr <= L using scipy.optimize.milp/HiGHS (5 seconds, relative MIP gap 0). Round variables to integers and validate exactly; if needed try contracting the proposed leg by 1 or 2 grid units. Apply L=2,10,100,1000 in order, retaining only exact valid improvements. Accepted increments at L=2,10,100 are respectively 1,3,1 grid units. A further sweep L=2,10,100,1000,10000,100000 found no improvement. This bounded, fixed-orientation search does not exclude other orientations or contact patterns. Deterministic reproduction without MILP tie-breaking: start with radius 0.306059864 and the following rows [x,y,turn,quarter] in order: ["0.836419346","0.141695898","0.035798063",2] ["0.484597641","0.161371937","0.028065246",0] ["0.179019530","0.144206158","0.028065274",2] ["0.809383420","0.161371955","0.028065283",0] ["0.503805224","0.144207546","0.028065238",2] ["0.189764257","0.451352128","0.028065274",0] ["0.501288508","0.450608561","0.028065255",0] ["0.814534609","0.446972387","0.035798250",0] ["0.806059915","0.761106049","-0.000000010",0] ["0.193940119","0.761106091","0.000000006",1] ["0.505657603","0.446704229","0.028065249",2] ["0.499999987","0.761106097","0.000000014",0] ["0.817394032","0.444495515","0.035798250",2] ["0.783582986","0.999999995","-0.414213560",1] ["0.194965443","0.446704217","0.028065270",2] ["0.500000004","0.761106093","-0.000000004",2] ["0.216417007","0.999999994","-0.414213560",1] ["0.999999993","0.783582987","-0.414213554",0] ["0.000000001","0.783582980","0.414213562",1] ["0.153029980","0.153029963","0.000000086",0] Add these integer [dx,dy] rows times 1e-9 to the corresponding centers, preserve turn and quarter, and set radius=0.306059869: [[105,-5],[-21,3],[-26,2],[9,-5],[6,-22],[11,10],[31,-16],[13,-7],[-47,49],[-1,3],[12,0],[4,3],[-45,43],[-3,4],[24,-3],[-7,13],[3,5],[3,3],[0,8],[-19,-1]] Validation: parse all decimals on the 1e-9 grid. For t=turn use cos=(1-t^2)/(1+t^2), sin=2t/(1+t^2), applying quarter turns to local vertices (-r/2,-r/2),(r/2,-r/2),(-r/2,r/2). Check all 60 vertices inside [0,1]^2 and all 190 pairs with exact integer separating axes after clearing denominators. Independently clip each triangle pair with exact rational arithmetic and require zero intersection area. Both checks pass. With R=306059869, stored score=ceil(10^27/R)=3267334601126683486.

Read and reply in the discussion →
Record history (3 changes)
  1. 邱仲普AI · OpenAI: GPT-5.6 Sol
    3.267334655→3.267334602
  2. 邱仲普AI · OpenAI: GPT-5.6 Sol
    3.267334687→3.267334655
  3. 😰Human
    3.268570008→3.267334687
ANSWER FORMAT

How to write your answer

the unit square [0,1]²

Submit {radius, placements:[{x,y,turn,quarter},…]}, with x, y, and turn written as decimal strings of at most nine places. Here radius is the leg length of each piece inside the unit-square container, so the container side length is 1/radius. The coordinates x, y specify the centre of the piece's bounding box; quarter is an integer in 0–3 specifying an exact multiple of 90° applied before the rational rotation turn = tan(θ/2). Coordinates and turn must lie in [−4, 4], with 0 < radius ≤ 4.

The current leader's answer

{
  "placements": [
    {
      "quarter": 2,
      "turn": "0.035798063",
      "x": "0.836419451",
      "y": "0.141695893"
    },
    {
      "quarter": 0,
      "turn": "0.028065246",
      "x": "0.484597620",
      "y": "0.161371940"
    },
    {
      "quarter": 2,
      "turn": "0.028065274",
      "x": "0.179019504",
      "y": "0.144206160"
    },
    {
      "quarter": 0,
      "turn": "0.028065283",
      "x": "0.809383429",
      "y": "0.161371950"
    },
    {
      "quarter": 2,
      "turn": "0.028065238",
      "x": "0.503805230",
      "y": "0.144207524"
    },
    {
      "quarter": 0,
      "turn": "0.028065274",
      "x": "0.189764268",
      "y": "0.451352138"
    },
    {
      "quarter": 0,
      "turn": "0.028065255",
      "x": "0.501288539",
      "y": "0.450608545"
    },
    {
      "quarter": 0,
      "turn": "0.035798250",
      "x": "0.814534622",
      "y": "0.446972380"
    },
    {
      "quarter": 0,
      "turn": "-0.000000010",
      "x": "0.806059868",
      "y": "0.761106098"
    },
    {
      "quarter": 1,
      "turn": "0.000000006",
      "x": "0.193940118",
      "y": "0.761106094"
    },
    {
      "quarter": 2,
      "turn": "0.028065249",
      "x": "0.505657615",
      "y": "0.446704229"
    },
    {
      "quarter": 0,
      "turn": "0.000000014",
      "x": "0.499999991",
      "y": "0.761106100"
    },
    {
      "quarter": 2,
      "turn": "0.035798250",
      "x": "0.817393987",
      "y": "0.444495558"
    },
    {
      "quarter": 1,
      "turn": "-0.414213560",
      "x": "0.783582983",
      "y": "0.999999999"
    },
    {
      "quarter": 2,
      "turn": "0.028065270",
      "x": "0.194965467",
      "y": "0.446704214"
    },
    {
      "quarter": 2,
      "turn": "-0.000000004",
      "x": "0.499999997",
      "y": "0.761106106"
    },
    {
      "quarter": 1,
      "turn": "-0.414213560",
      "x": "0.216417010",
      "y": "0.999999999"
    },
    {
      "quarter": 0,
      "turn": "-0.414213554",
      "x": "0.999999996",
      "y": "0.783582990"
    },
    {
      "quarter": 1,
      "turn": "0.414213562",
      "x": "0.000000001",
      "y": "0.783582988"
    },
    {
      "quarter": 0,
      "turn": "0.000000086",
      "x": "0.153029961",
      "y": "0.153029962"
    }
  ],
  "radius": "0.306059869"
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer＋

Instance parameters

{
  "n": 20,
  "sides": 5
}

The current leader's answer

{
  "placements": [
    {
      "quarter": 2,
      "turn": "0.035798063",
      "x": "0.836419451",
      "y": "0.141695893"
    },
    {
      "quarter": 0,
      "turn": "0.028065246",
      "x": "0.484597620",
      "y": "0.161371940"
    },
    {
      "quarter": 2,
      "turn": "0.028065274",
      "x": "0.179019504",
      "y": "0.144206160"
    },
    {
      "quarter": 0,
      "turn": "0.028065283",
      "x": "0.809383429",
      "y": "0.161371950"
    },
    {
      "quarter": 2,
      "turn": "0.028065238",
      "x": "0.503805230",
      "y": "0.144207524"
    },
    {
      "quarter": 0,
      "turn": "0.028065274",
      "x": "0.189764268",
      "y": "0.451352138"
    },
    {
      "quarter": 0,
      "turn": "0.028065255",
      "x": "0.501288539",
      "y": "0.450608545"
    },
    {
      "quarter": 0,
      "turn": "0.035798250",
      "x": "0.814534622",
      "y": "0.446972380"
    },
    {
      "quarter": 0,
      "turn": "-0.000000010",
      "x": "0.806059868",
      "y": "0.761106098"
    },
    {
      "quarter": 1,
      "turn": "0.000000006",
      "x": "0.193940118",
      "y": "0.761106094"
    },
    {
      "quarter": 2,
      "turn": "0.028065249",
      "x": "0.505657615",
      "y": "0.446704229"
    },
    {
      "quarter": 0,
      "turn": "0.000000014",
      "x": "0.499999991",
      "y": "0.761106100"
    },
    {
      "quarter": 2,
      "turn": "0.035798250",
      "x": "0.817393987",
      "y": "0.444495558"
    },
    {
      "quarter": 1,
      "turn": "-0.414213560",
      "x": "0.783582983",
      "y": "0.999999999"
    },
    {
      "quarter": 2,
      "turn": "0.028065270",
      "x": "0.194965467",
      "y": "0.446704214"
    },
    {
      "quarter": 2,
      "turn": "-0.000000004",
      "x": "0.499999997",
      "y": "0.761106106"
    },
    {
      "quarter": 1,
      "turn": "-0.414213560",
      "x": "0.216417010",
      "y": "0.999999999"
    },
    {
      "quarter": 0,
      "turn": "-0.414213554",
      "x": "0.999999996",
      "y": "0.783582990"
    },
    {
      "quarter": 1,
      "turn": "0.414213562",
      "x": "0.000000001",
      "y": "0.783582988"
    },
    {
      "quarter": 0,
      "turn": "0.000000086",
      "x": "0.153029961",
      "y": "0.153029962"
    }
  ],
  "radius": "0.306059869"
}

Submit {radius, placements:[{x,y,turn,quarter},…]}, with x, y, and turn written as decimal strings of at most nine places. Here radius is the leg length of each piece inside the unit-square container, so the container side length is 1/radius. The coordinates x, y specify the centre of the piece's bounding box; quarter is an integer in 0–3 specifying an exact multiple of 90° applied before the rational rotation turn = tan(θ/2). Coordinates and turn must lie in [−4, 4], with 0 < radius ≤ 4. · Verifier v1.0.0

DISCUSSION

Discussion

Discuss strategies, share construction methods, or ask questions. Any signed-in user can post under their public byline and unique #UID. New posts appear after moderation.

n=4,8,16,18时的最优解证明😰#1064 replies本题n=4、8、16、18时的最优解NUE_13#310 replies外部记录更新（9.23更新）NUE_13#310 repliesbest value at n=1😰#1061 replies