解説

方針・初手

まず、$1,2,\dots,2N$ を1回シャッフルしたとき、各数 $k$ がどの位置へ移るかを具体的に式で表す。

前半の $1,2,\dots,N$ は偶数番目に、後半の $N+1,N+2,\dots,2N$ は奇数番目に入るので、$f(k)$ は場合分けで簡単に書ける。そこから

$$ f(k)\equiv 2k \pmod{2N+1} $$

が従う。

この合同式を使うと、繰り返しシャッフルしたときの位置も

$$ f^{\circ m}(k)\equiv 2^m k \pmod{2N+1} $$

と表せるので、（1） も （3） もまとめて処理できる。

解法1

（1） 数列 ${1,2,3,4,5,6,7,8}$ を3回シャッフルしたとき

このとき $N=4$ であるから、$2N+1=9$ である。

1回シャッフルで数 $k$ の位置は $f(k)$ であり、後で示す （2） より

$$ f(k)\equiv 2k \pmod{9} $$

が成り立つ。したがって3回シャッフル後の位置は

$$ f^{\circ 3}(k)\equiv 2^3k=8k\equiv -k \pmod{9} $$

である。

ここで $f^{\circ 3}(k)$ は $1,2,\dots,8$ のいずれかであるから、

$$ f^{\circ 3}(k)=9-k $$

となる。

つまり数 $k$ は位置 $9-k$ に来るので、位置 $1,2,\dots,8$ に並ぶ数は順に

$$ 8,7,6,5,4,3,2,1 $$

である。

よって、求める数列は

$$ {8,7,6,5,4,3,2,1} $$

である。

**(2)**

$f(k)-2k$ は $2N+1$ で割り切れることの証明

数列 ${1,2,\dots,2N}$ を

$$ {1,2,\dots,N,\ N+1,N+2,\dots,2N} $$

と見れば、前半が $a_1,a_2,\dots,a_N$、後半が $b_1,b_2,\dots,b_N$ に対応する。したがって1回シャッフルすると

$$ {N+1,1,N+2,2,\dots,2N,N} $$

となる。

よって $1\le k\le N$ のとき、$k$ は偶数番目に入るから

$$ f(k)=2k $$

である。

また、$N+1\le k\le 2N$ のとき、$k=N+i$ とおけば $1\le i\le N$ であり、$k$ は $2i-1$ 番目に入るから

$$ f(k)=2i-1=2(k-N)-1=2k-(2N+1) $$

である。

したがって

$$ f(k)-2k= \begin{cases} 0 & (1\le k\le N),\\ -(2N+1) & (N+1\le k\le 2N). \end{cases} $$

よって、いずれの場合も $f(k)-2k$ は $2N+1$ で割り切れる。

すなわち

$$ f(k)\equiv 2k \pmod{2N+1} $$

が成り立つ。

**(3)**

$N=2^{n-1}$ のとき、$2n$ 回シャッフルすると元にもどることの証明

まず、1回シャッフルで

$$ f(k)\equiv 2k \pmod{2N+1} $$

であるから、$m$ 回シャッフル後の位置を $f^{\circ m}(k)$ と書けば、帰納法により

$$ f^{\circ m}(k)\equiv 2^m k \pmod{2N+1} $$

が成り立つ。

実際、$m=1$ では成立している。$m$ 回で成立するとすると、

$$ f^{\circ(m+1)}(k) =f\bigl(f^{\circ m}(k)\bigr) \equiv 2f^{\circ m}(k) \equiv 2\cdot 2^m k =2^{m+1}k \pmod{2N+1} $$

となるので、すべての $m$ で成り立つ。

ここで $N=2^{n-1}$ だから

$$ 2N+1=2^n+1 $$

である。

したがって、$2n$ 回シャッフル後には

$$ f^{\circ 2n}(k)\equiv 2^{2n}k \pmod{2^n+1} $$

となる。一方、

$$ 2^n\equiv -1 \pmod{2^n+1} $$

であるから、

$$ 2^{2n}=(2^n)^2\equiv (-1)^2=1 \pmod{2^n+1} $$

となる。よって

$$ f^{\circ 2n}(k)\equiv k \pmod{2^n+1} $$

である。

しかも $f^{\circ 2n}(k)$ も $k$ もともに $1,2,\dots,2N(=2^n)$ の範囲にある。$1$ 以上 $2^n$ 以下の整数で、法 $2^n+1$ で合同なものは一致するしかないから、

$$ f^{\circ 2n}(k)=k $$

である。

これはすべての $k=1,2,\dots,2N$ について成り立つので、$2n$ 回シャッフルすると数列全体が

$$ {1,2,3,\dots,2N} $$

にもどる。

解説

この問題の本質は、シャッフルを「並び替え」として見るだけでなく、**各数がどの位置へ移るかという写像 $f$** として捉えることにある。

1回のシャッフルで

$$ f(k)\equiv 2k \pmod{2N+1} $$

が得られると、繰り返しシャッフルは「$2$ を何回か掛けること」と同じ形になり、合同式の問題へ帰着する。

特に （3） では、$N=2^{n-1}$ とおくことで

$$ 2N+1=2^n+1 $$

となり、

$$ 2^n\equiv -1 \pmod{2^n+1} $$

がすぐ使える。この設定があるため、周期がきれいに求まるのである。

答え

**(1)**

$$ {8,7,6,5,4,3,2,1} $$

**(2)**

任意の $1\le k\le 2N$ に対して

$$ f(k)\equiv 2k \pmod{2N+1} $$

したがって

$$ f(k)-2k $$

は $2N+1$ で割り切れる。

**(3)**

$N=2^{n-1}$ のとき、$2n$ 回シャッフル後の位置は

$$ f^{\circ 2n}(k)\equiv 2^{2n}k \equiv k \pmod{2^n+1} $$

となるので、すべての $k$ について元の位置にもどる。よって数列 ${1,2,3,\dots,2N}$ は $2n$ 回シャッフルすると元にもどる。