トップ› 東京大学› 2002年› 理系第6問

東京大学 2002年理系第6問解説

方針・初手

シャッフルの操作によって、数列の各要素がどの位置に移動するかを数式で定式化する。元の数列で $k$ 番目にある要素が、シャッフル後に何番目になるかを $N$ を用いて表すことが第一歩となる。操作の規則性から、前半部分と後半部分で場合分けを行って位置の変化を追う。また、(2)の証明を見据えると、位置の変化を法 $2N+1$ の合同式（モジュロ演算）で捉えることで、複数回のシャッフルの結果を容易に計算できるようになる。

解法1

(1) 与えられたシャッフルの定義に従い、数列 $\{1, 2, 3, 4, 5, 6, 7, 8\}$ を具体的に並べ替える。ここでは $2N = 8$ より $N=4$ であり、前半4項が $a_i$、後半4項が $b_i$ に対応する。

1回目のシャッフル：前半部分は $1, 2, 3, 4$、後半部分は $5, 6, 7, 8$ である。後半の要素と前半の要素を交互に並べるため、得られる数列は $\{5, 1, 6, 2, 7, 3, 8, 4\}$ となる。

2回目のシャッフル： 1回目と同様に、前半部分 $5, 1, 6, 2$ と後半部分 $7, 3, 8, 4$ を交互に並べる。 $\{7, 5, 3, 1, 8, 6, 4, 2\}$ となる。

3回目のシャッフル：前半部分 $7, 5, 3, 1$ と後半部分 $8, 6, 4, 2$ を交互に並べる。 $\{8, 7, 6, 5, 4, 3, 2, 1\}$ となる。

(2) 元の数列における $k$ 番目の要素が、シャッフルによってどの位置に移動するかを考える。 $k$ の値によって前半部分か後半部分かが変わるため、場合分けを行う。

(i)

$1 \leqq k \leqq N$ のとき $k$ 番目の要素は $a_k$ に該当する。シャッフルの定義より、$a_k$ はシャッフル後の数列において $2k$ 番目に位置する。したがって、$f(k) = 2k$ である。このとき、

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

となり、$0 = 0 \cdot (2N+1)$ であるから、$2N+1$ で割り切れる。

(ii)

$N+1 \leqq k \leqq 2N$ のとき $k$ 番目の要素は $b_{k-N}$ に該当する。シャッフルの定義より、$b_{k-N}$ はシャッフル後の数列において $2(k-N)-1$ 番目に位置する。したがって、$f(k) = 2k - 2N - 1$ である。このとき、

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

となり、$-(2N+1) = -1 \cdot (2N+1)$ であるから、$2N+1$ で割り切れる。

（i）、（ii）のいずれの場合も、$f(k) - 2k$ は $2N+1$ で割り切れる。よって、任意の整数 $k$ ($1 \leqq k \leqq 2N$) に対し、$f(k) - 2k$ は $2N+1$ で割り切れることが示された。

(3)

（2）の結果より、任意の整数 $k$ ($1 \leqq k \leqq 2N$) に対して、$f(k) - 2k$ は $2N+1$ の倍数である。これを合同式を用いて表すと、

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

となる。これは、1回のシャッフルで元の位置 $k$ にあった数が位置 $2k \pmod{2N+1}$ に移動することを意味する。数列を $m$ 回シャッフルしたときに数 $k$ が現れる位置を $f_m(k)$ とすると、繰り返しこの関係を適用することで、

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

が成り立つ。

ここで、$N = 2^{n-1}$ のとき、$2N = 2^n$ であるから、法は $2N+1 = 2^n+1$ となる。数列を $2n$ 回シャッフルしたときの位置 $f_{2n}(k)$ について考える。上の式に $m=2n$ を代入すると、

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

となる。ここで、$2^{2n} = (2^n)^2$ であり、法 $2^n+1$ において $2^n \equiv -1 \pmod{2^n+1}$ が成り立つことから、

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

である。これを代入すると、

$$ f_{2n}(k) \equiv 1 \cdot k = k \pmod{2^n+1} $$

が成り立つ。

$f_{2n}(k)$ はシャッフル後の位置であるから $1 \leqq f_{2n}(k) \leqq 2N$ を満たし、$k$ も元の位置であるから $1 \leqq k \leqq 2N$ を満たす。すなわち、両者ともに $1$ 以上 $2^n$ 以下の整数である。 $1$ 以上 $2^n$ 以下の範囲にある2つの整数が、法 $2^n+1$ で合同であるならば、両者の差は $0$ でなければならない。ゆえに、

$$ f_{2n}(k) = k $$

が成り立つ。これは、任意の要素が $2n$ 回のシャッフルによって元の位置に戻ることを示している。したがって、数列 $\{1, 2, 3, \cdots, 2N\}$ は $2n$ 回シャッフルすると元の数列にもどることが証明された。

解説

トランプのシャッフル（パーフェクト・シャッフル、あるいはファロ・シャッフル）を題材にした問題である。この問題のように、山札を半分に分け、下の束の1枚目から交互に重なるように交差させるシャッフルは「イン・シャッフル」と呼ばれる。この操作の最大の特徴は、(2)で証明したように「要素の位置の推移が法 $2N+1$ における $2$ 倍の演算として表せる」ことにある。この性質を見抜ければ、(3)は合同式の累乗の周期性を問う典型的な整数問題へと帰着される。(3)における $2^n \equiv -1 \pmod{2^n+1}$ を利用して $2^{2n} \equiv 1$ を導く論理は、フェルマーの小定理などを背景とする位数の議論において非常によく用いられる手法である。