MathLabs

第3問

9個の空間内の点を考え、4点が同一平面上にないとする。各点対を赤、青、または無色の辺で結ぶ。ちょうど nn 本の辺を彩色したとき必ず3辺が同色の三角形が存在するような最小の nn を求めよ。
ステップ 4/4: 33本の彩色辺が単色三角形を強制することを示す
前のステップ次のステップ
ざっくり言うと

33本の彩色辺が単色三角形を強制することを示す

n≥33n\ge33
詳しい解説

ちょうど 3333 本を彩色すると無色辺は 33 本だけである。各無色辺から一方の端点を除けば、少なくとも6点が残り、それらの間の辺はすべて彩色済みである。その一つを XX とすると、5本の接辺の少なくとも3本が同色、例えば A,B,CA,B,C への赤辺である。AB,BC,CAAB,BC,CA のいずれかが赤なら XX を含む赤三角形ができ、そうでなければ3辺とも青なので ABCABC は青三角形。従って最小の nn は 3333。