次: 問題と考え方 上: 場合分け 前: 定数の範囲で式が変わる

個数を数える場合分け

こんどは個数を数える場合分けをやってみよう． ていねいに場合分けをしていこう．

例題 1.2       ［鳥取大過去問］

ある試験において，20点満点の問題が5題出題されている． 各問いとも0点，5点，10点，15点，20点のいずれかで全部を採点するものとする．

(1)

おこりうる採点の仕方はいく通りあるか．

(2)

少なくとも3問が正解である場合はいく通りあるか．

(3)

総得点が80点以上である場合はいく通りあるか．

解答    

(1)

各問いとも5通りの採点の仕方があるから

$$5^5=3125 (通り)$$

(2)

正解の個数で場合に分けて考えよう．

5問とも正解になるのは，1（通り）

4問正解になるのは

$$［どの4問かの決め方］\times ［他の1問の採点の仕方］（通り）$$

$$∴ \quad {}_5 \mathrm{C}_4 \cdot 4=20（通り）$$

同様に3問正解になるのは

$$∴ \quad {}_5 \mathrm{C}_3 \cdot 4^2=160（通り）$$

あわせて

$$1+20+160=181（通り）$$

(3)

まずどのような場合分けが必要かを考えよう． 得点で考えるのがよいか． 減点で考えるのがよいか．

問題1〜問題5の各々から減点される点数を $5x_1,\cdots ,5x_5$ とする．

$$0 \le 5x_1+\cdots +5x_5 \le 20 \ \iff \ 0 \le x_1+\cdots +x_5 \le 4$$

となる非負の整数 $x_1,\cdots ,x_5$ の取り方の総数が求めるものである．

条件 $0 \le x_1,\cdots ,x_5 \le 4$ は $0 \le x_1+\cdots +x_5 \le 4$なら必然的に満たされる．

$$x_1+\cdots +x_5=k ,\ k=0,\cdots 4$$

のとき $x_1,\cdots ,x_5$ の取り方の総数は

$${}_{k+5-1} \mathrm{C}_4$$

それぞれの場合の計算式ができた． この場合分けはもちろん重なりがない．よって

$${}_8 \mathrm{C}_4+{}_7 \mathrm{C}_4+\cdots+{}_4 \mathrm{C}_4=126$$

となる． □

別解     工夫をすれば場合分けが必要でなくなる．

$$0 \le x_1+\cdots +x_5 \le 4$$

となる非負整数の組 $(x_1,\cdots ,x_5)$に対し $x_6=4-(x_1+\cdots +x_5)$とすると

$$x_1+\cdots +x_5+x_6 = 4$$

となる非負整数の組 $(x_1,\cdots ,x_5,\ x_6)$ が得られる．

逆に

$$x_1+\cdots +x_5+x_6 = 4$$

となる非負整数の組 $(x_1,\cdots ,x_5,\ x_6)$ から

$$0 \le x_1+\cdots +x_5 \le 4$$

となる非負整数の組 $(x_1,\cdots ,x_5)$が得らる．

よってこれらはは1対1に対応している．

$$0 \le x_1+\cdots +x_5 \le 4$$

となる非負整数の組 $(x_1,\cdots ,x_5)$と

$$x_1+\cdots +x_5+x_6 = 4$$

となる非負整数の組 $(x_1,\cdots ,x_5,\ x_6)$ は同じだけある．

$$∴ \quad {}_{4+6-1} \mathrm{C}_4=126$$

である． □

次の問題はどのような場合分けが必要かはそれほど明らかではない．

例題 1.3       ［08京大文系］

正$n$角形とその外接円を合わせた図形を$F$とする，$F$上の点Pに対して， 始点と終点がともにPであるような，図形$F$の一筆がきの経路の数を$N(\mathrm{P})$で表す． 正$n$角形の頂点をひとつとってAとし， $a=N(\mathrm{A})$とおく． また正$n$角形の辺をひとつとってその中点をBとし， $b=N(\mathrm{B})$とおく．このとき$a$と$b$を求めよ．

注：一筆がきとは，図形を，かき始めから終わりまで，筆を紙からはなさず， また同じ線上を通らずにかくことである．

考え方     このようなときは「例で考える」にしたがって， $n$の値を4や5で考えてみるのも一つの方法である． 頂点から頂点に移動するには辺と弧のいずれを先に描くかで2通り． それに気づけば， 結局頂点をどの順に動いていくかという問題だということがわかる． (2)では， 頂点間の移動が辺と弦の両方通れるときと， 一方しか通れないときがあることと， ここにも場合分けの要素がこのようにあることがわかる．

一方，$n$のときの場合の数を$a_n$や$b_n$とおいて漸化式を立て求めることもできる．．

解答     $a=N(\mathrm{A})$について． 一筆がきの経路に関する場合分けは次の様に起こる．

1. 頂点から隣りあう頂点への移動は$n$カ所あり， それぞれ移り方は辺と弧のいずれを先に通るかの2通り． したがって，頂点の間の移動の順を決めれば，それに対して経路は$2^n$通りできる．
2. 点の間の移動順では，右回りから始めるか，左回りから始めるかが場合分けされる． これは対称性からたがいに同数あるので，左回りからはじめる場合で考えその2倍ある．
3. 左回りからはじめるときで考える． 点の間の移動順では，途中で折り返さないか途中で折り返すかの場合に分けられる． 折り返さない場合は1通り． 折り返す場合．2回折り返すのはA以外で折り返すとき．Aで折り返すときは1回折り返す． したがって折り返しなしも含めて，折り返しの仕方は$n+1$通り．

これらはそれぞれ異なる一筆がきを作り，場合分けは他にはない．

$$∴\quad a=2^n\cdot 2\cdot(n+1)=(n+1)2^{n+1}$$

$b=N(\mathrm{B})$について．

点Bのある辺をCDとする．左回りにC，B，Dと並ぶものとする．

点Bに始まり点Bに終わる一つの一筆がきに対し， 左回りなら最初のBDを書くところを最後に移動することでDから始まる一筆がきで， 最後にDに戻るとき辺を通るものが得られる． 右回りなら最初のBCを書くところを最後に移動することでCから始まる一筆がきで， 最後にCに戻るとき辺を通るものが得られる． 逆にこの操作を逆にたどることで，頂点を始点とする一筆がきで最後に始点に戻るとき辺を通るものから， その辺の中点を始点とする一筆がきが得られ，これは一対一に対応している．

したがって，$b$は頂点から始まる一筆がきで， 最後に始点に戻るとき辺を通ると指定した場合の数に等しい． この条件を付け加えた頂点を始点とする一筆がきは$a$の計算で1.の部分を$2^{n-1}$としたものである．

$$∴\quad b=(n+1)2^n$$

以上である． □

別解     正$n$角形の代わりに凸な$n$角形で考えても同じことである．

$n$角形のときの$a$を$a_n$とする． $n=3$のとき， 左回りと決めると$a_3$は点の移動の順番の決め方が4通りある． 一つの順番に対し，辺と弧の選び方は$2^3$通りある． 右回りも同数． ゆえに $a_3=2\cdot4\cdot2^3=64$である．

$n$角形に新たに$n+1$番の頂点を加えると， その頂点を挟むもとの$n$角形の2頂点の間の移動の仕方が， 2通りから4通りになる． これによって$n$角形の場合の一つの一筆がきの経路に対し， $n+1$角形の場合の一筆がきの経路が2つ得られる．

さらに新たに付け加わった$n+1$番目の点で折り返す一筆がきの経路が 右回りと左回りも考えて$2\cdot2^{n+1}$個できる． ゆえに

$$a_{n+1}=2a_n+2\cdot2^{n+1}$$

これから

$$\dfrac{a_{n+1}}{2^{n+1}}=\dfrac{a_n}{2^n}+2$$

$$∴\quad \dfrac{a_n}{2^n}=\dfrac{a_3}{2^3}+2(n-3)$$

これを整理して， $a_n=(n+1)2^{n+1}$．

同様に $n$角形のときの$b$を$b_n$とする． $n=3$のとき， 左回りと決めると$b_3$も点の移動の順番の決め方は4通りある． 一つの移動の型に対し，Bのある辺は，一筆がきの最初と最後が辺を通り， 途中では弧を通ることが決まるので，$2^2$通りある． $b_3=2\cdot4\cdot2^2=32$である．

$n$角形に新たに$n+1$番の頂点を加えると， その頂点を挟むもとの$n$角形の2頂点の間の移動の仕方が， 2通りから4通りになる． これによって$n$角形の場合の一つの一筆がきの経路に対し， $n+1$角形の場合の一筆がきの経路が2つ得られる．

さらに新たに付け加わった$n+1$番目の点で折り返す一筆がきの経路が 右回りと左回りも考えて$2\cdot2^n$個できる． ゆえに

$$b_{n+1}=2b_n+2\cdot2^n$$

これから，$b_n=(n+1)2^n$． □ 次: 問題と考え方 上: 場合分け 前: 定数の範囲で式が変わる