藤村の三角形問題のソースを表示

[[Image:Kobon triangles.gif|right|frame|3, 4, 5 本の直線で作られる藤村の三角形。]]

'''藤村の三角形問題'''（ふじむらのさんかっけいもんだい、{{Lang-en-short|Kobon triangle problem}}）は[[離散幾何学]]の未解決問題で、[[藤村幸三郎]]により初めて述べられた。この問題は、平面上に ''k'' 本の直線を引くときに重なり合わずに作ることのできる三角形の最大数 ''N''(''k'') を求めるものである。[[ユークリッド空間|ユークリッド平面]]ではなく[[射影平面]]で考え、三角形はその3辺以外の直線と交わらないこと、という条件を課す変種もある<ref name="forge">{{citation|title=Straight line arrangements in the real projective plane|first1=D.|last1=Forge|first2=J. L.|last2=Ramírez Alfonsín|journal=[[Discrete and Computational Geometry]]|volume=20|issue=2|pages=155–161|year=1998|doi=10.1007/PL00009373}}.</ref>。

== 上界 ==
[[田村三郎 (数学者)]]は ''k''(''k''&nbsp;&minus;&nbsp;2)/3 を超えない最大の整数が、''k'' 本の直線で作ることのできる重なり合わない三角形の個数の上界を与えることを証明した<ref>{{MathWorld|urlname=KobonTriangle|title=Kobon Triangle}}</ref>。2007年、Johannes Bader と Gilles Clément はより強い上界を発見し、''k'' が 6 を法として 0 または 2 と[[整数の合同|合同]]のとき、田村の上界には到達し得ないことを示した<ref name="bacl">[http://www.tik.ee.ethz.ch/sop/publicationListFiles/cb2007a.pdf G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007.]</ref>。したがってこれらの場合、三角形の個数は最大でも田村の上界より1だけ小さい数になる。完全な解（作り得る最大個数の三角形を生む直線の引き方）が得られているのは ''k'' = 3, 4, 5, 6, 7, 8, 9, 13, 15, 17 のときだけである<ref>[http://www.mathpuzzle.com/MAA/45-Kobon/mathgames_02_08_06.html Ed Pegg Jr. on Math Games]</ref>。''k'' = 10, 11, 12 に対しては、既知の最善解（直線の引き方）では上界より1だけ小さい個数の三角形が作れている。

G. Clément と J. Bader が証明した<ref name="bacl"/>ように、''k'' > 2 に対し
: <math>k(k-2)/3</math>, （''k'' ≡ 3 or 5 (mod 6) のとき）
: <math>(k+1)(k-3)/3</math>, （''k'' ≡ 0 or 2 (mod 6) のとき）
: <math>(k^2-2k-2)/3</math>, （''k'' ≡ 1 or 4 (mod 6) のとき）

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

''k''<sub>0</sub>（&gt;3）本の直線の場合に完全な解が分かったとすると、それ以外の全ての ''k<sub>i</sub>'' についても、完全な解となる三角形の個数を求めることができる。ここで
:<math>k_{n+1} = 2\cdot k_{n} - 1</math>
であり、D. Forge と J. L. Ramirez Alfonsin による手続きに従う<ref name="forge" /><ref>[http://www.johannesbader.ch/#kobon "Matlab code illustrating the procedure of D. Forge and J. L. Ramirez Alfonsin", Retrieved on 9 May 2012.]</ref>。例えば、''k''<sub>0</sub> = 5 からは ''k'' = 5,9,17,33,65,... のときに作れる最大の三角形の個数が求められる。
{{-}}
{| class="wikitable"
|-
| '''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 || {{OEIS2C|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 || {{OEIS2C|A006066}}
|}

== 例 ==
<gallery>
Image:KobonTriangle_3.svg|3本の直線が1個の三角形を作る。
Image:KobonTriangle_4.svg|4本
Image:KobonTriangle_5.svg|5本
Image:KobonTriangle_6.svg|6本
Image:KobonTriangle_7.svg|7本
</gallery>

==関連項目==
* {{仮リンク|ロバーツの三角形問題|ru|Теорема Робертса о треугольниках}}

==脚注==
{{Reflist}}

==外部リンク==
*Johannes Bader, [http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php "Kobon Triangles"]

{{DEFAULTSORT:ふしむらのさんかつけいもんたい}}
[[Category:数学のオープンプロブレム]]
[[Category:離散幾何学]]
[[Category:三角形]]
[[Category:数学パズル]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]