解説

注意

画像の一部が不鮮明で、特に （3） の「$N=2^{n-1}$ のとき、数列 ${1,2,\dots,2N}$ を **2N回** シャッフルすると元にもどる」という箇所の読み取りに不確実性がある。この命題はそのままでは成り立たない。実際、$n=3$ とすると $N=4$ であるが、8回では元にもどらない。

以下では、（1）、（2） はそのまま解き、（3） は数学的に整合する形 「$N=2^{n-1}$ のとき、**2n回** シャッフルすると元にもどる」 として解釈した場合の解答を書く。

方針・初手

1回のシャッフルで、もとの数列の前半にあった項と後半にあった項がどの位置に移るかをまず式で表す。

数列 ${1,2,\dots,2N}$ に対しては、数 $k$ が移る位置 $f(k)$ を具体的に書けるので、これを法 $2N+1$ の合同式で扱うと、繰り返しシャッフルしたときの位置も一気に追える。

解法1

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

$$ {a_1,a_2,\dots,a_N,b_1,b_2,\dots,b_N} $$

と見ると、

$$ a_i=i,\qquad b_i=N+i $$

である。したがって1回シャッフルすると

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

となる。

よって、数 $k$ が移る位置 $f(k)$ は

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

である。

したがって、どちらの場合にも

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

が成り立つ。

（1） 3回シャッフルしたときの数列

ここでは $2N=8$ だから $N=4$ であり、

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

である。

3回シャッフルしたとき、数 $k$ の位置は $f^3(k)$ であるから、

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

となる。

しかも $f^3(k)$ は $1$ 以上 $8$ 以下の整数であるから、

$$ f^3(k)=9-k $$

である。

つまり、もとの数 $k$ は3回シャッフルすると位置 $9-k$ に来る。したがって、位置 $j$ に来る数は

$$ k=9-j $$

であるから、得られる数列は

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

である。

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

上で求めた式

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

をそのまま見ればよい。

**(i)**

$1\le k\le N$ のときは

$$ f(k)-2k=0 $$

であり、これは明らかに $2N+1$ で割り切れる。

**(ii)**

$N+1\le k\le 2N$ のときは

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

であり、これも $2N+1$ で割り切れる。

以上より、任意の整数 $k\ (1\le k\le 2N)$ に対し、

$$ f(k)-2k $$

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

さらに、この結果を繰り返し用いると、$m$ 回シャッフル後の位置 $f^m(k)$ について

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

が帰納的に従う。

（3） 「$2n$ 回シャッフル」と読んだ場合

$N=2^{n-1}$ とする。このとき

$$ 2N=2^n,\qquad 2N+1=2^n+1 $$

である。

上で得た一般式より、$2n$ 回シャッフル後には

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

である。

ここで

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

であるから、

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

となる。したがって

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

である。

しかも $f^{2n}(k)$ も $k$ も、ともに $1$ 以上 $2N=2^n$ 以下の整数である。法 $2^n+1$ で合同な2つの整数がこの範囲に入っていれば、それらは等しい。よって

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

である。

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

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

にもどる。

解説

この問題の本質は、シャッフルを「位置の置換」と見て、その置換を合同式で表すことである。

1回のシャッフルで

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

となるので、繰り返しシャッフルすると

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

となる。したがって、何回で元にもどるかは、結局 $2^m\equiv 1 \pmod{2N+1}$ となる $m$ を調べる問題になる。

なお、画像の （3） を文字どおり「$2N$ 回」と読むと命題は偽である。たとえば $n=3,\ N=4$ のとき、8回シャッフルしても元にもどらない。

答え

**(1)**

3回シャッフル後の数列は

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

である。

**(2)**

任意の $k\ (1\le k\le 2N)$ に対し、

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

すなわち

$$ f(k)-2k $$

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

**(3)**

画像のまま「$2N$ 回」と読むと命題は成り立たない。これを「$2n$ 回」と読めば、$N=2^{n-1}$ のとき $2n$ 回シャッフルすると

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

にもどる。