以前の記事の続きです。
場合の数や条件整理の問題のなかで美しすぎる樹形図に出会うことがあります。
たとえばこちらの問題。
右の図のように、円周上に15個の点①、②、③、…⑮が反時計回りに順に並んでいます。
最初、①に石があります。コインを投げて表が出たら石を反時計回りに5個先の点に移動させ、裏が出たら石を時計回りに3個先の点に移動させる操作をくりかえします。
たとえば、石が⑬にあるとき、コインを投げて表が出たら石を③に移動させ、次に、裏が出たら③にある石を⑮に移動させます。このとき、次の問いに答えなさい。（栄東中2022）
⑴ コインを5回投げて、表が［ア］回、裏が［イ］回出れば、①にある石を②に移動させることができます。［ア］、［イ］に入る数をそれぞれ答えなさい。
表と裏で移動の方向が逆だが、わかりやすくこの移動の方向を合わせる。
問題文にある「表が出たら石を反時計回りに5個先の点に移動させ、裏が出たら石を時計回りに3個先の点に移動させる」を読みかえて「表が出たら石を反時計回りに5個先の点に移動させ、裏が出たら石を反時計回りに12個先の点に移動させる」ものと考える。
すると一回りするには15コ進む必要があるので、①→②の移動があるのは1コ、16コ、31コ、46コ…進んだとき。
とすると、表が2回、裏が1回出たときを（2,1）のように書くと（表がでると+5、裏がでると+12進むので）「コインを5回投げて」いちばん少ない進み方は（5,0）のときで25コ。ここから表が1つ裏に変わるごとに12－5＝7ずつ増えていくから、
（4,1）→32コ、（3,2）→39コ、（2,3）→46コ
となり（2,3）のときに①→②に移動することがわかる。
よって［ア］＝2、［イ］＝3
次に、②、③、…、⑮のうちから点を一つ選び、①にある石をコインを何回か投げてその点に移動させます。そのために必要なコインを投げる回数が最も小さい数を考え、これを最小回数と呼びます。たとえば、コインを1回だけ投げて①にある石を③に移動させることはできませんが、コインを2回投げて表と裏が1回ずつ出れば、①にある石を③に移動させることができます。つまり、③を選んだ場合には、この最小回数は2回となります。
⑵ ③のほかに、この最小回数が2回となる点を②、④、⑤、…⑮の中からすべて答えなさい。
「2回」の出方は3通りありそれぞれ調べると、表がでると+5、裏がでると+12進むから
- （2,0）…+10なので⑪へ移動
- （1,1）…+17は+2と同じなので③へ移動
- （0,2）…+24は+9と同じなので⑩へ移動
となるから、③のほかは⑩と⑪
⑶ ②、③、…、⑮のうち、この最小回数が最も大きいのは［ウ］であり、その最小回数は［エ］回です。［ウ］に入る点を②、③、…、⑮の中から選び、［エ］に入る数を答えなさい。
①からどう移動していくかを見ていくと
- ①からは（+5と+12で）⑥か⑬に進む
- ⑥からは（+5と+12で）⑪か③に進み、⑬からは③か⑩に進む
- ⑪からは…
となっており、これをまとめると次の樹形図になる。
ふつうの樹形図ならもっと広がるところ、「コインを2回投げて表と裏が1回ずつ出れば、①にある石を③に移動させることができます」と小問⑵にあるのが示すように、表→裏なら①→⑥→③のルートで、裏→表なら①→⑬→③のルートで同じ③にたどり着くため、規則的に重なる場所が出てくる美しい樹形図になるのがわかります。
*グレーはすでに登場した数字なので最小回数にはならずそこで終了
こうして最小回数を見ていくと、5回めまでに⑭以外の点にはすべて移動できるが、⑭は6回めにはじめて移動できるのがわかる。
よって ウ＝⑭、エ＝6回 
