方針
図1・図2の位置関係を読み取り,図1は から まで横6回・縦6回進む格子,, として数える。最短経路は右・上の12手の並べ方であり,(2)は , を通る経路を包除原理で除く。(3)は斜線部分に入る経路を,最初に境界を越える点で反射させる標準対応により数える。
解答
(1)
図1では から まで,右へ6回,上へ6回進む最短経路を考える。したがって12回の移動のうち,上へ進む6回の位置を選べばよいから 通りである。
(2)
図1の座標を ,,, と読む。 を通る最短経路は, から までが右2回・上2回, から までが右4回・上4回なので 通りである。同様に を通る経路も420通りである。
また, と の両方を通る経路は通りである。包除原理により, と のどちらも通らない経路は 通りである。
(3)
図2の斜線部分に入らない最短経路は,座標でいえば常に を満たしながら から へ進む経路である。全経路は(1)と同じく924通りである。
斜線部分に入る経路は,初めて直線 に到達する点を持つ。この初到達点までの部分を直線 に関して反射すると, から への右7回・上5回の最短経路と一対一に対応する。したがって斜線部分に入る経路は 通りである。よって求める数は 通りである。
別解
解法2
方針
各格子点に「そこまで来る最短経路数」を書き,左と下の値を足す動的計画法で3問を統一的に数える。(2)では の値を0にし,(3)では通れない側の格子点を0にする。
解答
(1) 格子点 までの最短経路数を とする。境界ではであり,内部では最後の1歩が左または下から来るのでである。これを で順に埋めるとを得る。
(2) 同じ漸化式を使い,通過を禁止する , では値を0と置く。すなわちとして表を埋め直すととなる。
(3) 図2では の格子点を通れないので,そこを全て0と置く。許される三角形領域では同じ加法則を使うと, の列はとなる。したがって答えは通りである。
総評
難度6,計算量5。図の読み取りを座標化できれば,(1)(2)は組合せの標準計算である。(2)では と の両方を通る経路を一度足し戻す包除原理が必要になる。(3)は通れない領域を直接数えるより,初めて境界を越える位置で反射させると一手で数えられる。解答では座標の取り方を最初に明記することが重要で,本番では図への書き込みも含めて15分程度が目安である。