MathLabs

第6题

设 pp 为奇素数。集合 {1,2,…,2p}\{1,2,\ldots,2p\} 的 pp 元子集 AA 中,元素之和被 pp 整除的有多少个?
第 2/3 步:形成循环轨道
通俗地说

平移第一块中所有选中元素保持个数,平移 pp 次后回到原状。

T↦T+1(modp)T\mapsto T+1\pmod p
详细分析

固定与 {p+1,…,2p}\{p+1,\ldots,2p\} 的交集,并将 rr 中选出的 {1,…,p}\{1,\ldots,p\} 个元素按 T↦T+1(modp)T\mapsto T+1\pmod p 平移。因 0<r<p0<r<p,非零平移不会固定 TT,所以每轨道恰有 pp 个不同子集。每次平移使第一块元素和模 rr 增加 pp。