MathLabs

第1問

平面上の点からなる有限集合 SS が、SS 内の任意の異なる2点 AA, BB に対して AC=BCAC=BC を満たす点 CC が SS 内に存在するとき、バランスが取れている と呼ぶことにする。また、SS 内の任意の異なる3点 AA, BB, CC に対して PA=PB=PCPA=PB=PC を満たす点 PP が SS 内に存在しないとき、SS は 中心を持たない と呼ぶことにする。 (a) すべての整数 n≥3n\ge3 に対して、nn 個の点からなるバランスが取れた集合が存在することを示せ。 (b) nn 個の点からなるバランスが取れていて中心を持たない集合が存在するような整数 n≥3n\ge3 をすべて求めよ。
ステップ 5/5: 証人を持つ二つの対は重なり合わなければならない
前のステップ次のステップ
ざっくり言うと

半数の点それぞれが、より小さな集合の中で新たな対を始めようとすれば、必ずどこかで二つの対が衝突してしまう。

{A,B},{A,C} witnessed by P⇒PA=PB=PC\{A,B\},\{A,C\}\ \text{witnessed by }P \Rightarrow PA=PB=PC
詳しい解説

PP が証人となる n2\frac n2 個の対のうち、PP 自身を含むものはない（それでは対の二点が一致してしまう）。よってこれら n2\frac n2 個の対はすべて、VV の残り n−1n-1 個の点の中にある。もしそれらが互いに素であれば 2⋅n2=n2\cdot\frac n2=n 個の相異なる点が必要になるが、利用できるのは n−1n-1 個しかない。したがって二つの対がある点を共有する、例えば {A,B}\{A,B\} と {A,C}\{A,C\}（B≠CB\ne C）とする。このとき PA=PBPA=PB かつ PA=PCPA=PC なので、三つの相異なる点 A,B,CA,B,C に対して PA=PB=PCPA=PB=PC となり、VV が中心を持たないことに矛盾する。よって偶数の大きさを持つバランスが取れていて中心を持たない集合は存在せず、(b) の答えはちょうど奇数の整数 n≥3n\ge3 である。