第4题

课间，n个孩子围坐成一圈。老师选定一个孩子给他一颗糖，跳过下一个孩子后给再下一个孩子；接着跳过2个孩子、再跳过3个孩子，如此继续。求哪些n能使每个孩子最终都至少得到一颗糖。

第 2/4 步：排除奇因子

n=2^a m,\ m>1\text{ odd}:\quad f(0)\equiv f(m-1)\equiv0\pmod m.

详细分析

若n含有奇因子m，则当x在模m下同余于0或m-1时，m整除x(x+1)。于是f在模m下两次取得同一值。由中国剩余定理，这种非单射性可提升到模n，因此不可能访问所有孩子。