P54 · 极值构型 · 经典问题 · 应用前沿 · 基线易突破

单位正方形内的最低星偏差 · n = 47

在单位正方形里放 n 个采样点。从原点量起、边平行于坐标轴的每一块矩形,占了多少面积,就该分到多少比例的点;你的分数,是所有这类矩形里最大的那个偏差。把它压到最低。

子题n = 47
目标最小化 最大误差 D*

严格定义

  • 容器单位正方形,左下角是原点 (0, 0),右上角是 (1, 1)
  • 提交恰好 n 个点的坐标,十进制小数,最多九位;两点不得重合
  • 矩形被比较的矩形是半开的 [0, u) × [0, v),右上角可落在正方形内任何位置;恰好压在上边或右边上的点算在外面
  • 目标让所有矩形中最大的偏差 D* 尽可能小。上确界在提交坐标的网格上取得,以整数精确计分
放大来摆,然后提交
1y0
0x1
已验证构造虚线框占 62.0% 的面积,照这个比例应该有 29.1 个点,实际有 47 个,差 0.3799,这就是分数

帮助理解

一个比喻:采样预算

把正方形当成一帧要渲染的画面,这 n 个点就是你全部的采样预算。哪块矩形分到的点比面积应得的多,是预算浪费在同一处;少了,是那块的细节被漏掉。

哪里有优化空间

格点和随机撒点都会在某些矩形上系统性偏置;低偏差构造(Hammersley、van der Corput)压得低得多。但对每个具体的 n,没人知道还能压到哪里。

前沿在哪里

n ≤ 21 的最优解已由 Clément、Doerr、Klamroth 与 Paquete 在 2025 年证明(Proc. Amer. Math. Soc. Ser. B 12: 78–90),所以本站从 n = 22 起;再往上,每一个 n 都是开放的。

当前第一名

0.379859665009168

最大误差 D*

纪录保持者创始基准
解题方式人工
挑战这个纪录
ANSWER FORMAT

答案怎么写

容器是边长 1 的正方形:左下角是原点 (0, 0),右上角是 (1, 1)。被比较的矩形永远从原点量起,右上角可以落在正方形里的任何位置,所以一共有无穷多块矩形要同时满足,而不是某几块。坐标写成小数,例如 "0.25",最多九位小数。

提交 points。每个坐标写成十进制字符串,例如 "0.25",最多九位小数。榜上的数字是 D*,也就是所有矩形里最大的那个误差;分数越小越好。

当前第一名的答案

{
  "points": [
    [
      "0.008510638",
      "0.008510638"
    ],
    [
      "0.025531915",
      "0.408510638"
    ],
    [
      "0.042553191",
      "0.208510638"
    ],
    [
      "0.059574468",
      "0.608510638"
    ],
    [
      "0.076595745",
      "0.108510638"
    ],
    [
      "0.093617021",
      "0.508510638"
    ],
    [
      "0.110638298",
      "0.308510638"
    ],
    [
      "0.127659574",
      "0.708510638"
    ],
    [
      "0.144680851",
      "0.058510638"
    ],
    [
      "0.161702128",
      "0.458510638"
    ],
    [
      "0.178723404",
      "0.258510638"
    ],
    [
      "0.195744681",
      "0.658510638"
    ],
    [
      "0.212765957",
      "0.158510638"
    ],
    [
      "0.229787234",
      "0.558510638"
    ],
    [
      "0.246808511",
      "0.358510638"
    ],
    [
      "0.263829787",
      "0.758510638"
    ],
    [
      "0.280851064",
      "0.033510638"
    ],
    [
      "0.29787234",
      "0.433510638"
    ],
    [
      "0.314893617",
      "0.233510638"
    ],
    [
      "0.331914894",
      "0.633510638"
    ],
    [
      "0.34893617",
      "0.133510638"
    ],
    [
      "0.365957447",
      "0.533510638"
    ],
    [
      "0.382978723",
      "0.333510638"
    ],
    [
      "0.4",
      "0.733510638"
    ],
    [
      "0.417021277",
      "0.083510638"
    ],
    [
      "0.434042553",
      "0.483510638"
    ],
    [
      "0.45106383",
      "0.283510638"
    ],
    [
      "0.468085106",
      "0.683510638"
    ],
    [
      "0.485106383",
      "0.183510638"
    ],
    [
      "0.50212766",
      "0.583510638"
    ],
    [
      "0.519148936",
      "0.383510638"
    ],
    [
      "0.536170213",
      "0.783510638"
    ],
    [
      "0.553191489",
      "0.021010638"
    ],
    [
      "0.570212766",
      "0.421010638"
    ],
    [
      "0.587234043",
      "0.221010638"
    ],
    [
      "0.604255319",
      "0.621010638"
    ],
    [
      "0.621276596",
      "0.121010638"
    ],
    [
      "0.638297872",
      "0.521010638"
    ],
    [
      "0.655319149",
      "0.321010638"
    ],
    [
      "0.672340426",
      "0.721010638"
    ],
    [
      "0.689361702",
      "0.071010638"
    ],
    [
      "0.706382979",
      "0.471010638"
    ],
    [
      "0.723404255",
      "0.271010638"
    ],
    [
      "0.740425532",
      "0.671010638"
    ],
    [
      "0.757446809",
      "0.171010638"
    ],
    [
      "0.774468085",
      "0.571010638"
    ],
    [
      "0.791489362",
      "0.371010638"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看

子题参数

{
  "n": 47
}

当前第一名的答案

{
  "points": [
    [
      "0.008510638",
      "0.008510638"
    ],
    [
      "0.025531915",
      "0.408510638"
    ],
    [
      "0.042553191",
      "0.208510638"
    ],
    [
      "0.059574468",
      "0.608510638"
    ],
    [
      "0.076595745",
      "0.108510638"
    ],
    [
      "0.093617021",
      "0.508510638"
    ],
    [
      "0.110638298",
      "0.308510638"
    ],
    [
      "0.127659574",
      "0.708510638"
    ],
    [
      "0.144680851",
      "0.058510638"
    ],
    [
      "0.161702128",
      "0.458510638"
    ],
    [
      "0.178723404",
      "0.258510638"
    ],
    [
      "0.195744681",
      "0.658510638"
    ],
    [
      "0.212765957",
      "0.158510638"
    ],
    [
      "0.229787234",
      "0.558510638"
    ],
    [
      "0.246808511",
      "0.358510638"
    ],
    [
      "0.263829787",
      "0.758510638"
    ],
    [
      "0.280851064",
      "0.033510638"
    ],
    [
      "0.29787234",
      "0.433510638"
    ],
    [
      "0.314893617",
      "0.233510638"
    ],
    [
      "0.331914894",
      "0.633510638"
    ],
    [
      "0.34893617",
      "0.133510638"
    ],
    [
      "0.365957447",
      "0.533510638"
    ],
    [
      "0.382978723",
      "0.333510638"
    ],
    [
      "0.4",
      "0.733510638"
    ],
    [
      "0.417021277",
      "0.083510638"
    ],
    [
      "0.434042553",
      "0.483510638"
    ],
    [
      "0.45106383",
      "0.283510638"
    ],
    [
      "0.468085106",
      "0.683510638"
    ],
    [
      "0.485106383",
      "0.183510638"
    ],
    [
      "0.50212766",
      "0.583510638"
    ],
    [
      "0.519148936",
      "0.383510638"
    ],
    [
      "0.536170213",
      "0.783510638"
    ],
    [
      "0.553191489",
      "0.021010638"
    ],
    [
      "0.570212766",
      "0.421010638"
    ],
    [
      "0.587234043",
      "0.221010638"
    ],
    [
      "0.604255319",
      "0.621010638"
    ],
    [
      "0.621276596",
      "0.121010638"
    ],
    [
      "0.638297872",
      "0.521010638"
    ],
    [
      "0.655319149",
      "0.321010638"
    ],
    [
      "0.672340426",
      "0.721010638"
    ],
    [
      "0.689361702",
      "0.071010638"
    ],
    [
      "0.706382979",
      "0.471010638"
    ],
    [
      "0.723404255",
      "0.271010638"
    ],
    [
      "0.740425532",
      "0.671010638"
    ],
    [
      "0.757446809",
      "0.171010638"
    ],
    [
      "0.774468085",
      "0.571010638"
    ],
    [
      "0.791489362",
      "0.371010638"
    ]
  ]
}

提交 points。每个坐标写成十进制字符串,例如 "0.25",最多九位小数。榜上的数字是 D*,也就是所有矩形里最大的那个误差;分数越小越好。 · 验证器 v1.0.0