Question

課間休息時，n個學(xué)生圍著老師坐成一圈做游戲，老師按順時針方向并按下列規(guī)則給學(xué)生們發(fā)糖：他選擇一個學(xué)生并給一塊糖，隔一個學(xué)生給下一個學(xué)生一塊，再隔2個學(xué)生給下一個學(xué)生一塊，再隔3個學(xué)生給下一個學(xué)生一塊…．試確定n的值，使最后(也許繞許多圈)所有學(xué)生每人至少有一塊糖．

Answer 1

解析：問題等價于確定正整數(shù)n，使同余式

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

對任意正整數(shù)a都有解．

我們證明當(dāng)且僅當(dāng)n是2的方冪時，(1)式總有解．

若n不是2的方冪，則n有奇素因數(shù)p．

由于1，1＋2，1＋2＋3，…，1＋2＋…＋(p－1)，1＋2＋…＋p至多表示mod p的p－1個剩余類(最后兩個數(shù)在同一個剩余類中)，所以1＋2＋…＋x也至多表示mod p的p－1個剩余類，從而總有a使1＋2＋…＋x≡a(mod p)無解，這時(1)也無解．

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

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

設(shè)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中，一個是奇數(shù)，一個是偶數(shù)，所以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(tǒng)．

因此(2)中的2^k個偶數(shù)mod 2^k＋1互不同余，從而對任意整數(shù)a，方程x(x＋1)≡2a(mod 2n)有解，即(1)有解．