MathLabs

未解決問題、組合せ論と離散数学, 幾何学、1917年に提起

三点共線回避問題（No-three-in-line問題）

未解決

各整数 n≥2n \ge 2 に対し、n×nn \times n の格子点集合 {1,2,…,n}2\{1, 2, \dots, n\}^2 から、どの3点も任意の傾きの同一直線上に並ばないように選べる点の最大個数 f(n)f(n) を決定せよ。特に、すべての nn で f(n)=2nf(n) = 2n が成り立つか、あるいは lim⁡n→∞f(n)/n<2\lim_{n \to \infty} f(n)/n < 2 となるかを決定せよ。

研究の最前線 2026年時点

2026年現在、漸近比 lim⁡n→∞f(n)/n\lim_{n \to \infty} f(n)/n は未解明であり、1975年のホール・ジャクソン・サドベリー・ワイルドによる代数的下界 32=1.5\frac{3}{2} = 1.5 と鳩の巣原理による自明な上界 22 の間に挟まれたままである。計算機探索（フラメンカンプ、プレルベルク、ヒューレら）により n≤74n \le 74 のすべての nn に対して三点共線を含まない 2n2n 点の配置が見つかっているが、nn が大きくなるにつれて対称な 2n2n 点解の個数は減少しており、ガイ・ケリーのヒューリスティック予測 f(n)∼π3n≈1.8138nf(n) \sim \frac{\pi}{\sqrt{3}} n \approx 1.8138n を経験的に支持している。

既知の最良の結果

  • すべての n≥2n \ge 2 に対して (32−o(1))n≤f(n)≤2n(\frac{3}{2} - o(1))n \le f(n) \le 2n が成り立つ（ホール、ジャクソン、サドベリー、ワイルド、1975年）。
  • 計算機で構成された明示的な配置により、すべての 2≤n≤742 \le n \le 74 に対して厳密な等式 f(n)=2nf(n) = 2n が成り立つ。

使われた手法と限界

手法達成したこと限界
有限体 Fp\mathbb{F}_p 上の代数曲線（エルデシュ、ホール・ジャクソン・サドベリー・ワイルド）Fp\mathbb{F}_p 上のベズーの定理（直線は y≡x2(modp)y \equiv x^2 \pmod p や xy≡k(modp)xy \equiv k \pmod p のような既約二次曲線と pp を法として高々 22 点、したがって Z2\mathbb{Z}^2 上でも高々 22 点でしか交わらないこと）を用いて (3/2−o(1))n(3/2 - o(1))n 個の点を構成した。Fp\mathbb{F}_p 上の次数 d≥3d \ge 3 の曲線は直線と 33 点以上で交わり得る一方、複数のシフトした二次曲線を並べると密度が 3n/23n/2 を超えた時点で異なるタイル間に共線三点が生じてしまう。

未解決の問い

  • f(n)<2nf(n) < 2n となる整数 n≥2n \ge 2 が存在するか。
  • 極限 lim⁡n→∞f(n)/n\lim_{n \to \infty} f(n)/n は存在するか。また、それは 22 より真に小さいか（例えば π/3≈1.8138\pi/\sqrt{3} \approx 1.8138 に等しいか）。

参考文献

  1. Klaus Friedrich Roth (with an appendix by Paul Erdős) (1951). On a problem of formal logic · DOI:10.1112/jlms/s1-26.3.198
  2. Richard K. Guy, Patrick A. Kelly (1968). The no-three-in-line problem · DOI:10.4153/CMB-1968-062-3
  3. R. R. Hall, T. H. Jackson, A. Sudbery, K. Wild (1975). Some advances in the no-three-in-line problem · DOI:10.1016/0097-3165(75)90043-6