第3問

9個の空間内の点を考え、4点が同一平面上にないとする。各点対を赤、青、または無色の辺で結ぶ。ちょうど

n

本の辺を彩色したとき必ず3辺が同色の三角形が存在するような最小の

n

を求めよ。

ステップ 3/4: 1つの正方形から2頂点を取る三角形を調べる

ざっくり言うと

1つの正方形から2頂点を取る三角形を調べる

i\equiv j\pmod2\Longrightarrow \chi(R_iR_j)=0

詳しい解説

$R_iR_jB_k$ を考える。 $i\equiv j\pmod2$ なら辺 $R_iR_j$ は無色の対角線、そうでなければ $R_iB_k$ と $R_jB_k$ は反対色である。 $B_iB_jR_k$ も同様で、単色三角形はない。