トランプシャッフル後のカードの並び順 – 2002年東大 数学 第6問
2002年東大 数学 第6問 はトランプをシャッフルしたときに、カードの並びがどうなるかを求める問題です。問題文は以下のとおりです。
N を正の整数とする。2N個の項からなる数列 \{a_1，a_2，\cdots ，a_N，b_1，b_2，\cdots ，b_N \} を \{ b_1，a_1，b_2，a_2， \cdots ，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≦k≦2Nを満たす任意の整数kに対し， f(k) − 2k は 2N + 1で割り切れることを示せ。
(3) n を正の整数とし，N = 2n−1 のときを考える。数列 {1，2，3，···，2N} を2n回シャッフルすると， {1，2，3，···，2N} にもどることを証明せよ。
やっていることは、トランプをふた山に分けて、パラパラっとやるやつです。筆者はなかなかうまく出来ませんでしたが（カードが互い違いになるようにすることがなかなか出来なかった）、あれをやった後にトランプの並びがどうなっているかを求めようと言うのが、お題です。
関数 f(k) はカードの数字に関する関数のようにも読めますが、実際はカードの位置に関する関数です。左から数えて k 番目のカードがシャッフルによって何番目に移ったかを、 f(k) で表します。
なんかなじみのない設問ですが、少なくとも小問1は何とかなりそうです。捨てるのはもったいないので、まずは食いついてみましょう。
2002年東大 数学 第6問 小問1の解法
これは定義に沿って、数字を並べ替えるだけです。
1,2,3,4,5,6,7,8
↓
5,1,6,2,7,3,8,4
↓
7,5,3,1,8,6,4,2
↓
8,7,6,5,4,3,2,1
と、数字を降順に並べ替えたものになりました。
2002年東大 数学 第6問 小問2の解法
これも定義に沿って確認してみます。
まず 1≦k≦N の場合ですが、定義より
f(k) = 2k
なので、
f(k) - 2k = 0
です。 0 は確かに 2N + 1で割り切れます。
次に N + 1 ≦k≦ 2N の場合です。この場合、
f(k) = 2(k -N) -1 = 2k-2N -1
なので、
f(k) -2k = -(2N +1)
であり、こちらも 2N + 1で割り切れます。
2002年東大 数学 第6問 小問3の解法
ここまでは楽勝でしたが、小問3はどうでしょうか。
小問1で N = 23-1 のとき、3回シャッフルするとカードが降順に並んだので、6回シャッフルするとカードは当然元の順序に戻ります。ここから、 N = 2n-1 のとき、 n 回シャッフルするとカードが降順に並ぶことが証明できれば良い、ということに気がつくことが第1歩です。
ここで、自然数 m に対し、カードの位置に関する関数 fm(k) を、 k 番目のカードが m 回のシャッフル後に移る位置、と定義します。すると、 n 回シャッフルするとカードが降順に並ぶということは、すべての 1≦k≦2N に対し、
f_n (k) + k = 2N+1
であることと同義です。証明すべき内容が定式化出来ました。
何とここで、小問2の 2N + 1 が出てきました！これは小問2の結果をいい感じに適用できそうです。
f_n(k) =f(f_{n-1}(k))なので、小問2の結果より、
f_n (k) -2f_{n-1}(k) \equiv 0 ( \mod 2N +1 )が成り立ちます。漸化式が導出できました！
よって
f_n (k) -2^n k \equiv 0 ( \mod 2N +1 )
すなわち
f_n (k) \equiv 2^n k ( \mod 2N +1 )
です。これにより、
\begin{aligned}
f_n (k) + k & \equiv 2^nk +k \\
& \equiv(2^n+1) k \\
& \equiv (2N +1) k \\
& \equiv 0 ( \mod 2N+1 )
\end{aligned}が成り立ちます。
したがって、ある整数 j が存在して、
f_n (k) + k = (2N+1) j
が成り立ちます。ところが、 fn(k) も k も正なので、
1 \leqq j
です。また、 fn(k) ≦ 2N かつ k ≦ 2N なので、
\begin{aligned}
j & = \frac{f_n (k) + k}{2N +1} \\
& \leqq \frac{4N}{2N +1} =2 -\frac{2}{2N +1} < 2
\end{aligned}であり、
j=1
が成り立ちます。
ゆえに
f_n (k) + k = 2N+1
であり、 2n 回シャッフルするとカードの並びが元に戻ることが証明できました。