6東京大学 2002年 数学 第6問解答・解説

1回のシャッフルでは、もとの位置 $i$ にある項は、$1\le i\le N$ なら位置 $2i$ に、$N<i\le2N$ なら位置 $2i-1$ に移る。この位置の対応は項の値によらず一定である。

(1) $N=4$ として操作を3回行うと、 $$\{1,2,3,4,5,6,7,8\}\to\{5,1,6,2,7,3,8,4\}\to\{7,5,3,1,8,6,4,2\}\to\{8,7,6,5,4,3,2,1\}.$$

(2) $1\le k\le N$ なら $k=a_k$ なので $f(k)=2k$。$N<k\le2N$ なら $k=b_{k-N}$ なので、 $$f(k)=2(k-N)-1=2k-(2N+1).$$ したがって前者では $f(k)-2k=0$、後者では $f(k)-2k=-(2N+1)$ となり、いずれも $2N+1$ で割り切れる。

(3) $M=2N+1=2^n+1$ とする。(2)より、1回のシャッフルで位置 $j$ は $2j$ と $M$ を法として合同な位置へ移る。よって $r$ 回後、最初に位置 $k$ にあった数の位置は $2^r k$ と $M$ を法として合同である。ここで $r=2n$ とすると、 $$2^{2n}k=(2^n)^2k\equiv(-1)^2k\equiv k\pmod{2^n+1},$$ となる。最終位置も $1,2,\ldots,2N$ のいずれかであり、この範囲で $k$ と合同な数は $k$ だけなので、全ての数が元の位置に戻り、数列全体も元に戻る。