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 をすべて求めよ。
ステップ 4/5: nn が偶数の場合は不可能：鳩の巣原理による議論
前のステップ次のステップ
ざっくり言うと

あまりに多くの組が、あまりに少ない「証人」候補点を共有せざるを得ず、その結果どこかの点が他の3点から等距離になってしまう。

(n2)=n(n−1)2 pairs,⌈n(n−1)/2n⌉=n2 for even n\binom n2 = \tfrac{n(n-1)}2 \text{ pairs},\quad \Big\lceil \tfrac{n(n-1)/2}{n}\Big\rceil=\tfrac n2 \text{ for even } n
詳しい解説

VV がバランスが取れていて中心を持たず、∣V∣=n|V|=n が偶数であるとする。(n2)=n(n−1)2\binom n2=\frac{n(n-1)}2 個の非順序対 {A,B}⊂V\{A,B\}\subset V のそれぞれについて、C(A,B)A=C(A,B)BC(A,B)A=C(A,B)B を満たす証人 C(A,B)∈VC(A,B)\in V を一つ固定する。これら n(n−1)2\frac{n(n-1)}2 個の対は、証人の候補として VV の nn 個の点に分配されるので、鳩の巣原理により、ある点 PP が少なくとも ⌈n(n−1)/2n⌉=⌈n−12⌉=n2\big\lceil\frac{n(n-1)/2}{n}\big\rceil=\big\lceil\frac{n-1}2\big\rceil=\frac n2 個の対の証人となる（最後の等式は nn が偶数であること、したがって n−1n-1 が奇数であることを用いている）。