第4問

休み時間にn人の子どもが輪になって座っている。先生は1人を選んで飴を渡し、次の1人を飛ばしてその次の人に渡し、以後は2人、3人というように飛ばす。最終的に全員が少なくとも1個の飴を受け取るnをすべて求めよ。

ステップ 3/4: 2つの三角数を比較する

f(x)-f(y)=\frac{(x-y)(x+y+1)}2.

詳しい解説

n=2^aでf(x)=f(y) (mod n)と仮定する。このとき $2^{a+1}$ は(x-y)(x+y+1)を割り切る。xとyが同じ偶奇なら第2因子は奇数なのでx=y (mod $2^{a+1}$ )となる。偶奇が異なればx-yは奇数で、第2因子は0と $2^{a+1}$ の間にあるため、 $2^{a+1}$ の倍数にはなれない。