2012年東北大入試理系数学第3問その2

どもども。


今回は前回の続きで，今年の東北大入試理系数学第３問をやっていきます

問題はこちら


前回：http://blog.goo.ne.jp/mathnegi/e/c13fe45fc9902b87c3a81f77616d743f

（２）からやっていきますよ～
１～３の数字が書かれた３枚のカードが袋Ａ，Ｂにそれぞれ入っていて
この２つの袋から１枚ずつカードを取り出すわけですね
そんで，取り出したのが同じ数字のカードだったらそれを除いて，違う数字だったらまた袋に戻す，と。

n回目の操作で初めて同じ数字のカードを引く確率がp_nです。
n回目の操作で全てのカードを引き出し終える確率がq_nです。
これらを求めなさい，という問題です


まずはp_nについて考えていきましょう～

n回目で初めて同じ数字のカードを引く，ということは
n-1回目までの操作ではずーーっと異なる数字のカードを引いていた，ということになります

１回の操作で２つの袋から異なる数字のカードを引き出す確率は，
Ａの袋から引いた数字に対してＢが残り２つの数字のカードのどちらかを引く
事象を考えて2/3になります
あるいはＡ，Ｂから引いた数字a，bの組が(a,b)が全部で３×３＝９通り，
そのうち(1,2)，(1,3)，(2,1)，(2,3)，(3,1)，(3,2)の６通りがあるので2/3としてもＯＫ

同様に１回の操作で（初めて）同じ数字のカードを引き当てる確率は1/3です。

確率2/3で違う数字のカードを引く操作をn-1回繰り返した後，n回目で確率1/3で同じ数字のカードを引くことを考えてp_nを求めます。



今度は順列を使ってp_nを求めてみます。

ｋ回目の操作でＡ，Ｂから引いたカードの数字をa_k，b_kとおいて
(a_1，a_2，…，a_n，b_1，b_2，…，b_n)の組を考えます
その総数は３^k×３^k通りです。

そのうちa_k≠b_k (1≦k≦n-1)を満たすものは，(a_k,b_k)をセットで考えて
各ｋにつき６通りあり，また(a_n,b_n)は３通りなので，
全部で６^(n-1)×３通りあります




次は，確率漸化式を使ってみます
１回目の操作で同じ数字を引くか引かないかで状況を分けたとき，
もし同じ数字のカードを引いたなら，そこで終了
もし違う数字のカードを引いたなら，２回目の操作を基点としてn回目に初めて同じ数字のカードを引く確率はp_{n-1}です。
これによって漸化式が立てられます




次はq_nについて考えます
p_nと同じ解法順に解いてみます。まずは純粋に確率計算。

そもそもとして，１回目，２回目の操作を終えた時点では全てのカードを引き終えることはできません




n≧3の場合について考えましょう。
ｋ回目の操作で初めて同じカードを引くと仮定しましょう。すると，ｋ回目までの確率はp_kで与えられますね

その後，k+1回目からn-2回目までは残り2枚ずつ入った袋からそれぞれ別の数字のカードを引き続けます。
n-1回目で2度目の数字一致が起きて，そうすると自動的にn回目で最後の数字一致が起き，終了です

これによって「ｋ回目の操作で初めて同じカードを引く」かつ「n回の操作で終了」の確率が求められます。



ｋが１からn-2の場合まで全て考えて確率を足し合わせれば答えが得られます





次は場合の数を求めるパターンです
さっきと同様に(a_1，a_2，…，a_n，b_1，b_2，…，b_n)の組を考えますが，
その総数は安易に３^k×３^k通りとしてはいけません

ｋ回目の操作で初めて同じ数字のカードを引くとすると，ｋ＋１回目以降はn-1回目まで，
Ａ，Ｂから出すカードは各2通りになります。

そこで，「ｋ回目の操作で初めて同じ数字のカードを引く」かつ「n回の操作で終了」の確率を求める方針でいきます








最後は漸化式を使ってみましょう
発想はp_nのときと同じ。1回目の操作で同じ数字のカードを引くか引かないかで分別します。

2012年東北大入試理系数学第3問その１

どもども。

今回は今年の東北大入試理系数学の第３問をやっていきます～

問題はこちら


なんだか長くて読むのがかったるい確率の問題です

（１）は，１～４の数字が書かれたカードが入った袋ＡとＢからカードを１枚ずつ取り出して
同じ数字のカードを引いた回数をＸとしなさい，Ｘ＝１，２，３，４となる確率は？
と聞いています。

自分の頭の中では袋Ａ，ＢではなくてＡさんＢさんになっていたようです
だから記述の仕方が微妙に変ッ
この際なので，ＡさんＢさんということで話を進めましょう～

ではまずは，ごくごく単純に，Ａが引いたカードの数字を順にa_k (1≦k≦4)，
Ｂが引いたカードの数字を順にb_k (1≦k≦4)とおくことにします



(a_1，a_2，a_3，a_4)の組は４！＝２４通りありますが，
そのうちの１つに固定して考えてみます
(b_1，b_2，b_3，b_4)の組を考えたときに，a_k＝b_kとなっているkの個数がＸですね

Ｎ＝４くらいですと，何も考えず樹形図を描いて考えるのも悪くないです
Ｘ＝１のときは，(b_1，b_2，b_3，b_4)＝(a_1，a_3，a_4，a_2)のような，
１個のkだけa_k＝b_kが成り立っているような組を見つけ出せばOKです
どのような(a_1，a_2，a_3，a_4)の組に対しても同じ樹形図が得られます。
なので最後に２４倍すればいいですな



数え漏れを防ぐためには，始めに２４通りすべての(b_1，b_2，b_3，b_4)の可能性を樹形図に描き出して，
その中からＸ＝１となるものに印をつけていく，というのも有効です。
そこで描いた樹形図をＸ＝２，３，４の場合を考えるときにも利用できますから便利です



この６通りなんかは数え漏れしやすそうです



よくよく考えればそりゃそうね～って感じですがＸ＝３となることはありえません




それにしても，Ｘ＝１，２，４で，確率を求める式の最初の1/24と最後の×２４というのが気になりますね。
相殺されてなくなる運命の項ですが，
もしかして何か無駄なことをやっているんでしょうか
後でその点について考えてみましょう

樹形図を使わずに今の方針で解いてみたいと思います
基本的に樹形図を使って解くというのは，手間がかかってめんどくさい！
という気持ちがありますし，Ｎが大きかったらますます大変です。

どのｋについてa_k＝b_kが成り立つか
そのときのa_k（＝b_k）の数字は何か
そのときの残りのカードの並び方の可能性は幾つあるか

の観点に基づいて計算します
(a_1，a_2，a_3，a_4，b_1，b_2，b_3，b_4)の組は全体で４！４！通り。
各Ｘ＝ｋに対して条件を満たす(a_1，a_2，a_3，a_4，b_1，b_2，b_3，b_4)の組の個数を求めましょう






さて，次はさっきのなんとなく無駄っぽい２４の相殺について考えてみます

最初の解答で，確率の計算式に出てきた×２４，これは何を示すものだったでしょうか。
はじめに(a_1，a_2，a_3，a_4)の組を固定して考察したので，
２４個全体分をカウントするために２４倍したのでしたね

この考え方は(a_1，a_2，a_3，a_4)と(b_1，b_2，b_3，b_4)，両方が変動するという見方をしています
見方を変えて，(b_1，b_2，b_3，b_4)だけが動くという考え方をしてみます

Ａさんの持ってる１～４の数字が書かれたカード。
各カードにＢさんの持ってるカードのどれか１枚をランダムに対応させる。
こういう状況を考えてみましょう

対応の決め方は色々考えられます。
Ｂの袋からランダムにカードを１枚ずつ引いて，取り出した順にＡの１～４のカードに対応させる。
例えばそういうやり方もあるでしょう

今回の，２つの袋から１枚ずつカード引いてペアを作る，という操作もまた
ランダムにＡの１～４のカードとＢの１～４のカードを１枚ずつ対応させる操作になっています

従って，Ａさんの持つｋの数字の書かれたカードに対応するＢのカードの数字をx_kとおくと，
x_k=kとなるようなｋの個数がＸになるわけです

(x_1，x_2，x_3，x_4)の組は全部で４！通りです。



(a_1，a_2，a_3，a_4)にあたる部分が変動しないので計算式が簡単になりました




ここで，X=0の場合について一言添えておきます
X=0とはすなわち，どのｋに対してもx_k≠ｋとなっているということです。

Wikipedia等からの抜粋ですが，
整数 1, 2, 3, …, n を要素とする順列において，i 番目 (i ≦ n) が i でない順列を完全順列といい，
その総数をモンモール数 (Montmort number) という。
これはフランスの数学者モンモールにちなんで名づけられた。1708年モンモールによりn = 13 の場合の問題として提唱された。
一般のnの場合はオイラーによって解決された。

完全順列を求めるような問題をモンモールの問題などと呼んだりします

興味のある方は調べてみてはどうでしょう



あ，(１)はXの期待値も求めなきゃいけないんですね。
では最後にそれを求めてフィニッシュです