東大理系数学'25年前期[5]
nを2以上の整数とする。1からnまでの数字が書かれた札が各1枚ずつ合計n枚あり、横一列におかれている。1以上
以下の整数i に対して、次の操作(
)を考える。
(
) 左からi 番目の札の数字が、左から
番目の札の数字よりも大きければ、これら2枚の札の位置を入れかえる。そうでなければ、札の位置を変えない。 最初の位置において札は左から
，
，･･･，
であったとする。この状態から
回の操作
，
，･･･，
を順に行った後、続けて
回の操作
，･･･，
，
を順に行ったところ、札の数字は左から1，2，･･･，nと小さい順に並んだ。以下の問いに答えよ。
(1) 
と
のうち少なくとも一方は2以下であることを示せ。
(2) 最初の状態としてありうる札の数字の並び方
，
，･･･，
の総数を
とする。nが4以上の整数であるとき、
を
と
を用いて表せ。
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
解答 場合の数の問題なのですが、2002年の[6]を思い出させる論証の難しい問題です。まともでは厳しいので、実戦的には完璧な論証を目指さずに、以下のように、
，
，
の場合を調べ、そこから類推するようなまとめ方がよいと思います。
回の操作
，
，･･･，
を順に行った後、続けて
回の操作
，･･･，
，
を順に行う一連の操作を操作(＊)と呼ぶことにします。
の場合、
よって、全ての
，
の並び方(2通り)について、操作(＊)によって、札の数字は、1，2と小さい順に並びます。
･･･①
の場合、
よって、全ての
，
，
の並び方(
通り)について、操作(＊)によって、札の数字は、1，2，3と小さい順に並びます。
･･･②
の場合、
と
がともに3以上の場合、全ての
，
，
の並び方は、
通りあります。そのうち以上の4通りでは、操作(＊)によって、札の数字は、小さい順に並ばないので、
･･･③
最初に左から1番目か2番目にいた3が、操作(＊)後に左から2番目に残ってしまうので、小さい順に並ばないことに注意します。
(1) 
の場合は、上記の通り、
，
のうち少なくとも一方は2以下であり、操作(＊)によって数字は小さい順に並びます。 
の場合、
のとき、最初の
の後、
は一番左に残ります。
～
，
～
の後、2度目の
で、仮に左から2番目の位置に
よりも小さい数字が来ても、3以上の
が左から2番目に残ります。左から2番目の位置に
よりも大きい数字が来れば、3以上の
が一番左に残ります。いずれにしても、操作(＊)によって、札の数字は、小さい順に並びません。
のとき、最初の
の後、
が一番左に残ります。
～
，
～
の後、2度目の
で仮に左から2番目の位置に
よりも小さい数字が来ても、3以上の
が左から2番目の位置に残ります。左から2番目の位置に
よりも大きい数字が来れば、3以上の
が一番左に残ります。いずれにしても、操作(＊)によって、札の数字は、小さい順に並びません。
以上より、
と
のうち少なくとも一方は2以下です。
(2) 
の場合で考えてみます。(1)より、題意の操作によって札が小さい順に並ぶためには、
と
のうち少なくとも一方は2以下なので、
の場合，
の場合，
の場合、
の場合を考えます。 
の場合、
，
，
の3枚が小さい順に並ぶのが
。
の場合、
で
と
が入れ替わると、
の場合と同様に
。
の場合も、
。
の場合も、
。
これらの間には重複があります。
，
の場合、
，
の2枚が小さい順に並ぶのが
通り、
，
の場合も同様に
通り。
これより、
通りになります。
(i) 
の場合、
，･･･，
の
枚が操作(＊)によって、札が小さい順に並ぶのは
通りあり、この
通りの全てで、操作(＊)によって札が小さい順に並びます。 (ii) 
の場合、
なので最初の
で
と
が入れ替わり、入れ替わると(i)と全く同じ状況になるので、
を除く
枚が操作(＊)によって、札が小さい順に並ぶのは
通りあり、この
通りの全てで、操作(＊)によって札が小さい順に並びます。 (iii) 
の場合、
のときには最初の
で
と
が入れ替わりますが、ここで入れ替えずに、2度目の
で入れ替えても1が先頭に来ます。
の場合を含め、2度目の
までに、
，･･･，
の
枚が操作(＊)によって、2を除く札が小さい順に並ぶのは
通りあり、
～
のどこに1があっても、
回の操作
～
を行った後の
回の操作
～
で1が先頭に来ます。従って、
通りの全てで、操作(＊)によって札が小さい順に並びます。 (iv) 
の場合、
で
と
が入れ替わる場合を含めて、
を除く
枚が操作(＊)によって、2を除く札が小さい順に並ぶのは
通りあり、
～
のどこに1があっても、
回の操作
～
を行った後の
回の操作
～
で1が先頭に来ます。従って、
通りの全てで、操作(＊)によって札が小さい順に並びます。 上記で、(i)と(ii)は同時には起こりません。(iii)と(iv)も同時には起こりません。ですが、「(i)または(ii)」と「(iii)または(iv)」には重複があります。
，
の場合、及び、
，
の場合です。 (v) 
，
の場合、
，･･･，
の
枚が操作(＊)によって、札が小さい順に並ぶのは
通りあり、この
通りの全てで、操作(＊)によって札が小さい順に並びます。 (vi) 
，
の場合、
で
と
が入れ替わり、入れ替わると(v)と全く同じ状況になるので、
，･･･，
の
枚が操作(＊)によって、札が小さい順に並ぶのは
通りあり、この
通りの全てで、操作(＊)によって札が小さい順に並びます。 以上より、(i)＋(ii)＋(iii)＋(iv)－(v)－(vi)により、
......[答]
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
東大理系数学TOP 数学TOP TOPページに戻る
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
各問題の著作権は
出題大学に属します。©2005-2025(有)りるらる 苦学楽学塾 随時入会受付中！理系大学受験ネット塾苦学楽学塾(ご案内はこちら)ご入会は、
まず、こちらまでメールを
お送りください。 
