第308問の解答
問題 [場合の数]
マサルさんはツヨシ君の家庭教師をしています。 マサルさんは、ツヨシ君が帰宅する前に部屋に行き、その日の問題を作りはじめます。問題ノルマは全部で7問で、作成順に1〜7の番号をつけ、台の上に出来た順に重ねて置いていきます。
ツヨシ君は帰宅すると部屋に入り、マサルさんが置いた問題を上から順に解きはじめます。また、ツヨシ君が問題を解いている間もマサルさんは残りの問題を(もしあれば)作り続け、出来るたびに台の上に重ねていきます。
途中の休憩の時点で、ツヨシ君は6番の問題はすでに解いていたそうです。(この時点でも問題は全部完成しているとは限りません。)
では、休憩後にツヨシ君が問題を解く順序は何通り考えられるでしょうか。
解答例1
Nonさん、小杉原 啓さん、AЯOTさん 、maruhagedonさん、ふじさきたつみさん、Taroさん、CRYING DOLPHINさん、小西孝一さん、M.Hossieさん、ねこやんさん、孫悟空さん、有無相生さん、あさみかずみさん、kokoさん、ステップ ばい ステップさん、他 多数
問題の解く順序としては、次のことが成り立ちます。
(補題)ある番号を解いた後に、それより小さい番号が複数残っているときは、大きい順に解くことになる。 (例)1、4、3、2はOK、1、4、2、3はダメ。
従って、第6問を解き終わっていることから、残る問題は第7問以外を除いて全て番号の大きい順に解くことになります。
そこで、第7問以外の問題が何問残っているかで場合分けしましょう。
5問残っているとき:残る問題の選び方5C5=1通り
・第7問を既に解いているとき・・・1通り
・第7問がまだ残っているとき・・・第7問以外は大きい順だから、第7問の解く順番によって6通り
合計=5C5×7通り同様にして、
4問残っているとき:5C4×6通り
3問残っているとき:5C3×5通り
2問残っているとき:5C2×4通り
1問残っているとき:5C1×3通り
0問残っているとき:5C0×1通り(第7問だけ残っている場合)
(第7問以外に4問残っているとき)
よって、合計=5C5×7+5C4×6+5C3×5+5C2×4+5C1×3+5C0×1
=1×7+5×6+10×5+10×4+5×3+1×1
=143通り答: 143通り
以上
解答例2
高橋 道広さん、拓パパさん、他
第7問を解き終わっているとき:
残る5問がいくつ残っているかが決まれば解く順番は番号の大きい順の一通りに決まるので、
5C5+5C4+5C3+5C2+5C1=25−1通り(解く問題なしのときを除く)
第7問が残っているとき :
・休憩後、すぐ第7問を解くとき
残る5問が決まれば解く順番は一通りなので、
5C5+5C4+5C3+5C2+5C1=25通り・休憩後、第7問以外の問題をまず解くとき :
最初に解く問題を選ぶのは5C1=5通り
残り4問のうちいくつ残っているか決まれば解く順番は一通りに決まるので、
4C4+4C3+4C2+4C1=24通り
合計=5×24通り
以上から、合計=25−1+25+5×24=31+32+80=143通りになります。(参考1)
問題が全部でn問あり、第n-1問を解き終わったあとの解く順番(Pnとします)は、上記同様に
Pn=2n-2−1+2n-2+(n-2)×2n-3=(n+2)×2n-3−1となります。解答例1からは、
Pn=n-2Cn-2×n+n-2Cn-3×(n-1)+・・・+n-2C1×3+n-2C0×2−1
となります。ここで、Fn=nCn×n+nCn-1×(n-1)+・・・+nC1×1+nC0×0とおくと、
Fn=nC0×0+nC1×1+・・・+nCn-1×(n-1)+nCn×n
=nCn×0+nCn-1×1+・・・+nC1×(n-1)+nC0×nよって、Fn×2=n×(nCn+nCn-1+・・・+nC1+nC0)=(n+1)×2n
Fn=n×2n-1従って、
Pn=n-2Cn-2×(n-2)+n-2Cn-3×(n-3)+・・・+n-2C1×1+n-2C0×0
+2×(n-2Cn-2+n-2Cn-1+・・・+n-2C1+n-2C0)−1
=Fn-2+2×2n-2−1
=(n-2)×2n-3+2×2n-2−1
=(n-2)×2n-3+4×2n-3−1
=(n+2)×2n-3−1
となり、解答例2の結果と一致します。
(参考2)
問題が全部でn問ある場合で、第n-1問を解き終わったあとという条件がない場合の解く順番
(Knとします)は、n次のカタラン数となり、Kn=2nCn/(n+1)となります。
とくに、n=7のときは、K7=14C7/8=429通りとなります。カタラン数については、既に算チャレでも何度か出題されています。
下図のようなn×nの格子上で左下の頂点から右上の頂点へ進む経路との関連を考えます。
問題を作成する⇔格子上で上に進む、
問題を解くことと⇔格子状で
すると、作成した問題数を超えて問題を解くことはありませんから、格子上で対角線よりは左上の経路に限定して進むこととなります。
従って、ちょうどn次のカタラン数になります。
上図の経路例では、
問題1、2、3を作成→問題3を解く→問題4、5を作成→問題5、4を解く→問題6を作成→問題6を解く
→問題7を作成→問題7、2、1を解く
となりますので、問題を解く順番だけで言うと、3、5、4、6、7、2、1と対応します。あるいは、Nonさんが考えられたように、漸化式
Kn=Kn-1+K1×Kn-2+K2×Kn-3+・・・+Kn-2×K1+Kn-1
からもカタラン数と一致することが得られます。