第4問

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

ステップ 1/4: 訪問位置を符号化する

f(x)=\frac{x(x+1)}2\pmod n.

詳しい解説

0,1,2,...人を飛ばすと、連続する訪問位置の差は法nでそれぞれ1,2,3,...となる。したがって初期ラベルによる平行移動を除けば、x回後の位置は三角数f(x)である。