MathLabs

第3問

正整数 nn と kk、および平面上の nn 個の点からなる集合 SS を考える。ただし S のどの3点も一直線上にないものとする。SS の各点 P∈SP\in S に対し、PP から等距離にある SS の点が少なくとも kk 個あると仮定する。k<12+2nk<\frac12+\sqrt{2n} を証明せよ。
ステップ 5/5: 3点一直線上なしに矛盾する
前のステップ次のステップ
ざっくり言うと

矛盾が二重計数を閉じる。等距対称性が多すぎれば禁じられた一直線性が生じる。

Contradiction: P1,P2,P3 are collinear, so k<12+2n\text{Contradiction: }P_1,P_2,P_3\text{ are collinear, so }k<\frac12+\sqrt{2n}
詳しい解説

同じ垂直二等分線上の3つの証人点は一直線上にあり、SS のどの3点も一直線上にないという仮定に反する。ゆえに反対仮定は不可能で、k<12+2nk<\frac12+\sqrt{2n} である。