Evolton

北海道大学 1999年度 前期日程 第2次学力試験文系数学 第4問

図のような碁盤の目状の道路がある.
S地点を出発して,道路上を東または北に進んでG地点に到達する経路を考える.
(図1の太線はそのような経路の一例である.)

(1) S地点からG地点に至る経路は何通りあるか.
(2) S地点からG地点に至る経路のうち,図2のA地点とB地点をともに通る経路は何通りあるか.
(3) 図3のaの部分が通行止めのとき,S地点からG地点に至る経路は何通りあるか.

問題の図
問題の図
問題の図

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

場合の数 数え上げ、包除原理、図形的解釈

方針

図の格子点を座標で正確に読み、(1)は東西移動の並べ替え、(2)は区間ごとの積、(3)は全体から通行止めの1辺を通る経路を引く。

解答

(1)

S から G へは東へ6回、北へ4回進む。10回の移動のうち北へ進む4回を選ぶので、10C4=210通りである。

(2)

図2の格子点を S=(0,0)、G=(6,4) と読むとA=(4,2),B=(5,2)である。したがって#(S→A)=6C2=15,#(A→B)=1,#(B→G)=3C2=3.積の法則より、A,B をともに通る経路は15⋅1⋅3=45通りである。

(3)

通行止め a は (1,1) から (2,1) へ向かう東向きの1辺である。この辺を通る経路は2C1⋅7C3=2⋅35=70通りである。よって、通行止めを避ける経路は210−70=140通りである。

別解

解法2

方針

格子点ごとの到達数を西隣と南隣の和で更新する。通行止めの辺から来る寄与だけを加えない。

解答

(1)

各格子点に「そこへ到達する経路数」を書く。西隣と南隣からしか来られないので、通常の格子点では両者の和を記入する。南端・西端を1から始めて右上まで計算するとy\x012345641515357012621031410203556842136101521281123456701111111となり、G の値は 210 である。

(2)

同じ表で A=(4,2) の値は 15 である。A→B は1通りで、B=(5,2) から G=(6,4) までの小格子の経路数は3である。よって15⋅1⋅3=45.(3)

(1,1)→(2,1) の寄与だけを加えず、同じ漸化式を続けるとy\x01234564151327508614031481423365421346913181121234501111111を得る。したがって答えは 140 通りである。

総評

難度4、計算量3、目安15分。原図の座標を再照合し、答えは 210,45,140。既存解答の(2)の60通りは図2のA、Bの位置の読み違いであり訂正した。二項係数と動的計画法が一致する。

Evolton Pro

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

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

出典: 北海道大学 1999年度 前期 文系 第4問。問題文はHTML表示のために再入力・数式組版しています。