II横浜市立大学 2021年 数学 第II問解答・解説

(1) カード1,2の順序は変わらないので、5つの位置のうちカード1,2を置く2つの位置を選べば並び方が定まる。　 したがって$$\displaystyle \binom{5}{2}=10$$通りである。　 　 (2) まず$k$を固定すると、シャッフル後の並びは、各位置が左のグループまたは右のグループのどちらに属するかを表す長さ$n$の文字列で指定できる。　 この文字列には左のグループを表す記号が$k$個、右のグループを表す記号が$n-k$個あるから、その指定は$\displaystyle \binom{n}{k}$通りである。　 $k=1,2,\ldots,n-1$についての指定を合わせると、長さ$n$の二種類の記号からなる文字列のうち、すべてが左の記号またはすべてが右の記号である2通りを除いた$2^n-2$通りになる。　 異なる指定が同じカードの並び方を与えることもあるので、得られる並び方の数はこれ以下である。　 よって$2^n$通り未満である。　 　 (3)$m=\lceil n/2\rceil$とする。　 $n!$のうち、$\lfloor n/2\rfloor+1$から$n$までの$m$個の因数は、いずれも$n/2$より大きい。　 また、残りの因数はすべて1以上である。　 したがって$$\displaystyle n!>\left(\frac{n}{2}\right)^m.$$ここで$n\ge 2$より$n/2\ge1$、また$m\ge n/2$であるから$$\displaystyle \left(\frac{n}{2}\right)^m\ge\left(\frac{n}{2}\right)^{n/2}.$$ゆえに$\displaystyle \left(\frac{n}{2}\right)^{n/2}<n!$である。　 　 (4) どの時点の並びから始めても、$k$を固定した一回のシャッフルの指定は$\displaystyle \binom{130}{k}$通りである。　 したがって一回のシャッフル後に得られる並びは$$\displaystyle \sum\limits _{k=1}^{129}\binom{130}{k}=2^{130}-2<2^{130}$$通り以下である。　 この上限は各段階で共通なので、3回のシャッフルで得られる並びは$(2^{130})^3=2^{390}$通り未満である。　 一方、(3)に$n=130$を代入し、さらに$65>64=2^6$を用いると$$130!>65^{65}>64^{65}=2^{390}.$$カードの並び方全体は$130!$通りあるから、3回のシャッフルで得られない並び方が少なくとも1通り存在する。