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。
第 4/5 步：计算非线性环与线性环的扩展数
上一步下一步
通俗地说

非线性环中 n 只有一个插入位置，线性环中有紧邻 0 的两个位置；线性环的数量由欧拉函数计数。

Ln−1=φ(n),Mn=Mn−1+φ(n)L_{n-1}=\varphi(n),\qquad M_n=M_{n-1}+\varphi(n)
详细分析

对于非线性环，拟平行的 n 弦至多留下一个放置 n 的位置；放在那里仍然美丽，因为任何禁形相交经关于 n 弦反射都会变成原环中已有的禁形相交。对于线性环，n 必须紧邻 0 的顺时针或逆时针一侧，且两种插入都美丽。{0,…,n−1}\{0,\ldots,n-1\} 上的线性环由与 n 互素的步长决定，故有 φ(n)\varphi(n) 个。若其数目为 Ln−1L_{n-1}，则 Mn=Mn−1+Ln−1=Mn−1+φ(n)M_n=M_{n-1}+L_{n-1}=M_{n-1}+\varphi(n)。