MathLabs

第6题

设 n≥2n\ge2 为整数,在圆周上标出 n+1n+1 个等间距的点。考虑用 0,1,…,n0,1,\ldots,n 对这些点作标号、每个数恰用一次的所有方式;若一种标号可由另一种经圆的旋转得到,则视为相同的标号。称一种标号是美丽的,如果对任意满足 a+d=b+ca+d=b+c 的四个标号 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。
第 3/5 步：用 n 弦刻画线性环
上一步下一步
通俗地说

n 弦覆盖除 0 外的所有点；0 是否位于它们之间决定标号是否构成等差数列。

0 lies between two n-chords⟺the ring is nonlinear0\text{ lies between two n-chords}\Longleftrightarrow\text{the ring is nonlinear}
详细分析

在 {0,…,n−1}\{0,\ldots,n-1\} 上的环中，总和为 n 的弦连接互补标签 aa 与 n−an-a，覆盖除 0 外的所有点。由伪平行性它们实际互相平行。若 0 位于两条此类弦之间，这是唯一的非线性情形；若 0 位于所有弦同侧，则总和为 n 与 n-1 的弦共同表明映射 t↦n−1−t(modn)t\mapsto n-1-t\pmod n 是旋转，故环为线性的。这就证明了该刻画。