Evolton
方針
長さ1の線分は格子の横辺と縦辺だけである。まず横辺 本、縦辺 本を数えて を得る。(2)では から まで、少なくとも右方向に 回、上方向に3回、合計 本の線分が必要なので、選んだ全ての線分が最短経路そのものでなければならない。(3)では 本を選ぶが、端点間の経路の長さは と同じ奇偶に限られるため、 本の経路はありえない。したがって最短経路1本に、経路外の線分を1本追加する場合を数える。
解答
(1)
長さ1の線分は、隣り合う格子点を結ぶ横または縦の線分である。
横の線分は、各 について の 本がある。したがって横の線分は 本である。
縦の線分は、各 について の3本がある。したがって縦の線分は 本である。よって である。相異なる 本を選ぶ方法は 通りである。
(2)
点 から点 までつながるには、 座標を合計 だけ増やし、 座標を合計3だけ増やす必要がある。長さ1の線分を1本通るごとに、座標は上下左右のいずれかに1だけ変わる。したがって、どのようなつながり方でも少なくとも 本の線分が必要である。
いま選ぶ線分はちょうど 本であるから、つながるためには、それら全てが から への最短経路を作っていなければならない。最短経路では右へ進む線分が 本、上へ進む線分が3本であり、その並べ方は 通りである。
全ての選び方は 通りである。よって求める確率は である。
(3)
今度は 本を選ぶ。 から までの経路の長さは、最短長 に戻り道の分だけ偶数を加えたものになる。したがって、経路の長さは の形であり、 本の経路は存在しない。
よって 本の線分を選んで2点がつながるためには、その中に から への最短経路が含まれており、残り1本はその経路に含まれない線分である必要がある。
最短経路は 通りである。1つの最短経路は 本の線分を使うので、経路外の線分は 本である。したがって有利な選び方は 通りである。
ここで重複して数えていないことを確認する。 本の中に異なる2つの最短経路が含まれるなら、2つの経路はどこかで分かれて再び合流し、その部分だけで少なくとも1つの小さな四角形を作る。その場合、2つの最短経路の和集合は最短経路より少なくとも2本多い線分を含むので、少なくとも 本必要である。よって 本の場合には最短経路はただ1つである。
全ての選び方は 通りであるから、求める確率は である。
総評
格子上の線分選択を、最短経路の数え上げに落とす確率問題で、22分程度が目安である。(1)では横辺と縦辺を分けて 本を正確に数える。(2)は選んだ本数が最短長と等しいため、右 回・上3回の並べ方だけでよい。(3)では「1本多いから少し寄り道できる」と考えがちだが、端点間の経路長は最短長と同じ奇偶に限られるので、 本の経路は作れない。したがって最短経路に経路外の1本を加える場合だけを数える。重複が起きない理由まで書くと答案として安定する。