冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

中学受験算数 通れない交差点の最短経路—交点の数を零にしてその先を足し直す|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

右と上に進む格子で、0から足し直して道順を数える対象は、通れない交差点です。

よくあるのは、通れない交差点に印を付けたのに、その交差点を通って来た道順も次の交差点へ足してしまう小5の場面です。印の先にある数が、通行止めのないときと同じなら、どこかで通れない道順が戻ってきたかもしれません。交差点に書く数が何を表すかを決め、禁止の印を付けた点から先へ、その数をどう伝えるかを追ってみましょう。

印のある点をどう扱うか

道は格子状に並び、交差点と交差点の間を1区間とします。横と縦の区間数が決まった長方形の左下から右上へ、右または上に1区間ずつ進みます。左や下には戻れません。右と上だけで進む道順は、必要な横と縦の区間をそれぞれ1回ずつ進むため、どれも最短です。曲がる場所が違えば別の道順として数えます。

まず、禁止の交差点がない場合です。ある交差点に着くには、そのすぐ左から右へ来るか、すぐ下から上へ来ます。左から来た道順と下から来た道順は最後の1区間が違い、重なりません。そこで、それぞれの点までの道順の数を足して、今の点までの数にできます。端の点は、存在する側からだけ数を受け取ります。

次に、長方形の内側の交差点が1か所通れない場合です。その点に着くこと自体が許されないので、そこまでの道順は0通りとします。通れない点の左や下に数があっても、禁止点では足しません。禁止点のすぐ右とすぐ上は、もう一方から来られるなら使えます。禁止点の数を0として、その先の点を改めて足すことが大切です。

もう一つの出方は、禁止点を通る道順を全体から除く問いです。禁止がないときの全道順を数え、そのうち禁止点を通る道順を引きます。足し上げと同じ答えになるはずですが、引く数を作るときは、禁止点までの道順と、そこから終点までの道順を組にする必要があります。両方の数をただ足すのではありません。

交差点に書く数の意味

出発点を S、終点を G、通れない点を P とします。図1の格子は横3区間、縦2区間です。交差点の数は横4個、縦3個です。区間の数と交差点の数は1つ違うので、図を写すときは区間を指で数えてから点を数えます。

図1 通れない交差点と左右上下の位置関係

図1の赤い丸が P です。赤い丸の位置には入れませんが、そこにつながる線そのものを1本だけ通れないと言っているわけではありません。たとえば P の右隣の点には、下の点から上へ進んで着くことができます。P の上隣の点にも左から着けるので、P の右や上にある点をまとめて消してはいけません。

交差点に書くのは「S から、禁止点を通らずに、その交差点へ着く道順の数」です。S はまだ1区間も進んでいない状態を1通りとし、1を書きます。そこからどの道も選んでいない状態が1つあるので、最初の1を土台に数を伝えられます。0と書くと、出発した道順がないことになってしまいます。

右と上にしか進めないため、交差点へ入る最後の向きは左からか下からの2つに限られます。左から着く道順の末尾の1区間を消すと、そのすべてが左の点までの道順に戻ります。逆に左の点までの道順に右向きの1区間を加えれば、左から来る道順を1つずつ作れます。下から来る場合も同じです。この対応があるので、前の2点の数を足すと漏れや重なりがありません。

ただし P は例外です。左や下から P へ入る道順は条件に合わないので、P 自身に0を書きます。P に普通の足し算をした後で、最後に答えからその数だけを引いても直せません。その数は P までの道順であって、P から G までの進み方が複数ある場合、終点までの禁止された道順の数とは異なるからです。

基本例題:0から先へ伝える〈標準〉

横3区間、縦2区間の格子があります。左下の S から右上の G まで、右か上へ1区間ずつ進みます。S から右へ1区間、上へ1区間の交差点 P は通れません。最短の道順は何通りですか。

図2では、点の右下に、その点までの道順の数を示しています。P の0は、そこへ入らないという条件を表します。左下の S から順に、下の段、真ん中の段、上の段へと計算します。

図2 横3縦2の格子で禁止点を避けた到達数

下の段では上から降りて来られず、左からだけ進みます。S の1がそのまま伝わるので、右へ並ぶ4点は左から1、1、1、1です。左端の列も下からだけ進むため、下から1、1、1です。

真ん中の段の P は、左が1、下が1でも0です。その右隣は左の0と下の1を足して1です。さらに右は左の1と下の1を足して2です。上の段では P の真上が左の1と下の0を足して1です。その右は1と1で2、G は2と2で4になります。

P の右隣  0 + 1 = 1
真ん中の段の右端  1 + 1 = 2
P の真上  1 + 0 = 1
上の段の右から2番目  1 + 1 = 2
G  2 + 2 = 4

したがって答えは4通りです。最後に足した2つの2は、G へ左から入る道順と下から入る道順です。最後の区間が違うため、同じ道順を両方に入れていません。

実際に、右を「右」、上を「上」として並べると、条件に合うのは「右右右上上」「右右上右上」「右右上上右」「上上右右右」です。どれも右3回、上2回で、途中に P を含みません。最初に右と上を1回ずつ使った道順は、順番がどちらでも P に着くため除かれます。上の4つは、その場合を除いて残るすべてです。

少し広い格子で足し直す〈やや難〉

横4区間、縦3区間の格子を、左下の S から右上の G まで右か上へ進みます。S から右へ2区間、上へ1区間の交差点 P は通れません。最短の道順は何通りですか。

下の段は左から1、1、1、1、1です。左端の列も下から上まで1です。下から2段目で、P の左は1 + 1 = 2ですが、P は0にします。P の右は0 + 1 = 1、その右は1 + 1 = 2です。

次の段は左端から1、3、3、4、6です。最初の3は左の1と下の2を足し、次の3は左の3と P の0を足した数です。その右の4は3 + 1、一番右の6は4 + 2です。さらに上の段を左から計算すると、1、4、7、11、17となります。

上の段の左から2番目  1 + 3 = 4
その右  4 + 3 = 7
その右  7 + 4 = 11
G  11 + 6 = 17

答えは17通りです。P を0にする前に書いた数を使い回さず、P より右や上の数を順に作り直しています。特に P の真上の数は、P 以外の方向から来る3通りを残すので0ではありません。

別の方法でも確かめます。禁止がなければ、格子の足し上げで G までは35通りです。P までは右2回と上1回の順を選び、3通りです。P から G までは右2回と上2回の順を選び、6通りです。前半の1通りに対して後半の6通りをそれぞれつなげられるので、P を通る道順は3 × 6 = 18通りです。右と上だけなら一度 P を通った後で P に戻れず、各道順の分け目は1つに決まります。

禁止のない道順  35通り
P を通る道順  3 × 6 = 18通り
残る道順  35 - 18 = 17通り

引いた18通りは P を通るもの、残した17通りは P を通らないものです。両者は重ならず、禁止のない道順のすべてを分けています。P までの3と P からの6を足すと、前半だけや後半だけの数になり、S から G までつながった道順を数えたことにはなりません。

禁止点が上寄りにあるとき〈難〉

横4区間、縦4区間の格子を、左下の S から右上の G まで右か上へ進みます。S から右へ1区間、上へ3区間の交差点 P は通れません。最短の道順は何通りですか。

禁止点が左端に近くても、左端の列は通れます。下から順に到達数を並べると、左端と下端はすべて1です。下から2段目は左から1、2、3、4、5、次の段は1、3、6、10、15です。次の段では、左端の1に続く P を0とし、残りを左から作ります。

P  0
P の右  0 + 6 = 6
その右  6 + 10 = 16
右端  16 + 15 = 31
最上段の左から2番目  1 + 0 = 1
その右  1 + 6 = 7
その右  7 + 16 = 23
G  23 + 31 = 54

答えは54通りです。P の上にある点にも、左端を上ってから右に進む1通りがあります。禁止点の真上だからといって、必ず到達数が0になるとは限りません。数が0になるのは、許された入口の両方から0しか来ない場合です。

引き算でも一致します。禁止がない格子の G には70通りあります。P までは右1回と上3回の順で4通り、P から G までは右3回と上1回の順で4通りです。P を通る道順は4 × 4 = 16通りなので、70 − 16 = 54通りです。P を通る16通りを1つずつ除くと、実際に P に入らず G に着く道順が残ります。

誤った数をどこで止めるか

基本例題で、P に左の1と下の1を足して2を書き、その2を次の点にも伝えると、P の右は3、真上も3になります。禁止がないときの数を使い続けると、G に10を書いてしまいます。しかし10通りの中には、たとえば「右上右右上」が含まれます。最初の右と上で P に着くので、条件を満たしません。

図3 禁止点を0にして右と上へ数を伝える比較

図3の左は P に2を残した誤り、右は P を0にした直し方です。図の矢印は、P の右隣に数が伝わる向きを表します。誤りでは P の2と下の1で右隣が3になります。直した場合は P の0と下の1で1になります。右隣の点自体を消すのではなく、禁止点から来る分だけをなくします。

禁止点の周りをすべて通行止めにすることも別の誤りです。P の右隣には下から来る道順が1通りあり、P の真上には左から来る道順が1通りあります。点への立ち入り禁止と、道の1区間だけが通れない条件では、どこに着けるかが違います。印が点に付いているか、線に付いているかを問題文と図の両方で確かめます。

最後に P の数だけを引く誤りにも気を付けます。基本例題では禁止がなければ P に2通りで着きますが、その後 G へ進む方法は3通りあります。P を通る完成した道順は2 × 3 = 6通りです。全体の10から2だけを引くと、P を通ったまま G に着く道順が残ってしまいます。

練習:通れない点を避ける

どの問題も、長方形の格子の左下を S、右上を G とします。右か上へ1区間ずつ進み、指定された内側の交差点 P は通れません。最短の道順が何通りかを答えてください。P の位置は、S から右へ何区間、上へ何区間かで指定します。

  1. 花壇の周りの格子は横2区間、縦3区間です。P は右1区間、上2区間の位置です。
  2. 校庭に引いた格子は横4区間、縦2区間です。P は右3区間、上1区間の位置です。
  3. 紙に描いた格子は横3区間、縦3区間です。P は右1区間、上1区間の位置です。
  4. 展示場所を結ぶ格子は横5区間、縦2区間です。P は右2区間、上1区間の位置です。
  5. 模型の格子は横2区間、縦2区間です。P は右1区間、上1区間の位置です。

練習の答えと道筋

  1. 4通りです。下から2段目は左から1、2、3です。その上の段では左から1、0、3、最上段は1、1、4となります。P の右隣の3は、下の3から来る道順です。別に確かめると全体は10通り、P を通るものは3 × 2 = 6通りで、10 − 6 = 4通りです。

  2. 7通りです。下から2段目は左から1、2、3、0、1です。最上段は左から1、3、6、6、7です。P の真上にある6は、左から伝わった数です。全体15通りのうち P を通る4 × 2 = 8通りを除いても、15 − 8 = 7通りです。

  3. 8通りです。下から2段目は1、0、1、2、次の段は1、1、2、4、最上段は1、2、4、8です。P から先を一段ずつ足し直して G に8を書きます。全体20通りから P を通る2 × 6 = 12通りを除くと8通りです。

  4. 9通りです。下から2段目は左から1、2、0、1、2、3、最上段は1、3、3、4、6、9です。P の右隣は下から来る1通りを残します。全体21通りのうち P を通る3 × 4 = 12通りを除き、21 − 12 = 9通りです。

  5. 2通りです。下から2段目は1、0、1、最上段は1、1、2となります。実際に残る道順は「右右上上」と「上上右右」です。右と上を最初の2回で1回ずつ使うと P に着きます。全体6通りから P を通る2 × 2 = 4通りを除いても2通りです。

覚えておくこと

出発点には1、通れない交差点には0を書きます。
それ以外の点には左と下から来る道順の数を足します。
禁止点の右や上も、別の方向から来られる場合があります。
全体から除くときは、禁止点までとその先の道順を組にします。

どの数が届いたかを説明する

個別に確かめるときは、まず P の0が何を表すかを、自分の言葉で説明してみましょう。左と下に数があるのに P で足さない理由を言えれば、印を単なる飾りではなく、入れない点として読めています。次に P の右隣を指し、左からは何通り、下からは何通り来るかを別々にたずねます。右隣を0にした場合は、下からの1通りを実際にたどってみます。

G の数だけが合っていても、途中に禁止点を通る道順を混ぜていないとは限りません。途中の1つの数を選び、それを左と下のどちらから受け取ったか、最後の区間まで戻って説明します。道順の数は、入れる点と入れない点を区別して伝えると、終点まで条件を保てます。

集団塾で沈んだ子を、ここから浮上させます。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問