以前の記事に関連する話です。
道順問題では最短経路を求めさせるものがほとんどですが、たまに最長経路をきく問題も出されます。
一筆書きできる図形であれば「一筆書きする方法」が最長経路になるので、一筆書きできない図形のときにこういう問いになりますが(いずれも一度通った道は通れないことが前提)考え方は一筆書きする方法とほとんど同じになります。そのため直感的に見つかる行き方の2倍や4倍が実は正解というのもよくあることで規則的に調べ上げることがカギになります。
今年の入試問題ではたとえば次のようなものが出されています。
線をたどって2つの地点を移動するときの最短経路と最長経路を考えます。ただし、一度通った線は通れないものとします。
例えば、図1で地点Pから地点Qまで移動することを考えると、図2のアは最短経路を、イは最長経路の1つを表しています。
図3で地点Aから地点Bまで移動します。このとき、次の問いに答えなさい。(普連土2023・2日午後)
⑴ 最短経路を解答欄の図に1通りだけかきなさい。また、全部で何通りあるか答えなさい。
たとえば次の経路がある。
また直線ABを対称の軸としてこれと線対称の形もやはり最短経路になるから全部で2通り
⑵ 最長経路を解答欄の図に1通りだけかきなさい。また、全部で何通りあるか答えなさい。
たとえば次の経路がある。
ひとまずこの経路を例に考える(次のようにアからオの記号をつける)
その際、アイを直径とする円と三角形イエオに注目すると、大きく次の2つのパターンを考えることとなる。
❶まず円を完成させそのあと三角形を完成させる場合
- このとき円のところはA→ア→イ→ア→イの道をたどる。このうち最初のア→イの道の選び方は3通り、イ→アの道の選び方は2通り(2回めのア→イは残った1通り)だから 3×2=6通り
- そのあと三角形のところは①イ→エ→オ→イ→ウ→Bと右回りに行くか、②イ→オ→エ→イ→ウ→Bと左回りに行くかで2通り
したがってこの場合 6×2=12通り
❷円を完成させる前に三角形を完成させる場合
- まず①A→ア→イ→エ→オ→イ→ア→イ→ウ→Bの行き方がある。このうち最初のア→イが3通り、イ→アが2通りあるから(それ以外の矢印はすべて1通りだけなので)3×2=6通り
- また②A→ア→イ→オ→エ→イ→ア→イ→ウ→Bの行き方がある。①との違いは三角形を右回りで行くか左回りで行くかだけなので、①と同じく6通り
したがってこの場合 6+6=12通り
以上のように例にあげた最長経路だけで計24通りある。
そして最長経路にはもう一つ次の形(直線ABを対称の軸として線対称のもの)もあるから、こちらも24通りあるので全部あわせて 48通り