Evolton

九州大学 2008年度 後期日程 第2次学力試験理系(後期)数学 第2問

右の図1と図2は碁盤の目状の道路とし,すべて等間隔であるとする。

問題の図

道路は格子線上にあり,図2では橙色の斜線側へ入れない。

以下の問いに答えよ。

(1) 図1において,点Aから点Bに行く最短経路は全部で何通りあるか求めよ。

(2) 図1において,点Aから点Bに行く最短経路で,
点Cと点Dのどちらも通らないものは全部で何通りあるか求めよ。

(3) 図2において,点Aから点Bに行く最短経路は全部で何通りあるか求めよ。
ただし斜線の部分は通れないものとする。

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

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

方針

図1・図2の位置関係を読み取り,図1は A から B まで横6回・縦6回進む格子,C=(2,2),D=(4,4) として数える。最短経路は右・上の12手の並べ方であり,(2)は C,D を通る経路を包除原理で除く。(3)は斜線部分に入る経路を,最初に境界を越える点で反射させる標準対応により数える。

解答

(1)

図1では A から B まで,右へ6回,上へ6回進む最短経路を考える。したがって12回の移動のうち,上へ進む6回の位置を選べばよいから 12C6=12!6!6!=924 通りである。

(2)

図1の座標を A=(0,0),B=(6,6),C=(2,2),D=(4,4) と読む。 C を通る最短経路は,A から C までが右2回・上2回,C から B までが右4回・上4回なので 4C2 8C4=6⋅70=420 通りである。同様に D を通る経路も420通りである。

また,C と D の両方を通る経路は4C2 4C2 4C2=63=216通りである。包除原理により,C と D のどちらも通らない経路は 924−(420+420−216)=300 通りである。

(3)

図2の斜線部分に入らない最短経路は,座標でいえば常に y≦x を満たしながら (0,0) から (6,6) へ進む経路である。全経路は(1)と同じく924通りである。

斜線部分に入る経路は,初めて直線 y=x+1 に到達する点を持つ。この初到達点までの部分を直線 y=x+1 に関して反射すると,(−1,1) から (6,6) への右7回・上5回の最短経路と一対一に対応する。したがって斜線部分に入る経路は 12C5=792 通りである。よって求める数は 924−792=132 通りである。

別解

解法2

方針

各格子点に「そこまで来る最短経路数」を書き,左と下の値を足す動的計画法で3問を統一的に数える。(2)では C,D の値を0にし,(3)では通れない側の格子点を0にする。

解答

(1) 格子点 (i,j) までの最短経路数を T(i,j) とする。境界ではT(i,0)=T(0,j)=1であり,内部では最後の1歩が左または下から来るのでT(i,j)=T(i−1,j)+T(i,j−1)である。これを 0≦i,j≦6 で順に埋めるとT(6,6)=924を得る。

(2) 同じ漸化式を使い,通過を禁止する C=(2,2),D=(4,4) では値を0と置く。すなわちT(2,2)=T(4,4)=0として表を埋め直すとT(6,6)=300となる。

(3) 図2では j>i の格子点を通れないので,そこを全て0と置く。許される三角形領域では同じ加法則を使うと,i=6 の列はT(6,0),T(6,1),…,T(6,6)=1,6,20,48,90,132,132となる。したがって答えはT(6,6)=132通りである。

総評

難度6,計算量5。図の読み取りを座標化できれば,(1)(2)は組合せの標準計算である。(2)では C と D の両方を通る経路を一度足し戻す包除原理が必要になる。(3)は通れない領域を直接数えるより,初めて境界を越える位置で反射させると一手で数えられる。解答では座標の取り方を最初に明記することが重要で,本番では図への書き込みも含めて15分程度が目安である。

Evolton Pro

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

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

出典: 九州大学 2008年度 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。