11. 問題
\(n\) を \(2\) 以上の整数とする.円周上に等間隔に \(n\) 個のマスが並んでいる.ここで,次のようにマスに整数を書き込む操作を考える.
・操作:直前に書き込んだ数字を \(a\) としたとき,直前に書き込んだマスから時計回りに \(a\) 個だけ進んだマスに \(a+1\) を書き込む.
いま,あるマスに \(1\) を書き込んだあと,\(n-1\) 回この操作を繰り返したとき,円周上の \(n\) 個のマスすべてに,互いに異なる整数が \(1\) つずつ書き込まれた.このような \(n\) を全て求めよ.
12. 解答
問題は \(\tfrac12 k(k+1)\equiv \tfrac12 m(m+1) \pmod{n}\),すなわち,\((k-m)(k+m+1)\equiv 0 \pmod{2n}\) を満たす,\(0\leq m< k< n\) なる整数 \(k,m\) が存在しないような \(n\) を全て求めよという問題に帰着される.
[1] \(n\) が奇数のとき:\(m=0, k=n-1\) とすれば \((k-m)(k+m+1)\equiv 0 \pmod{2n}\) を満たすので不適.
[2] \(n\) が偶数のとき:\(n=2^p\times q\) と表すことができる.(\(p\geq 1, q\) は奇数)
[2-1] \(p=1\) のとき:\(k-m\leq n-1\),\(k+m+1\leq (n-1)+(n-2)+1=2n-2\) かつ,\(k-m\) と \(k+m+1\) がともに偶数となることはないので,\((k-m)(k+m+1)\) は \(2n\) で割り切れない.よってこれは条件を満たす.
[2-2] \(p\geq 3\) のとき:\(k,m\) の組であって,\(k-m=2^{p+1}\) かつ \(k+m+1=q\) を満たすものを \((k,m)=(k_1,m_1)\),\(k-m=q\) かつ \(k+m+1=2^{p+1}\) を満たすものを \((k,m)=(k_2,m_2)\) とする.すると,
\[k_1=k_2=2^p+\frac{q-1}{2} < 2^p\times q = n,\]
\[m_1=\frac{q-1}{2}-2^p,\quad m_2=2^p-\frac{q+1}{2}\]
となり,\(m_1,m_2\) のうち,一方でも \(0\) 以上ならこれが解である.いま,\(m_1,m_2\) ともに負と仮定すると,
\[2^{p+1}-1 < q < 2^{p+1}+1\]
となるが,これを満たす奇数 \(q\) は存在しない.よって,\(m_1,m_2\) のうち少なくとも一方は \(0\) 以上であり,\((k-m)(k+m+1)\equiv 0 \pmod{2n}\) を満たす \(k,m\) の存在が示されたので,これは不適.
以上より,条件を満たす \(n\) は,正の整数 \(k\) を用いて \(\mathbf{n=2^k}\) と表せるものである.