第5問

平面上の 2n+1 個の点は、3点が一直線上になく、4点が同一円周上にないとする。3点を通り、その内部にちょうど n-1 点を含む円を集合を分割する円と呼ぶ。分割する円の個数が偶数であることと n が偶数であることが同値であることを示せ。

ステップ 4/5: すべての点対を数える

\sum_{\{A,B\}}q_{AB}=3G,\qquad \binom{2n+1}{2}=n(2n+1)\equiv n\pmod2

詳しい解説

qAB を A,B を通る分割円の個数、G を全分割円の個数とする。前段より各 qAB は奇数である。全点対で qAB を足すと、各分割円は3つの点対をもつので 3G となる。点対は binomial(2n+1,2)=n(2n+1) 個で偶奇は n。3 は奇数なので G の偶奇も n である。