藤村の三角形問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
3, 4, 5 本の直線で作られる藤村の三角形。

藤村の三角形問題(ふじむらのさんかっけいもんだい、: 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 ≡ 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 による手続きに従う[1][5]。例えば、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 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

[編集]

関連項目[編集]

脚注[編集]

  1. ^ a b Forge, D.; Ramírez Alfonsín, J. L. (1998), “Straight line arrangements in the real projective plane”, Discrete and Computational Geometry 20 (2): 155–161, doi:10.1007/PL00009373 .
  2. ^ Weisstein, Eric W. "Kobon Triangle". MathWorld(英語).
  3. ^ a b G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007.
  4. ^ Ed Pegg Jr. on Math Games
  5. ^ "Matlab code illustrating the procedure of D. Forge and J. L. Ramirez Alfonsin", Retrieved on 9 May 2012.