第342問の解答
問題[場合の数]
「ジャンケンの帝王」と呼ばれるマサルさんは、「連敗などをしない」という伝説の男です。 つまり、「勝ち」の次の勝負は、「勝ち」「負け」「あいこ」のどれかになりますが、
「負け」や「あいこ」の次の勝負には必ず「勝ち」ます。あるときマサルさんが、7人の人と連続でジャンケン勝負をしました。
このときのマサルさんの勝負の勝敗表は、勝ちを◎、あいこを▲、負けを×とすると、例え ば
◎→◎→×→◎→▲→◎→◎
のようになります。では、マサルさんの勝敗表は何通り考えられるでしょうか。
解答例1
小杉原 啓さん、Toru Fukatsuさん、CRYING DOLPHINさん、るてみいなさん、フランク長いさん、ミミズクはくず耳さん、有無相生さん、M.Hossieさん、長野 美光さん、らんまさん、Banyanyanさん、kazayaさん、Taroさん、ねこやんさん、つく子さん、tomoさん、他
n回勝負したときの場合の数をFnとして、nに関する漸化式を考えます。
n=1のとき、勝、負、引分の3通り、よってF1=1。
n=2のとき、(勝、勝)、(勝、負)、(勝、引分)、(負、勝)、(引分、勝)の5通り、よってF2=5。
n≧3のとき、
最初が勝のとき ・・・ 2回目以降はFn-1通り
最初が負、引分のとき ・・・
2回目は必ず勝であり、3回目以降はFn-2通りより、
Fn=Fn-1+2Fn-2 ・・・(1)
が得られます。従って、順次
F3=F2+2F1=5+2×3=11
F4=F3+2F2=11+2×5=21
F5=F4+2F3=21+2×11=43
F6=F5+2F4=43+2×21=85
F7=F6+2F5=85+2×43=171
となりますので、7回勝負ではF7=171通りとなります。
なお、一般式は、(1)より、x2−x−2=0の根x=2、−1を用いて
Fn=a×2n-1+b×(−1)n-1
と表されます。a、bは、F1=a+b=3、F2=2a−b=5を解いて、a=8/3、b=1/3となりますので、
Fn=8/3×2n-1+1/3×(−1)n-1
となります。答: 171通り
以上
解答例2
遠い山のぽきょぽんさん、ponta55555さん、トトロ@Nさん、Banyanyanさん、大岡 敏幸さん、 他
負、引分の回数によって場合分けして数えます。
0回のとき ・・・ 7回全て勝つのは、1通り
1回のとき ・・・ 6回の勝の間(両端を含む)7個所のうち1個所が負、引 分
なので、7C1×2=14通り2回のとき ・・・ 5回の勝の間(両端を含む)6個所のうち2個所が負、引 分
なので、6C2×22=60通り3回のとき ・・・ 4回の勝の間(両端を含む)5個所のうち3個所が負、引 分
なので、5C3×23=80通り4回のとき ・・・ 3回の勝の間(両端を含む)4個所のうち4個所が負、引 分
なので、4C4×24=16通り従って、合計=1+14+60+80+16=171通りとなります。
(その他の解法)
- 樹形図等を用いて数え上げる ・・・ フィリピンの鷹さん、ゆんななこさん、いにょさん、ふじさきたつみさん、前田先生@P進学院さん、koba-shoneさん、他
- プログラムで計算 ・・・ kasamaさん、???さん、ハラギャーテイさん、 他