2002年(平成14年)東京大学前期-数学(理科)[6] - [別館]球面倶楽部零八式markIISR

2024.02.13記

[6] $N$ を正の整数とする． $2N$ 個の項からなる数列
$\{ a_1， a_2， …， a_N， b_1， b_2， …， b_N \}$
を
$\{ b_1， a_1， b_2， a_2， …， b_N， a_N \}$
という数列に並べ替える操作を「シャッフル」と呼ぶことにする．並べ替えた数列は $b_1$ を初項とし， $b_i$ の次に $a_i$ ， $a_i$ の次に $b_{i+1}$ が来るようなものになる．また，数列 $\{ 1， 2， …$ ， $2N \}$ をシャッフルしたときに得られる数列において，数 $k$ が現れる位置を $f(k)$ で表す．
たとえば， $N=3$ のとき， $\{ 1， 2， 3， 4， 5， 6 \}$ をシャッフルすると $\{ 4， 1， 5， 2， 6， 3 \}$ となるので， $f(1)=2$ ， $f(2)=4$ ， $f(3)=6$ ， $f(4)=1$ ， $f(5)=3$ ， $f(6)=5$ である．

(1) 数列 $\{ 1， 2， 3， 4， 5， 6， 7， 8 \}$ を $3$ 回シャッフルしたときに得られる数列を求めよ．

(2) $1\leqq k\leqq 2N$ を満たす任意の整数 $k$ に対し， $f(k)-2k$ は $2N+1$ で割り切れることを示せ．

(3) $n$ を正の整数とし， $N=2^{n-1}$ のときを考える．数列 $\{ 1， 2， 3， …， 2N \}$ を $2n$ 回シャッフルすると， $\{ 1， 2， 3， …， 2N \}$ にもどることを証明せよ．

2021.01.18記

[解答]
(1) $\{8,7,6,5,4,3,2,1\}$ となる．

(2) $k$ （ $1\leqq k\leqq N$ ）番目の数はシャッフルによって $2k$ 番目に移動し，
$k$ （ $N+1\leqq k\leqq 2N$ ）番目の数はシャッフルによって $2k-2N-1$ 番目に移動するので，
$f(k)-2k=0，2N-1$ となり題意をみたす．

(3) 任意の $k$ について， $2n$ 回シャッフルしたときの $k$ 番目の数の位置は
$2^{2n}k(\mbox{mod}\, 2N+1)$ であり，
$2^{2n}k-k$ $=(2^n+1)(2^n-1)k$ $=(2N+1)(2^n-1)k$ $\equiv 0(\mbox{mod}\, 2N+1)$ であるから，
$2n$ 回シャッフルしたときの $k$ 番目の数の位置は同じく $k$ 番目である．

つまり， $2n$ 回シャッフルしたとき，最初の並びに戻る．

解答では， $k$ 番目にあった数が何処に移動するかに着目したが，
$k$ 番目にある数がどう変化するか着目すると次のようになる．

$1$ 〜 $2N=2^n$ を $0$ 〜 $2^n-1$ とし，頭に0をつけて $n$ 桁の2進数表示をするとき，
シャッフルの結果は，末尾を取り除き，0,1を反転させて頭につけることと対応する．

(1) 3桁の2進数を末尾を取り除き，0,1を反転させて頭につけることを3回行うと，全ての0,1が反転したことになるので，逆順にならぶ．
(3) $n$ 桁の2進数を末尾を取り除き，0,1を反転させて頭につけることを $n$ 回行うと，全ての0,1が反転したことになるので，逆順にならぶ．
これを2セット繰り返すので，元に戻る．

ということがわかる．

[解答]
(2) は略

(3) 以下， $2N+1$ を法として考える．
数を1ずつ減らして $0〜2N-1$ が並んでいたとする．このとき， $m+1$ 番目にある数は $m$ である．
数 $i$ は $i+1$ 番目の数なので，シャッフル後は $2i+2$ 番目にあるので $2i+1\equiv m$ をみたす $i$ が
$m$ があった場所にやってくる．

ここで， $m$ が奇数 $2m'+1$ のとき， $2i+1=m=2m'+1$ ，つまり $i=m'$ (1引いて2で割る) となる．
また， $m$ が偶数 $2m'$ のとき， $2i+1=m+2N+1=2m'+2N+1$ ，つまり $i=m'+N$ (2で割って $N$ を足す)となる．
この操作を2進法で考えると， $m$ を $n$ 桁の2進数で表現し，末尾を取り除き，0,1を反転させて頭につけることを行っていることになる．

シャッフル2回目で $m$ があった場所にやってくる数は
シャッフル1回目で $m$ を $n$ 桁の2進数で表現し，末尾を取り除き，0,1を反転させて頭につけた数 $i$ があった場所にやってきた数だから， $i$ を $n$ 桁の2進数で表現し，末尾を取り除き，0,1を反転させて頭につけた数であることがわかり，これは

$m$ を $n$ 桁の2進数で表現し，末尾を取り除き，0,1を反転させて頭につけることを2回繰り返して得られる数

となる．帰納的にシャッフル $k$ 回目で $m$ があった場所にやってくる数は $m$ を $n$ 桁の2進数で表現し，末尾を取り除き，0,1を反転させて頭につけることを $k$ 回繰り返して得られる数であることがわかる．

以上から，シャッフルを $N$ 回繰り返すと、 $m$ があった場所にやってくる数は $m$ を $n$ 桁の2進数で表現し，末尾を取り除き，0,1を反転させて頭につけることを $n$ 回繰り返して得られる数であることから， $m$ を $n$ 桁の2進数で表現したものの $0,1$ を全部反転したものとなり，これは $(2N-1)-m$ であるから，逆順に並ぶことがわかる．よってこれを2回繰り返すと，もとと同じ順序に並ぶことがわかる．

よって(1)の答は逆順に並び，(3)が証明された.