MathLabs

第6問

平面上に、3点が一直線上にない 100100 個の点がある。これらを頂点とするすべての三角形を考える。そのうち鋭角三角形は 70%70\% 以下であることを証明せよ。
ステップ 3/4: 100点集合の5点部分集合を数える
A100(972)≤7(1005)A_{100}\binom{97}{2}\le7\binom{100}{5}
詳しい解説

A100A_{100} を 100100 点中の鋭角三角形数とする。各5点部分集合には鋭角三角形が高々 77 個なので、出現回数は高々 7(1005)7\binom{100}{5}。固定した鋭角三角形はちょうど (972)\binom{97}{2} 個の5点集合に含まれる。従って A100(972)≤7(1005)A_{100}\binom{97}{2}\le7\binom{100}{5}。