東大理系数学'02年前期[6]
Nを正の整数とする。
個の項からなる数列
を
という数列に並べ替える操作を「シャッフル」と呼ぶことにする。並べ替えた数列は
を初項とし、
の次に
，
の次に
が来るようなものになる。また、数列
をシャッフルしたときに得られる数列において、数kが現れる位置を
で表す。
たとえば、
のとき、
をシャッフルすると
となるので、
，
，
，
，
，
である。
(1) 数列
を3回シャッフルしたときに得られる数列を求めよ。 (2) 
を満たす任意の整数kに対し、
は
で割り切れることを示せ。 (3) nを正の整数とし、
のときを考える。数列
を
回シャッフルすると、
にもどることを証明せよ。
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
解答 2002年前期の東大の問題は、この問題が考えにくいので、他を易しくしたのかも知れません。
(1) 各回ごとにシャッフルした結果を書いてみます。
(2) 問題文のまま考えようとしても、よほどの天才でない限り、何も浮かばないと思います。
文字で問題が書かれているので抽象的で、どのようなことを言っている問題なのか、感じがつかめないのです。
こういう時は、具体的に数値を代入して、調べていきます。(1)では
の場合を調べました。ここでも
として考えてみます。1回シャッフルした結果
について、8種類の数の各々について、
と
(
)の動きを調べてみます。左表で、例えば、上から6行目に、 6, 3, 
と数が並んでいますが、これは、(1)で1回シャッフルした結果、6が3番目に出てきて、
，
であることを意味しています。
のとき、
ですが、
の欄に並んでいる数は、0か
なので、
は9で割り切れます。
これを、一般的な正の整数Nについて示せ、と、言っているのです。
まず、
の場合を例にとりながら、方針を立てます。表を見ると、2つのタイプに分かれることにすぐ気づきます。
のグループ(上の4行)と
のグループ(下の4行)です。1回シャッフルした結果を眺めると、
のグループでは、
になっていることがわかります。
が1つずつ互い違いに割り込んでくるからです。
のグループでは、
になっていますが、これはどのような仕掛けになっているのでしょうか？1回シャッフルした結果
を見ると、このグループの先頭の5が1番目に入り、以後、2つのグループが互い違いに入るので、1つおきに6, 7, 8が入り、6は3番目、7は5番目、8は7番目という具合に入っていきます。
一般的に、
個の項からなる数列
を前半の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 |  |  |  |
| 1 | 2 | 4 | 8 |
| 2 | 4 | 8 | 7 |
| 3 | 6 | 3 | 6 |
| 4 | 8 | 7 | 5 |
| 5 | 1 | 2 | 4 |
| 6 | 3 | 6 | 3 |
| 7 | 5 | 1 | 2 |
| 8 | 7 | 5 | 1 |
左表で、例えば、上から4行目の
のところは、8, 7, 5となっていますが、
，
，
，つまり、4は、1回シャッフルすると8番目に、2回シャッフルすると7番目に、3回シャッフルすると5番目に来る、という意味です。
ここで、一つ気がつきたいことがあります。(2)で
から
を引いたとき
で割り切れることを確かめました。これを応用してみます。(2)では、
からは
を引いて9で割り切れることを確かめたのですが、
に対して、シャッフルするごとに、
，
，
と、2倍ずつされて行きます。
そこで、
についても、シャッフルするごとに2倍ずつして行き、
で割ったものを考えます。
を9で割ると、
に対して、9で割った余りは、
となり、
と一致します。
を9で割ると、
に対して、9で割った余りは、
となり、
と一致します。
を9で割ると、
に対して、9で割った余りは、
となり、
と一致します。
そこで、一般的に、
のとき、mを自然数、kが
を満たす整数だとして、
を
で割った余りが
と一致すること、つまり、商を
として、 
･･･①
(Ⅰ) 
のとき、(2)より、
は、
で割り切れるので、商を
として、 ∴ 
･･･②
これは、
を
で割ると、余りが
であることを意味します。
(Ⅱ) 
のとき成り立つとします。
を
で割った余りが
と一致するので、 両辺に2をかけて、
･･･③
の場合を考えるのに当たって、この式に出てくる
を何とかしなくてはいけません。
上の
，
，
の表をよく見ると、どの欄においても、1の次には2，2の次には4，3の次には6，4の次には8，5の次には1，6の次には3，7の次には5，8の次には7が来ます。ということは、
は、
のkを
としたものに一致する(
，
，
，･･･)、ということです。つまり、言い換えると、kがl回シャッフルして
番目の位置にいたとして、次のシャッフルでどこに行くか(これが、
です)と言うと、最初に
番目の位置にいたのはkなので、kが1回シャッフルして行く位置
と同じ位置に行く、つまり、
に行く、ということです。
②のkを
に入れ替えると、 これを③に代入すると、
は整数なので、これは、
を
で割った余りが
であることを意味します。つまり、
においても成り立ちます。(Ⅰ)，(Ⅱ)より、
を
で割った余りは、
と一致します。
ここで、①において、
とすると、 ∴ 
は整数なので、これは、
を
で割った余りがkであることを意味しています。
は
を
で割った余りなので、
ですから、
です。
これは、数列
を
回シャッフルすると、
にもどることを意味します。
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
東大理系数学TOP 数学TOP TOPページに戻る
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
各問題の著作権は
出題大学に属します。©2005-2023(有)りるらる 苦学楽学塾 随時入会受付中！理系大学受験ネット塾苦学楽学塾(ご案内はこちら)ご入会は、
まず、こちらまでメールを
お送りください。 
→
→
→
より
......[答]
