Evolton

東北大学 1996年度 後期日程 第2次学力試験理系(後期)数学 第3問

下の図のように、道路が碁盤の目のようになった街がある。
地点 A から地点 B まで長さが最短の道を行くとき、次の場合は何通りの道順があるか。

問題の図

(1) 地点 C を通る。

(2) 地点 P は通らない。

(3) 地点 P および地点 Q は通らない。

難易度5/ 10計算量4/ 10目安15分

場合の数 数え上げ、余事象、包除原理

方針

図から格子を座標化する。A=(0,0)、B=(5,6)、C=(1,2) であり、点 P は横道路の途中、すなわち (2,3) から (3,3) への1歩の上にある。同様に Q は (3,4) から (4,4) への1歩の上にある。最短経路は右5回、上6回なので、通過条件は必要な部分経路の積、通らない条件は余事象と包除で数える。

解答

図より、A を (0,0)、B を (5,6) とみなす。最短経路では、右へ5回、上へ6回進むだけであるから、全体の道順は 11C5=462 通りである。

(1)
図より C=(1,2) である。A から C までは右へ1回、上へ2回なので 3C1=3 通りである。C から B までは右へ4回、上へ4回なので 8C4=70 通りである。したがって、C を通る道順は 3⋅70=210 通りである。

(2)
点 P は交差点ではなく、横道路の途中にある。図から、P を通るためには、(2,3) から (3,3) へ右に進む1歩を通らなければならない。 A から (2,3) までは右へ2回、上へ3回なので 5C2=10 通りである。その後、(2,3) から (3,3) への1歩は固定される。さらに (3,3) から B=(5,6) までは右へ2回、上へ3回なので 5C2=10 通りである。したがって、P を通る道順は 10⋅1⋅10=100 通りである。よって P を通らない道順は 462−100=362 通りである。

(3)
同様に、Q を通るためには、(3,4) から (4,4) へ右に進む1歩を通る必要がある。A から (3,4) までは右へ3回、上へ4回なので 7C3=35 通りである。その後の1歩は固定され、(4,4) から B までは右へ1回、上へ2回なので 3C1=3 通りである。したがって Q を通る道順は 35⋅1⋅3=105 通りである。

次に、P と Q の両方を通る道順を数える。A から (2,3) までは10通り、P を通る1歩は固定、(3,3) から (3,4) までは上へ1歩だけ、Q を通る1歩も固定、(4,4) から B までは3通りである。よって両方を通る道順は 10⋅1⋅1⋅1⋅3=30 通りである。

包除原理より、P も Q も通らない道順は 462−100−105+30=287 通りである。

別解

解法2

方針

格子点までの最短経路数を動的計画法で数える。各格子点の値を左と下の和にし、P、Q に当たる横辺だけ遷移を禁止すれば、余事象や包除を使わず直接答えを得られる。

解答

A=(0,0)、B=(5,6) とし、格子点 (i,j) までの許された最短経路数を N(i,j) とする。通常はN(i,j)=N(i−1,j)+N(i,j−1),N(0,0)=1である。

(1)
C=(1,2) を通る経路は、A から C と C から B を独立に選べるので3C1⋅8C4=3⋅70=210.(2)
P は辺 (2,3)→(3,3) 上にある。この辺を禁止し、(3,3) の更新時だけ左からの項 N(2,3) を加えずに漸化式を進めるとN(5,6)=362.(3)
さらに Q のある辺 (3,4)→(4,4) も禁止する。各行を j=6 から j=0 の順に並べた計算表はj\i01234561728741452875162146711424151525257131410102546213610152111234560111111となる。したがって287通りである。

総評

難度5、計算量4。P,Q は格子点ではなく横道路の途中にあるため、特定の1辺を通る条件として数える。包除と辺を禁止する動的計画法が同じ362、287を与える。 2解法の最終値を照合し、境界条件・符号・定義域も確認した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東北大の場合の数の問題で問題集を作る

出典: 東北大学 1996年度 後期日程 理系 第3問。問題文はHTML表示のために再入力・数式組版しています。