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

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

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

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

严格定义

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

最大误差 D*

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

答案怎么写

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

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

当前第一名的答案

{
  "points": [
    [
      "0.008695652",
      "0.008695652"
    ],
    [
      "0.026086957",
      "0.408695652"
    ],
    [
      "0.043478261",
      "0.208695652"
    ],
    [
      "0.060869565",
      "0.608695652"
    ],
    [
      "0.07826087",
      "0.108695652"
    ],
    [
      "0.095652174",
      "0.508695652"
    ],
    [
      "0.113043478",
      "0.308695652"
    ],
    [
      "0.130434783",
      "0.708695652"
    ],
    [
      "0.147826087",
      "0.058695652"
    ],
    [
      "0.165217391",
      "0.458695652"
    ],
    [
      "0.182608696",
      "0.258695652"
    ],
    [
      "0.2",
      "0.658695652"
    ],
    [
      "0.217391304",
      "0.158695652"
    ],
    [
      "0.234782609",
      "0.558695652"
    ],
    [
      "0.252173913",
      "0.358695652"
    ],
    [
      "0.269565217",
      "0.758695652"
    ],
    [
      "0.286956522",
      "0.033695652"
    ],
    [
      "0.304347826",
      "0.433695652"
    ],
    [
      "0.32173913",
      "0.233695652"
    ],
    [
      "0.339130435",
      "0.633695652"
    ],
    [
      "0.356521739",
      "0.133695652"
    ],
    [
      "0.373913043",
      "0.533695652"
    ],
    [
      "0.391304348",
      "0.333695652"
    ],
    [
      "0.408695652",
      "0.733695652"
    ],
    [
      "0.426086957",
      "0.083695652"
    ],
    [
      "0.443478261",
      "0.483695652"
    ],
    [
      "0.460869565",
      "0.283695652"
    ],
    [
      "0.47826087",
      "0.683695652"
    ],
    [
      "0.495652174",
      "0.183695652"
    ],
    [
      "0.513043478",
      "0.583695652"
    ],
    [
      "0.530434783",
      "0.383695652"
    ],
    [
      "0.547826087",
      "0.783695652"
    ],
    [
      "0.565217391",
      "0.021195652"
    ],
    [
      "0.582608696",
      "0.421195652"
    ],
    [
      "0.6",
      "0.221195652"
    ],
    [
      "0.617391304",
      "0.621195652"
    ],
    [
      "0.634782609",
      "0.121195652"
    ],
    [
      "0.652173913",
      "0.521195652"
    ],
    [
      "0.669565217",
      "0.321195652"
    ],
    [
      "0.686956522",
      "0.721195652"
    ],
    [
      "0.704347826",
      "0.071195652"
    ],
    [
      "0.72173913",
      "0.471195652"
    ],
    [
      "0.739130435",
      "0.271195652"
    ],
    [
      "0.756521739",
      "0.671195652"
    ],
    [
      "0.773913043",
      "0.171195652"
    ],
    [
      "0.791304348",
      "0.571195652"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看

子题参数

{
  "n": 46
}

当前第一名的答案

{
  "points": [
    [
      "0.008695652",
      "0.008695652"
    ],
    [
      "0.026086957",
      "0.408695652"
    ],
    [
      "0.043478261",
      "0.208695652"
    ],
    [
      "0.060869565",
      "0.608695652"
    ],
    [
      "0.07826087",
      "0.108695652"
    ],
    [
      "0.095652174",
      "0.508695652"
    ],
    [
      "0.113043478",
      "0.308695652"
    ],
    [
      "0.130434783",
      "0.708695652"
    ],
    [
      "0.147826087",
      "0.058695652"
    ],
    [
      "0.165217391",
      "0.458695652"
    ],
    [
      "0.182608696",
      "0.258695652"
    ],
    [
      "0.2",
      "0.658695652"
    ],
    [
      "0.217391304",
      "0.158695652"
    ],
    [
      "0.234782609",
      "0.558695652"
    ],
    [
      "0.252173913",
      "0.358695652"
    ],
    [
      "0.269565217",
      "0.758695652"
    ],
    [
      "0.286956522",
      "0.033695652"
    ],
    [
      "0.304347826",
      "0.433695652"
    ],
    [
      "0.32173913",
      "0.233695652"
    ],
    [
      "0.339130435",
      "0.633695652"
    ],
    [
      "0.356521739",
      "0.133695652"
    ],
    [
      "0.373913043",
      "0.533695652"
    ],
    [
      "0.391304348",
      "0.333695652"
    ],
    [
      "0.408695652",
      "0.733695652"
    ],
    [
      "0.426086957",
      "0.083695652"
    ],
    [
      "0.443478261",
      "0.483695652"
    ],
    [
      "0.460869565",
      "0.283695652"
    ],
    [
      "0.47826087",
      "0.683695652"
    ],
    [
      "0.495652174",
      "0.183695652"
    ],
    [
      "0.513043478",
      "0.583695652"
    ],
    [
      "0.530434783",
      "0.383695652"
    ],
    [
      "0.547826087",
      "0.783695652"
    ],
    [
      "0.565217391",
      "0.021195652"
    ],
    [
      "0.582608696",
      "0.421195652"
    ],
    [
      "0.6",
      "0.221195652"
    ],
    [
      "0.617391304",
      "0.621195652"
    ],
    [
      "0.634782609",
      "0.121195652"
    ],
    [
      "0.652173913",
      "0.521195652"
    ],
    [
      "0.669565217",
      "0.321195652"
    ],
    [
      "0.686956522",
      "0.721195652"
    ],
    [
      "0.704347826",
      "0.071195652"
    ],
    [
      "0.72173913",
      "0.471195652"
    ],
    [
      "0.739130435",
      "0.271195652"
    ],
    [
      "0.756521739",
      "0.671195652"
    ],
    [
      "0.773913043",
      "0.171195652"
    ],
    [
      "0.791304348",
      "0.571195652"
    ]
  ]
}

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