no-three-in-line 問題
概要
no-three-in-line 問題（no-three-in-line problem）とは、$n\times n$ の格子点の中から、どの 3 点も一直線上にないように最大で何点選べるかを問う問題である。各行には 2 点までしか置けないので、選べる点は多くても $2n$ 点である。小さい $n$ では $2n$ 点の配置が見つかるが、大きい $n$ での最大値は分かっていない。$p$ が素数のとき、$x=0,1,\dots,p-1$ について $x^2$ を $p$ で割った余りを $y$ とする $p$ 個の点 $(x,y)$ は、どの 3 点も一直線上にない。3 点の行列式は $p$ を法として $(x_2-x_1)(x_3-x_1)(x_3-x_2)$ と合同で、$p$ の倍数にならないからである。$p$ を素数でない数にすると、この構成は成り立たないことがある。
高校での出発点：一直線に 3 つ並べずに格子点を選ぶ
$x$ 座標と $y$ 座標がともに整数である点を 格子点 という。$1\le x\le n$、$1\le y\le n$ の範囲にある $n^2$ 個の格子点を $n\times n$ の格子点 とよぶ。この中から、どの 3 点も一直線上に並ばないように、できるだけ多くの点を選びたい。何点まで選べるだろうか。
- 6 点は選べる。たとえば
$$ (1,1),\ (2,1),\ (1,2),\ (3,2),\ (2,3),\ (3,3) $$
の 6 点を選ぶ（図 1）。横の行 $y=1,2,3$ にはどれも 2 点ずつ、縦の列 $x=1,2,3$ にも 2 点ずつある。斜めの直線 $y=x$ の上には $(1,1)$ と $(3,3)$ の 2 点だけで、$(2,2)$ は選んでいない。直線 $y=x+1$ の上には $(1,2)$、$(2,3)$ の 2 点だけ、$y=x-1$ の上には $(2,1)$、$(3,2)$ の 2 点だけである。6 点から 3 点を選ぶ $\binom63=20$ 通りをすべて調べると、一直線上に並ぶ組はない（lem-ntl-det の式で確かめられる）。 - 7 点は選べない。$3\times3$ の格子点は横の 3 つの行 $y=1,2,3$ に分かれる。7 点を 3 つの行に入れると、どれかの行に 3 点以上が入る（2 点ずつなら合わせて 6 点までしか入らない）。同じ行の 3 点は直線 $y=k$ の上にあるので、一直線上に並んでしまう。
3×3 の格子点から、どの 3 点も一直線上にないように選んだ 6 点（青）
4×4 の格子点から、どの 3 点も一直線上にないように選んだ 8 点（青）
ex-ntl-start の (2) の議論は、どの $n$ でも使える。一方、(1) のように上限いっぱいの点を選ぶ方法は、$n$ が大きくなると簡単には見つからない。この記事で答える問いは次の 3 つである。
- $n\times n$ の格子点から選べる点の数には、どんな上限があるか。→ thm-ntl-upper
- 多くの点を、規則的に選ぶ方法はあるか。→ thm-ntl-parabola
- その方法は、どの条件が崩れるとうまくいかないか。→ 節「例と反例」
高校の計算 この記事の言葉 大学の言葉 行ごとに点を数える 上限 $2n$ 鳩の巣原理 3 点の三角形の面積が $0$ 行列式による一直線の判定 $3$ 点の行列式 $x^2$ を $p$ で割った余り 放物線を折りたたんだ配置 有限体の上の放物線 $(x_2-x_1)(x_3-x_1)(x_3-x_2)$ は $p$ の倍数でない 3 点が一直線上にない 2 次式の根は多くても 2 個
言葉の準備：3 点が一直線上にあることの判定
平面の格子点の集まりで、どの異なる 3 点も一直線上にないものを、no-three-in-line の配置 とよぶ。$n\times n$ の格子点の中の no-three-in-line の配置が最大で何点からなるかを問う問題を no-three-in-line 問題 という（Wei26）。
一直線上にあるかどうかは、座標の計算で判定できる。3 点を頂点とする三角形の面積が $0$ になることと同じで、靴ひも公式 の面積の式の 2 倍にあたる量を使う。
異なる 3 点 $P_1(x_1,y_1)$、$P_2(x_2,y_2)$、$P_3(x_3,y_3)$ について
$$
D=(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)
$$
とおく。3 点が一直線上にあるための必要十分条件は $D=0$ である。
$\overrightarrow{P_1P_2}=(a,b)=(x_2-x_1,\ y_2-y_1)$、$\overrightarrow{P_1P_3}=(c,d)=(x_3-x_1,\ y_3-y_1)$ とおくと $D=ad-bc$ である。$P_1\ne P_2$ なので $(a,b)\ne(0,0)$ である。
段 1（一直線上なら $D=0$）。$P_3$ が直線 $P_1P_2$ の上にあれば、実数 $t$ で $(c,d)=t(a,b)$ と書ける。このとき $D=a\cdot tb-b\cdot ta=0$ である。
段 2（$D=0$ なら一直線上）。$a\ne0$ のとき、$ad=bc$ から $d=\dfrac{bc}a$ で、$t=\dfrac ca$ とおくと $(c,d)=\left(ta,\ tb\right)=t(a,b)$ である。$a=0$ のときは $b\ne0$ で、$ad-bc=-bc=0$ から $c=0$ となり、$(c,d)=\dfrac db(0,b)=\dfrac db(a,b)$ である。どちらの場合も $\overrightarrow{P_1P_3}$ は $\overrightarrow{P_1P_2}$ の実数倍なので、$P_3$ は直線 $P_1P_2$ の上にある。$\square$
$\lvert D\rvert$ は、3 点を頂点とする三角形の面積の 2 倍である（靴ひも公式）。$D$ は次のような行列式としても書ける（1次変換と行列式：面積の拡大率）。
$$
D=\begin{vmatrix}x_2-x_1&x_3-x_1\\y_2-y_1&y_3-y_1\end{vmatrix}
$$
- $(1,1)$、$(2,2)$、$(4,4)$：$D=(2-1)(4-1)-(4-1)(2-1)=3-3=0$ で、3 点は直線 $y=x$ の上にある。
- $(0,0)$、$(1,1)$、$(2,4)$：$D=(1-0)(4-0)-(2-0)(1-0)=4-2=2\ne0$ で、3 点は一直線上にない。三角形の面積は $1$ である。
- $(1,1)$、$(3,2)$、$(5,3)$：$D=(3-1)(3-1)-(5-1)(2-1)=4-4=0$ で、3 点は直線 $y=\dfrac{x+1}2$ の上にある。行でも列でも斜め $45^\circ$ でもない直線にも、格子点は 3 つ並びうる。
主定理 1：選べる点は $2n$ 個まで
$n\times n$ の格子点の中の no-three-in-line の配置は、多くても $2n$ 点からなる。
$n\times n$ の格子点は、横の $n$ 本の行 $y=1,2,\dots,n$ に分かれる。配置が $2n+1$ 点以上からなると仮定する。各行に 2 点以下しかなければ、合わせて $2n$ 点以下で、仮定に反する。したがって、ある行 $y=k$ に 3 点以上がある（鳩の巣原理）。その 3 点はどれも直線 $y=k$ の上にあり、一直線上に並ぶ。これは no-three-in-line の配置であることに反する。よって配置は $2n$ 点以下である。$\square$
上限 $2n$ に届く配置を、小さい $n$ で見る。
- $n=2$：$2\times2$ の格子点の 4 点すべて。4 点から 3 点を選ぶと、どの組も直角三角形の頂点になり、一直線上にない。
- $n=3$：ex-ntl-start (1) の 6 点（図 1）。
- $n=4$：次の 8 点（図 2）。
$$ (1,1),\ (2,1),\ (3,2),\ (4,2),\ (1,3),\ (2,3),\ (3,4),\ (4,4) $$
各行・各列に 2 点ずつある。この配置は、中心 $\left(\dfrac52,\dfrac52\right)$ のまわりに $180^\circ$ 回しても変わらない（$(x,y)\mapsto(5-x,5-y)$ で $(1,1)\leftrightarrow(4,4)$、$(2,1)\leftrightarrow(3,4)$、$(3,2)\leftrightarrow(2,3)$、$(4,2)\leftrightarrow(1,3)$）。8 点から 3 点を選ぶ $\binom83=56$ 通りすべてで $D\ne0$ であることを、コンピュータで確かめた。
コンピュータで全部を調べると、$2n$ 点の配置は、$n=3$ では 2 通り、$n=4$ では 11 通り、$n=5$ では 32 通りある（向きや裏返しで重なるものも別に数える）。Wei26 によれば、$2n$ 点の配置は $2\le n\le76$ の $n$（$n=75$ を除く）で見つかっている。
主定理 2：放物線を素数で割った余り
$2n$ 点の配置を、どの $n$ にも通用する式で作る方法は知られておらず、$n$ ごとに探して見つけている。一方、点の数を $n$ 程度に減らしてよければ、どの素数 $p$ についても、式 1 本で配置が作れる。放物線 $y=x^2$ の上の点を、$y$ 座標を $p$ で割った余りに置きかえて、$p\times p$ の範囲に折りたたむのである。
$x=0,1,\dots,6$ について、$x^2$ を $7$ で割った余りを $y$ とする。
| $x$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|---|
| $x^2$ | $0$ | $1$ | $4$ | $9$ | $16$ | $25$ | $36$ |
| $y$（$7$ で割った余り） | $0$ | $1$ | $4$ | $2$ | $2$ | $4$ | $1$ |
7 点 $(0,0)$、$(1,1)$、$(2,4)$、$(3,2)$、$(4,2)$、$(5,4)$、$(6,1)$ ができる（図 3）。たとえば $(1,1)$、$(3,2)$、$(5,4)$ では
$$
D=(3-1)(4-1)-(5-1)(2-1)=6-4=2
$$
で、一直線上にない。$(2,4)$、$(3,2)$、$(4,2)$ では $D=(3-2)(2-4)-(4-2)(2-4)=-2+4=2$ である。
どちらの組でも $D$ を $7$ で割った余りは、次の定理の証明に出てくる差の積 $(x_2-x_1)(x_3-x_1)(x_3-x_2)$ を $7$ で割った余りと同じである（$2\cdot4\cdot2=16$ と $1\cdot2\cdot1=2$ は、どちらも $7$ で割って $2$ 余る）。これは偶然ではない。$D$ の値そのものは組によって変わり、たとえば $(0,0)$、$(1,1)$、$(3,2)$ では $D=-1$、差の積は $6$ で、どちらも $7$ で割って $6$ 余る。
$p$ を素数とする。$x=0,1,\dots,p-1$ について、$x^2$ を $p$ で割った余りを $y_x$ とする。$p$ 個の点
$$
(x,\ y_x)\qquad(x=0,1,\dots,p-1)
$$
は、どの 3 点も一直線上にない。これらの点は $0\le x\le p-1$、$0\le y\le p-1$ の範囲の格子点である。
方針：3 点が一直線上にあるとして、lem-ntl-det の $D=0$ を $p$ で割った余りで見て、矛盾を導く。
段 1（設定）。$p\le2$ なら点は 2 個以下なので、$p\ge3$ としてよい。異なる 3 点 $(x_1,y_1)$、$(x_2,y_2)$、$(x_3,y_3)$ をとる。点は $x$ ごとに 1 つなので $x_1,x_2,x_3$ は異なり、どれも $0$ 以上 $p-1$ 以下である。$y_i$ は $x_i^2$ を $p$ で割った余りなので $y_i\equiv x_i^2\pmod p$ である（合同式の計算規則）。
段 2（$D$ の余り）。$D=(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)$ の $y_i$ を $x_i^2$ に置きかえても、$p$ を法として合同である（合同式は、和・差・積について置きかえてよい）。
$$
\begin{aligned}
D&\equiv(x_2-x_1)(x_3^2-x_1^2)-(x_3-x_1)(x_2^2-x_1^2)\\
&=(x_2-x_1)(x_3-x_1)(x_3+x_1)-(x_3-x_1)(x_2-x_1)(x_2+x_1)\\
&=(x_2-x_1)(x_3-x_1)\bigl\{(x_3+x_1)-(x_2+x_1)\bigr\}\\
&=(x_2-x_1)(x_3-x_1)(x_3-x_2)\pmod p
\end{aligned}
$$
2 行目は $x_3^2-x_1^2=(x_3-x_1)(x_3+x_1)$ などの因数分解、3 行目は共通因数 $(x_2-x_1)(x_3-x_1)$ でくくった。
段 3（$p$ の倍数でない）。$x_1,x_2,x_3$ は $0$ 以上 $p-1$ 以下の異なる整数なので、3 つの差 $x_2-x_1$、$x_3-x_1$、$x_3-x_2$ は、どれも $0$ でなく、絶対値が $p-1$ 以下である。よってどれも $p$ の倍数でない。$p$ は素数なので、$p$ の倍数でない整数の積は $p$ の倍数でない（素数 $p$ が積 $ab$ を割り切れば $a$ か $b$ を割り切る。素因数分解の一意性）。したがって $(x_2-x_1)(x_3-x_1)(x_3-x_2)$ は $p$ の倍数でない。
段 4（結論）。段 2 と段 3 から、$D$ は $p$ の倍数でない。とくに $D\ne0$ である（$0$ は $p$ の倍数）。lem-ntl-det により、3 点は一直線上にない。$\square$
p=7 の配置の 7 点（赤）。薄い曲線は放物線 y=x² を 7 ずつ下にずらしたもので、赤い点はその上にある
p=11 の配置の 11 点（赤）も、どの 3 点も一直線上にない
図 3 の薄い曲線は、放物線 $y=x^2$ を $y$ 方向に $7$ ずつ下げた曲線 $y=x^2-7k$ である。点 $(x,y_x)$ は、$x^2-7k$ が $0$ 以上 $6$ 以下になる $k$ の曲線の上にある。放物線を $p\times p$ の正方形に折りたたんだ形である。
- $p=5$：$x=0,\dots,4$ で $x^2=0,1,4,9,16$ の余りは $0,1,4,4,1$ で、5 点 $(0,0)$、$(1,1)$、$(2,4)$、$(3,4)$、$(4,1)$ である。$5\times5$ の格子点から 5 点で、上限 $2\cdot5=10$ の半分である。
- $p=11$：11 点 $(0,0)$、$(1,1)$、$(2,4)$、$(3,9)$、$(4,5)$、$(5,3)$、$(6,3)$、$(7,5)$、$(8,9)$、$(9,4)$、$(10,1)$（図 4）。
- 素数でない $n$ でも、$n$ 以下の素数 $p$ を 1 つとれば、$n\times n$ の格子点の中に $p$ 点の no-three-in-line の配置がある（$p\times p$ の範囲を $(1,1)$ だけ平行移動して入れる。平行移動で 3 点が一直線上かどうかは変わらない）。たとえば $n=10$ なら $p=7$ で 7 点である。
コンピュータで $p=3,5,7,11,13,17,19,23$ のすべての 3 点の組を調べ、thm-ntl-parabola のとおり一直線上に並ぶ組がないことを確かめた。
thm-ntl-parabola の配置は $p$ 点で、thm-ntl-upper の上限 $2p$ の半分である。上限との差を詰めることが、この問題の難しいところである。
例と反例
thm-ntl-parabola の仮定を変えると何が崩れるかを並べる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $p$ が素数 | $x^2$ を $6$ で割った余り | どの 3 点も一直線上にない |
| $p$ が素数 | $x^2$ を $9$ で割った余り | どの 3 点も一直線上にない |
| $x$ の 2 次式 | $x^3$ を $7$ で割った余り | どの 3 点も一直線上にない |
| 斜めの直線も調べる（行だけを見ない） | 各行に 2 点ずつの 6 点 $(1,1),(2,1),(2,2),(3,2),(3,3),(1,3)$ | どの 3 点も一直線上にない |
$x=0,\dots,5$ で $x^2=0,1,4,9,16,25$ を $6$ で割った余りは $0,1,4,3,4,1$ で、6 点 $(0,0)$、$(1,1)$、$(2,4)$、$(3,3)$、$(4,4)$、$(5,1)$ ができる（図 5）。このうち $(0,0)$、$(1,1)$、$(3,3)$、$(4,4)$ の 4 点が直線 $y=x$ の上にある。
prf-ntl-parabola の段 3 で見ると、$(0,0)$、$(1,1)$、$(3,3)$ では差の積が $(1-0)(3-0)(3-1)=6$ で、$6$ の倍数になっている。$2$ と $3$ はどちらも $6$ の倍数でないが、積 $6$ は $6$ の倍数である。「倍数でない数の積は倍数でない」は、$p$ が素数のときにしか使えない。
$x=0,3,6$ では $x^2=0,9,36$ がどれも $9$ の倍数で、余りは $0$ である。3 点 $(0,0)$、$(3,0)$、$(6,0)$ は $x$ 軸の上に並ぶ。差の積は $3\cdot6\cdot3=54=9\cdot6$ で、$9$ の倍数である。
x² を 6 で割った余りの 6 点では、緑の破線 y=x の上に 4 点が並ぶ
x³ を 7 で割った余りの 7 点では、緑の破線 y=1 と y=6 の上に 3 点ずつ並ぶ
$x=0,\dots,6$ で $x^3=0,1,8,27,64,125,216$ を $7$ で割った余りは $0,1,1,6,1,6,6$ で、$(1,1)$、$(2,1)$、$(4,1)$ の 3 点が直線 $y=1$ の上に、$(3,6)$、$(5,6)$、$(6,6)$ の 3 点が直線 $y=6$ の上に並ぶ（図 6）。
prf-ntl-parabola の段 2 で $x^2$ の代わりに $x^3$ を使うと、$x_3^3-x_1^3=(x_3-x_1)(x_3^2+x_3x_1+x_1^2)$ から
$$
D\equiv(x_2-x_1)(x_3-x_1)(x_3-x_2)(x_1+x_2+x_3)\pmod p
$$
となり、余分な因数 $x_1+x_2+x_3$ が現れる。$(1,1)$、$(2,1)$、$(4,1)$ では $1+2+4=7$ で、$7$ の倍数である。2 次式では、この余分な因数が現れない。
6 点 $(1,1)$、$(2,1)$、$(2,2)$、$(3,2)$、$(3,3)$、$(1,3)$ は、どの行にも 2 点ずつである。しかし $(1,1)$、$(2,2)$、$(3,3)$ は直線 $y=x$ の上に並ぶ。thm-ntl-upper の証明で使った「行に 3 点がない」は、no-three-in-line の配置であるための必要条件だが、十分条件ではない。上限 $2n$ は簡単に示せても、それに届く配置を作るのが難しいのはこのためである。
大学数学で見る：有限体の上の放物線
thm-ntl-parabola の証明は、「放物線と直線は多くても 2 点でしか交わらない」という事実を、$p$ で割った余りの世界に持ちこんだものである。
$p$ で割った余り $0,1,\dots,p-1$ の集まりを $\mathbb{F}_p$ と書く。$\mathbb{F}_p$ では足し算・引き算・掛け算ができ、$p$ が素数なら $0$ 以外の数での割り算もできる。このような数の集まりを 有限体 という（有限体）。余りの組 $(x,y)$ を点とみると、$p\times p$ の格子点が「$\mathbb{F}_p$ の平面」の点になる。
放物線と直線の交わりで見た別証明を開く
実数の平面で 3 点 $(x_i,y_i)$ が直線 $ax+by=c$（$a,b,c$ は整数で、$a,b$ の少なくとも一方は $0$ でない）の上にあれば、余りの世界でも $ax_i+by_i\equiv c\pmod p$ が成り立つ。3 点が格子点で一直線上なら、そのような整数の $a,b,c$ を、$a,b,c$ の最大公約数が $1$ になるようにとれる。すると $a,b$ の両方が $p$ の倍数になることはない（そうなら $c=ax_1+by_1$ も $p$ の倍数で、最大公約数が $p$ の倍数になる）。
- $b$ が $p$ の倍数でないとき：$\mathbb{F}_p$ で $b$ で割れるので、直線は $y\equiv mx+k$ の形になる。放物線の点では $x^2\equiv mx+k$、つまり $x^2-mx-k\equiv0\pmod p$ である。$p$ が素数なら、この 2 次の合同式を満たす $x$（$0\le x\le p-1$）は多くても 2 個である（解 $\alpha$ が 1 つあれば、$\alpha^2\equiv m\alpha+k$ を使って $x^2-mx-k\equiv(x-\alpha)\bigl(x-(m-\alpha)\bigr)$ と因数分解できる。積が $p$ の倍数なら一方の因数が $p$ の倍数なので、解は $\alpha$ と $m-\alpha$ の余りに限られる）。3 点の $x$ 座標は異なるので矛盾する。
- $b$ が $p$ の倍数のとき：$a$ は $p$ の倍数でなく、$ax_i\equiv c$ から $x_i$ は $\mathbb{F}_p$ でただ 1 つに決まる。3 点の $x$ 座標は $0$ 以上 $p-1$ 以下で異なるので、これも矛盾する。
いずれにしても 3 点は一直線上にない。ここで使ったのは「$\mathbb{F}_p$ で 2 次式の根は多くても 2 個」という性質で、ex-ntl-cx-cube の 3 次式では根が 3 個ありうる（$x^3\equiv1\pmod7$ の解 $x=1,2,4$）。
大きな $n$ で何点まで選べるかは、Wei26 によれば分かっていない。頁には、大きな $n$ では $2n$ 点は選べず、おおよそ $\dfrac{\pi}{\sqrt3}n\approx1.814n$ 点までしか選べないだろうという予想が載っている（Guy と Kelly が 1968 年に予想した定数 $\left(\dfrac{2\pi^2}3\right)^{1/3}\approx1.87$ を改めた値）。これは予想で、証明されていない。
さらに先へ
- どの 3 点も一直線上にない点の集まりは、一般の位置にあるという。どの $k$ についても、一般の位置にある点が十分多ければ、そのうち $k$ 個が凸 $k$ 角形の頂点になる（Erdős–Szekeresの定理（凸多角形））。
- 逆に、有限個の点がすべて一直線上にあるのでなければ、ちょうど 2 点だけを通る直線がある（Sylvester–Gallaiの定理）。
- 格子点の円の問題（Gaussの円問題、格子点をちょうど n 個通る円）では、円の上に格子点がいくつ乗るかを考えた。円と直線は多くても 2 点でしか交わらないので、1 つの円の上の格子点は、どの 3 点も一直線上にない。
- 3 点の三角形の面積と行列式は 靴ひも公式 と 1次変換と行列式：面積の拡大率 で扱う。
関連項目
- 前提: 鳩の巣原理, 合同式の計算規則, 靴ひも公式, 素因数分解の一意性
- 前に読む: 格子点をちょうど n 個通る円, 合同式の計算規則, 鳩の巣原理
- 次に読む: Erdős–Szekeresの定理（凸多角形）
- 関連（高校数学）: 靴ひも公式, 1次変換と行列式：面積の拡大率, Gaussの円問題, 格子点の正多角形
- 発展: 有限体, 平方剰余, Sylvester–Gallaiの定理
- 比較: Erdős–Szekeresの定理（凸多角形）
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
