Question

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

Answer 1

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

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

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

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

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

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

若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)

因?yàn)閤－y，x＋y＋1中，一個(gè)是奇數(shù)，一個(gè)是偶數(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個(gè)偶數(shù)mod 2^k＋1互不同余，從而對(duì)任意整數(shù)a，方程x(x＋1)≡2a(mod 2n)有解，即(1)有解．