Question

课间休息时，n个学生围着老师坐成一圈做游戏，老师按顺时针方向并按下列规则给学生们发糖：他选择一个学生并给一块糖，隔一个学生给下一个学生一块，再隔2个学生给下一个学生一块，再隔3个学生给下一个学生一块…．试确定n的值，使最后(也许绕许多圈)所有学生每人至少有一块糖．

Answer 1

解析：问题等价于确定正整数n，使同余式

1＋2＋3＋…＋x＝a(modn)                        (1)

对任意正整数a都有解．

我们证明当且仅当n是2的方幂时，(1)式总有解．

若n不是2的方幂，则n有奇素因数p．

由于1，1＋2，1＋2＋3，…，1＋2＋…＋(p－1)，1＋2＋…＋p至多表示mod p的p－1个剩余类(最后两个数在同一个剩余类中)，所以1＋2＋…＋x也至多表示mod p的p－1个剩余类，从而总有a使1＋2＋…＋x≡a(mod p)无解，这时(1)也无解．

若n＝2^k(k≥1)，考察下列各数：

0×1，1×2，2×3，…，(2^k－1)2^k                                 (2)

设x(x＋1)≡y(y＋1)、(mod 2^k＋1)，其中0≤x，y≤2k－1，则

x²－y²＋x－y≡(x－y)(x＋y＋1)≡0(mod 2^k＋1)

因为x－y，x＋y＋1中，一个是奇数，一个是偶数，所以x－y≡0(mod2^k＋1)或x＋y＋1≡0(mod 2^k＋1)

由后者得：

2^k＋1≤x＋y＋1≤2^k－1＋2^k－1＋1＝2^k＋1－1

矛盾．故  x≡y(mod 2^k＋1)，即x＝y．

因此(2)中的2^k个偶数mod 2^k＋1互不同余，从而对任意整数a，方程x(x＋1)≡2a(mod 2n)有解，即(1)有解．