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 を証明せよ。
ステップ 1/5: 美しい環を線形と非線形に分類する
前のステップ次のステップ
ざっくり言うと

帰納法は最大ラベルを除いた後にそれを挿入できる位置だけに依存する。

A ring is linear if its labels form an arithmetic progression modulo n+1\text{A ring is linear if its labels form an arithmetic progression modulo }n+1
詳しい解説

等間隔点のラベル付けを環と呼び、円周上のラベルが n+1n+1 を法とする等差数列をなすとき線形と呼ぶ。ラベル n の点を除いて {0,…,n−1}\{0,\ldots,n-1\} 上の環を得る。非線形環は n の美しい拡張をちょうど一つ、線形環はちょうど二つ持つことを示す。