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。
第 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 作出的美丽扩展，而每个线性环恰有两个。