藤村の三角形問題

藤村の三角形問題（ふじむらのさんかっけいもんだい、英: Kobon triangle problem）は離散幾何学の未解決問題で、藤村幸三郎により初めて述べられた。この問題は、平面上に k 本の直線を引くときに重なり合わずに作ることのできる三角形の最大数 N(k) を求めるものである。ユークリッド平面ではなく射影平面で考え、三角形はその3辺以外の直線と交わらないこと、という条件を課す変種もある^[1]。

上界編集

田村三郎 (数学者)は k(k − 2)/3 を超えない最大の整数が、k 本の直線で作ることのできる重なり合わない三角形の個数の上界を与えることを証明した^[2]。2007年、Johannes Bader と Gilles Clément はより強い上界を発見し、k が 6 を法として 0 または 2 と合同のとき、田村の上界には到達し得ないことを示した^[3]。したがってこれらの場合、三角形の個数は最大でも田村の上界より1だけ小さい数になる。完全な解（作り得る最大個数の三角形を生む直線の引き方）が得られているのは k = 3, 4, 5, 6, 7, 8, 9, 13, 15, 17 のときだけである^[4]。k = 10, 11, 12 に対しては、既知の最善解（直線の引き方）では上界より1だけ小さい個数の三角形が作れている。

G. Clément と J. Bader が証明した^[3]ように、k > 2 に対し

k(k-2)/3

, （k ≡ 3 or 5 (mod 6) のとき）

(k+1)(k-3)/3

, （k ≡ 0 or 2 (mod 6) のとき）

(k^{2}-2k-2)/3

, （k ≡ 1 or 4 (mod 6) のとき）

が上界になる（床関数は、k(k − 2) が1番目の場合3の倍数であり、3番目の場合3で割って2余ることに注意して取り扱うことができる。Clément と Bader が改善を行ったのは2番目の場合のみである）。

k₀（>3）本の直線の場合に完全な解が分かったとすると、それ以外の全ての k_i についても、完全な解となる三角形の個数を求めることができる。ここで

k_{n+1}=2\cdot k_{n}-1

であり、D. Forge と J. L. Ramirez Alfonsin による手続きに従う^[1]^[5]。例えば、k₀ = 5 からは k = 5,9,17,33,65,... のときに作れる最大の三角形の個数が求められる。

k	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	OEIS
N(k) に対する田村の上界	1	2	5	8	11	16	21	26	33	40	47	56	65	74	85	96	107	120	133	A032765
Clément と Bader の上界	1	2	5	7	11	15	21	26	33	39	47	55	65	74	85	95	107	119	133	-
既知の最善解	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85	93	104	115	130	A006066