第4問

休み時間にn人の子どもが輪になって座っている。先生は1人を選んで飴を渡し、次の1人を飛ばしてその次の人に渡し、以後は2人、3人というように飛ばす。最終的に全員が少なくとも1個の飴を受け取る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で同じ値を2回取る。この非単射性は中国剰余定理によって法nにも持ち上がるので、全員を訪問することはできない。