東大理系数学'02年前期[6]

Nを正の整数とする。個の項からなる数列

という数列に並べ替える操作を「シャッフル」と呼ぶことにする。並べ替えた数列はを初項とし、の次にの次にが来るようなものになる。また、数列をシャッフルしたときに得られる数列において、数kが現れる位置をで表す。
たとえば、のとき、をシャッフルするととなるので、である。

(1) 数列3回シャッフルしたときに得られる数列を求めよ。
(2) を満たす任意の整数kに対し、で割り切れることを示せ。
(3) nを正の整数とし、のときを考える。数列回シャッフルすると、にもどることを証明せよ。

解答 2002年前期の東大の問題は、この問題が考えにくいので、他を易しくしたのかも知れません。

(1) 各回ごとにシャッフルした結果を書いてみます。
より
......[]
(2) 問題文のまま考えようとしても、よほどの天才でない限り、何も浮かばないと思います。
文字で問題が書かれているので抽象的で、どのようなことを言っている問題なのか、感じがつかめないのです。
こういう時は、具体的に数値を代入して、調べていきます。

(1)ではの場合を調べました。ここでもとして考えてみます。1回シャッフルした結果について、8種類の数の各々について、 ()の動きを調べてみます。
k
120
240
360
480
51
63
75
87
左表で、例えば、上から6行目に、 6, 3, と数が並んでいますが、これは、(1)1回シャッフルした結果、63番目に出てきて、であることを意味しています。

のとき、ですが、の欄に並んでいる数は、
0なので、9で割り切れます。
これを、一般的な正の整数
Nについて示せ、と、言っているのです。

まず、の場合を例にとりながら、方針を立てます。表を見ると、
2つのタイプに分かれることにすぐ気づきます。
のグループ
(上の4)のグループ(下の4)です。
1回シャッフルした結果を眺めると、のグループでは、になっていることがわかります。1つずつ互い違いに割り込んでくるからです。
のグループでは、になっていますが、これはどのような仕掛けになっているのでしょうか?

1回シャッフルした結果を見ると、このグループの先頭の51番目に入り、以後、2つのグループが互い違いに入るので、1つおきに6, 7, 8が入り、63番目、75番目、87番目という具合に入っていきます。

一般的に、個の項からなる数列を前半の
N個のグループと後半のN個のグループに分けます。
シャッフルすると、先頭はになります。です。

2番目は、1になります。です。
から順にまで、
1番目のより、1つおきに、3番目、5番目、・・・という具合に入っていくので、,・・・,
即ち、となる整数
kについて、となります(などを確かめてください)
2から順にNまで、1の入った2番目の位置より、1つおきに、4番目、6番目、・・・という具合に入っていくので、,・・・,
即ち、となる整数
kについて、となります。

以上より、
となる整数
kについて、で割り切れます。
となる整数
kについて、で割り切れます。
よって、示されました。

(3) (1)よりのとき、つまりのとき、n回、つまり3回シャッフルすると、ちょうど順番が正反対になることがわかります。従って、さらにn回計回、つまり、はじめから6回シャッフルすれば、順番がまた正反対になって、元に戻るわけです。

m(mは、を満たす整数)シャッフルしたときのkの位置をと書くことにします。です。
示すべきこと、つまり、回シャッフルして順番が元に戻るということは、となる、ということです。


(1)の場合を調べましたが、これを利用して、の場合について、シャッフルするごとにkがどこに移動するか、を調べてみます。
k
1248
2487
3636
4875
5124
6363
7512
8751
左表で、例えば、上から4行目ののところは、8, 7, 5となっていますが、,つまり、4は、1回シャッフルすると8番目に、2回シャッフルすると7番目に、3回シャッフルすると5番目に来る、という意味です。

ここで、一つ気がつきたいことがあります。
(2)からを引いたときで割り切れることを確かめました。これを応用してみます。
(2)では、からはを引いて9で割り切れることを確かめたのですが、に対して、シャッフルするごとに、と、2倍ずつされて行きます。
そこで、についても、シャッフルするごとに
2倍ずつして行き、で割ったものを考えます。
9で割ると、に対して、9で割った余りは、となり、と一致します。
9で割ると、に対して、9で割った余りは、となり、と一致します。
9で割ると、に対して、9で割った余りは、となり、と一致します。

そこで、一般的に、のとき、
mを自然数、kを満たす整数だとして、で割った余りがと一致すること、つまり、商をとして、
 ・・・@
と書けることを、mに関する数学的帰納法を用いて示します。

(T) のとき、(2)より、は、で割り切れるので、商をとして、
・・・A
これは、で割ると、余りがであることを意味します。

(U) のとき成り立つとします。で割った余りがと一致するので、
両辺に2をかけて、
・・・B
の場合を考えるのに当たって、この式に出てくるを何とかしなくてはいけません。
上のの表をよく見ると、どの欄においても、
1の次には22の次には43の次には64の次には85の次には16の次には37の次には58の次には7が来ます。ということは、は、kとしたものに一致する(,・・・)、ということです。つまり、
言い換えると、kl回シャッフルして番目の位置にいたとして、次のシャッフルでどこに行くか(これが、です)と言うと、最初に番目の位置にいたのはkなので、k1回シャッフルして行く位置と同じ位置に行く、つまり、に行く、ということです。
Aの
kに入れ替えると、
これをBに代入すると、
は整数なので、これは、で割った余りがであることを意味します。つまり、においても成り立ちます。

(T)(U)より、で割った余りは、と一致します。

ここで、@において、とすると、


は整数なので、これは、で割った余りがkであることを意味しています。
で割った余りなので、
ですから、です。
これは、数列回シャッフルすると、にもどることを意味します。


   東大理系数学TOP   数学TOP   CHALLENGE from the VOID   TOPページに戻る

(C)2005,2006,2007,2008,2009
(有)りるらる
CFV21 随時入会受付中!
CFV21ご入会は、まず、
こちらまでメールをお送りください。
 雑誌「大学への数学」購入