算数星人さんの最上級問題①最短経路の問題をいろいろな方法で解いてみた（解説編）

■  最上級問題①最短経路   ■

算数星人さんの最上級問題①最短経路の問題をいろいろな方法で解いてみたの解説編です。

happyhappy-turn.com

（１）図のように４マス×４マスのAからBへ行くときの片道を最短距離で行く場合は何通り？

書き込み方式で解く方法と、計算で解く方法と２つあります。

計算で解く方法は、↑が4回、→が4回の組み合わせなので8C4=70通り

これは予習シリーズでもや参考書にも載っているレベルです。

では、往復だと？ 

（２）２マス×２マスのときにA⇒B⇒Aへ往復するときに同じ点を２度通らずに行く場合は何通り？（左下がA、右上がBとする）

2マス×2マスなら書いてしまう方が早いです。

というわけで↓の6通りです。

ちなみに上３つと下３つは対称的なので上３つを２倍すればいいのです。

 では、なぜ上３つだけを考えればいいかわかりますか？

それは、

Aからスタートした時に↑からスタートしたらBへ行く直前は必ず→でないとかならず往復の時に同じ点を通ってしまうのです。それはA⇒Bへ行くルートをB⇒Aへ行くときにまたがってしまうからなのです。だから往復するとぐるっと一周するような経路をたどればいいのです。

この問題を紹介したのはここがポイントだからです。

これを踏まえたうえで、書き出して解くことが大事だからです。

（３）3マス×3マスのときにA⇒B⇒Aへ往復するときに同じ点を２度通らずに行く場合は何通り？（左下がA、右上がBとする）

これは（２）の考え方を応用して、あとは書き込み法との合わせ技です。

対称性を考慮して最後に２倍します。

（6+5+3+3+2+1)×2=40通り

（４）では最上級問題の場合は何通り？

これはおまけのようなものです。

同じように場合分けをします。

へこんだ部分の数が0～9個までのパターンが考えられます。

0個：20

1個：19

2個：16,16

3個：10,14,10

4個：9,10,9

5個：7,6,7

6個：4,5,4

7個：3,3

8個：2

9個：1

これらをすべて足して２倍すると350通りになります。

では、これを計算で解くとしたら、余事象を使って考えます。

A上の点をC、Aの右の点をD、Bの左の点をE、Bの下の点をFとします。

反時計回りのADFBECAの経路を求めて２倍すれば求めることができます。

そこには（２）での考察がポイントです。

D⇒Fの経路数は「右」「上」を3回ずつ6C3=20通り

E⇒Cの経路数も同じく20通り

したがって20×20=400通り

このうちD⇒FとE⇒Cが同じ点を通る場合は禁止されます。

同じ点を通る場合、通る同じ点のうち最もAに近い点をPとして

「D→P→FとE←P←C」を「D→P→EとC←P←F」に対応させると

このような経路の組み合わせはD→EとC→Fの経路の組み合わせと対応し

D→Eは「右」２回と「上」４回を行うので6C2=15通り

C→Fも同数となってこの組み合わせは15×15=225

したがって（400-225）×2=350通り

地道な書き出し法と同じ答えになりました。