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。
第 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）。因此等和弦不会以禁形相交。