NEWみんなの算数講座96 囲碁のような経路数

みなさんこんにちは。ニューみん算講座96回目です。

講座に書く内容ですが、毎回けっこう思案します。ネタはいくら書いても尽きないですが、悩むのは内容よりもレベルですね。簡単な内容が多いと持てあます人が増えるだろうし、難しい内容が多いと敬遠されてしまいますからね。僕としては、算数が得意な人にも得意ではない人にも読んでほしいので、その回ごとに、レベルのメリハリをつけて書いていこうと思っています。

というわけで今回ですが、正直、場合の数の問題でレベルはやや高めです。すごく難しいというわけではないですが、珍しい問題だし、のっている本もあまりないので、知っている人は少ないでしょう。でもじっくりと呼んでもらえれば、算数の素晴らしい知恵を感じてもらえると思います。ではもったいぶらずに問題を紹介しますね。

問題の意味はおわかりになりますか？
点Ａから点Ｂまで一番早く進むには、４cmで進むことになります。３cm以下ではＡからＢに到達することはできません。
設問(1)で求めるのは４cmの場合の経路数です。下のような進み方が一例です。

経路数が何通りあるかを正直に数えるのはなかなか大変です。全部の頂点に記号をつけ、Ａ→□→□→□→Ｂのような樹形図を書いていく方法もありますが、(1)はなんとか正解できても、(2)を正解するのは大変でしょう。たいてい数え忘れが起きそうです。

じつはこの問題には素晴らしいアイデアがあります。それを解説していきますね。

考え方①　「進む長さが１cmだったら？」と考えてみる
進む長さが１cmの場合、点Ａのすぐ下にある２個の点(左下と右下)に進む経路があります。１cmではそれ以外の点に進むことはできません。スタートのＡに戻ることも１cmでは不可能です。左下と右下の点に１通りずつなので、それを次のように表しておきます。

考え方②　１cm延ばして「進む長さが２cmだったら？」と考えてみる
進む長さが２cmになると、１cmのときより一段下の点まで行けるようになります。１cmのときの「１」の点の下にある３個の点まで行けます。
そしてここで大切なのは、１cmのときの図で「１」になっている点や、スタートのＡにも、２cmで進むことができるということです。
黄緑色で示した経路は、Ａの右下の点へ２cmで進む経路です。また、出発点Ａに２cmで進む（ＡからＡに戻る）のは２通りの経路があります。Ａから左下に下がって同じ道を戻る経路、右下に下がって同じ道を戻る経路です。この問題には、一度通った道を通れない、同じ点に戻れないという条件はないので注意してください。
Ａから２cmで進める場所は下の通りです。「１」となっている点には１通りの経路があり、「２」となっている点には２通りの経路があります。

さて、もう１cm延ばして進む長さを３cmにすると、だいぶ話が見えてくると思います。

考え方③　さらに１cm延ばして「進む長さが３cmだったら？」と考えてみる
今度は進む長さが３cmです。２cmのときより、もう一段下の点まで行けるようになります。３cmで到達できない点は、一番下の線上にある５個の点だけです。それ以外の点はすべて３cmあれば到達可能です。
では３cmで進める各点への経路数を示してみます。

３cmの図を見て、もし次のことに気づいた人がいたら素晴らしく優秀です。
３cmのときの各点への経路数は、２cmのとき、その点から１cm離れていた点の経路数の合計です。
（右側に２cmのときの図をもう一度入れます）

具体例でいきましょう。３cmの図で赤で示した「６」は、２cmの図でその点と１cm離れていた各点の経路数の合計です。
６(←３cmの図)＝２＋１＋２＋１（←２cmの図）

理由を説明すると、３cmで「ある点」に到達するためには、２cmのときにその隣の点にいないとならないでしょう？だから３cmのときの６は、２cmのときに隣にあった数の合計２＋１＋２＋１で求めることができるわけです。
ひとつ前の図にさかのぼって考えるというナルホドの考え方ですね。

これで設問(1)の解答は手中です。
Ｂまで４cmで進む経路数は、３cmのとき、点Ｂのとなりにある経路数の合計です。３cmのときＢのとなりにあるのは左上と右上にある「３」と「３」です。
(1)の解答は３＋３＝６通りです。

次は設問(2)のＢまで５cmの経路ですが、それを考えるには４cmのときの経路数を示しておく必要がありそうです。４cmのときの経路数は次のようになります。どの点も３cmの図でとなりにあった数字をたしています。４cmのときの経路図があれば、Ｂまで５cmの経路数は簡単です。

５cmでＢに進む経路数は、この図で点Ｂと隣り合っている点の数をすべて加えます。11＋11＋４＋４＝30ですね。(2)の解答は30通りです。
この図の各点でとなりの数をたせば５cmの図もできますが、５cmの図は省略させてもらいますね。この問題が理解できたみなさんは、ぜひ５cmの図も作ってみてください。

＊＊＊
いかがでしたでしょうか。この考え方を自力で思いつける人は相当の才能の人だと思うし、解説している僕自身もむかし誰かから教わりました。
そのとき僕は、この話は囲碁に似てるナと思いました。囲碁を知らない人もいると思いますが、囲碁では右のイラストのように、まわりを黒石で囲まれた白石は取られてしまいます。ある点の経路数を求めるとき、その点自身（白石）を除き、となりの数（黒石）をたす作業が、なんとなく囲碁に思えたのです。それで今回のタイトルを「囲碁のような経路数」にしました。このタイトルでみなさんの記憶にも残ればうれしいです。

では今回の講座はここまでにします。次回97回目の講座を楽しみに待っていてください。次回は久しぶりにベン図を使った集合の話を予定しています。

インフォメーションボード

〈算数の家庭教師のご相談・ご依頼・体験授業〉
こちらの説明ページをお読みいただき、ページ内のフォームからご連絡をお願いします。

〈お仕事関係のご連絡〉
こちらの連絡用フォームからお願いします。

〈算数講座へのご意見や質問／ウタマル先生へのお便り〉
こちらのフォームからどうぞお寄せください。

〈全講座カラー印刷ファイル〉
おかげさまでとてもよく売れています。どうもありがとうございます。印刷屋さんの協力で、５講座ずつを１冊子にまとめ、「なかとじ印刷」した片側Ａ５サイズ（開くとＡ４）のコンパクト版です。内容やご注文方法は、ご案内ページをご覧ください。
ご案内ページこちら