Evolton

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

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

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

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

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

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

方針

図からA、Bと通行止め2辺の座標を読み取る。(2)は積の法則、(3)は2つの禁止辺を通る経路を包除原理で除く。

解答

(1)

S から G へは東へ6回、北へ4回進むので10C4=210通りである。

(2)

図2では A=(1,1)、B=(2,1) である。したがって#(S→A)=2C1=2,#(A→B)=1,#(B→G)=7C3=35.よって A,B をともに通る経路は2⋅1⋅35=70通りである。

(3)

通行止め a を通る経路は2C1⋅7C3=70通りである。通行止め b は (4,2)→(4,3) の北向きの辺であるから、これを通る経路は6C2⋅3C1=15⋅3=45通りである。両方を通る経路は2C1⋅3C1⋅3C1=2⋅3⋅3=18通りである。包除原理により210−70−45+18=113.したがって 113 通りである。

別解

解法2

方針

格子点ごとの到達数を漸化的に記入し、2本の通行止めに対応する寄与だけを除外する。

解答

(1)

各格子点の経路数を、西隣と南隣の値の和として順に記入する。通行止めがないとき G の値は 210 となる。

(2)

A=(1,1) までの経路数は2、A→B は1、B=(2,1) から G までは35である。よって2⋅1⋅35=70.(3)

辺 a:(1,1)→(2,1) と辺 b:(4,2)→(4,3) からの寄与だけを加えずに動的計画法を行うとy\x01234564151327416811331481414274521346913181121234501111111となる。右上の値より答えは 113 通りである。

総評

難度5、計算量4、目安18分。原図から A=(1,1),B=(2,1)、禁止辺 a,b を再読した。答えは 210,70,113。既存の60、98は図の読み違いで、包除原理と動的計画法の双方により訂正した。

Evolton Pro

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

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

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