MathLabs

第5問

平面上の 2n+1 個の点は、3点が一直線上になく、4点が同一円周上にないとする。3点を通り、その内部にちょうど n-1 点を含む円を集合を分割する円と呼ぶ。分割する円の個数が偶数であることと n が偶数であることが同値であることを示せ。
ステップ 3/5: 分割円の個数が奇数であること
#{i:fi=n−1}≡1(mod2)\#\{i:f_i=n-1\}\equiv1\pmod2
詳しい解説

Ci が集合を分割する条件は fi=n-1 である。順序列が水準 n-1 を横切るとき、水準上の添字の個数の偶奇は水準への出入りで変化する。この水準上の連続部分では、両端の Xi の側が交互になるため長さは奇数である。最初と最後の円を比較し(端点が水準上なら同じ片側の議論を用いる)と、偶奇の意味で列は反対側から始まり反対側で終わる。従って fi=n-1 となる i の個数は奇数である。よって任意の A,B を通る分割円の個数は奇数である。