藤村の三角形問題

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

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

G. Clément と J. Bader が証明したように、k > 2 に対し
 , （k ≡ 3 or 5 (mod 6) のとき）
 , （k ≡ 0 or 2 (mod 6) のとき）
 , （k ≡ 1 or 4 (mod 6) のとき）

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

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

であり、D. Forge と J. L. Ramirez Alfonsin による手続きに従う"Matlab code illustrating the procedure of D. Forge and J. L. Ramirez Alfonsin", Retrieved on 9 May 2012.。例えば、k0 = 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 120133   Clément と Bader の上界   1 2 5 7 11 15 21 26 33 39 47 55 65 74 85 95 107 119133  - 既知の最善解  1 2 5 7 11 15 21 25 32 38 47 53 65 72 85  93 104  115  130  

 例 

関連項目


脚注

外部リンク
Johannes Bader, "Kobon Triangles"

Category:数学のオープンプロブレム
Category:離散幾何学
Category:三角形
Category:数学パズル
Category:数学のエポニム
Category:数学に関する記事