MathLabs

第6問

n≥2n\ge2 を整数とし、円周上に等間隔に印をつけた n+1n+1 個の点を考える。これらの点に 0,1,…,n0,1,\ldots,n を1回ずつ用いてラベル付けするすべての方法を考える。円の回転で一方から他方が得られるとき、2つのラベル付けは同じものとみなす。ラベル付けが美しいとは、a+d=b+ca+d=b+c を満たす任意の4つのラベル a<b<c<da<b<c<d について、ラベル aa と dd の点を結ぶ弦が、ラベル bb と cc の点を結ぶ弦と交わらないことをいう。MM を美しいラベル付けの個数、NN を x+y≤nx+y\le n かつ gcd⁡(x,y)=1\gcd(x,y)=1 を満たす正の整数の順序対 (x,y)(x,y) の個数とする。M=N+1M=N+1 を証明せよ。
ステップ 2/5: 構造補題:同じ和の弦は交わらない
前のステップ次のステップ
ざっくり言うと

美しさの条件により、端点ラベルの和が同じ弦は一つの平行に近い族になる。

chords of a fixed sum are pseudo-parallel\text{chords of a fixed sum are pseudo-parallel}
詳しい解説

退化した弦も許し、任意の三本のうち一本が他の二本を隔てるとき擬平行と呼ぶ。ラベル数についての帰納法により、和が k の弦は擬平行である。性質に反する三本があれば一本を基準にし、別の弦の端点和が k より小さい、等しい、大きい場合に分けて、端のラベルを除き 1 を引くと帰納法に反する三本が得られる（最後の場合は先に反射 t↦n−tt\mapsto n-t を行う）。従って同じ和の弦は禁じられた形では交わらない。