Evolton

京都大学 1992年度 後期日程 第2次学力試験理系（後期）数学 第2問

一辺の長さがnの立方体ABCD−PQRSがある．
ただし，2つの正方形ABCD，PQRSは立方体の向かい合った面でAP，BQ，CR，DSは，それぞれ，立方体の辺である．

立方体の各面は一辺の長さ1の正方形に碁盤目(ごばんめ)状に区切られているとする．
そこで，頂点Aから頂点Rへ碁盤目上の辺をたどっていくときの最短径路を考える．

(1) 辺BC上の点を通過する最短径路は全部で何通りあるか．

(2) 頂点Aから頂点Rへの最短径路は全部で何通りあるか．

難易度9/ 10計算量9/ 10目安30分

場合の数、整数　数え上げ、場合分け、包除原理

方針

格子路を x,y,z 各方向の単位移動の語として表す。表面上に留まるには、第3種類目の方向が初めて現れるまでに、先の2方向の一方が n 回完了している必要がある。(1)は指定辺へ初めて到達する位置で分け、(2)は最後に現れる方向を選んで数える。

解答

座標をA=(0,0,0),B=(n,0,0),C=(n,n,0),R=(n,n,n)とする。最短経路は正の x,y,z 方向の移動を各 n 回行う長さ 3n の経路である。

(1) 辺 BC を通るには、最初の z 方向移動より前に x 方向移動を n 回終える必要がある。n 回目の x 移動の前に y 移動が j 回あるとすると、そこまでの並べ方はn+j−1Cj通り、その後の n−j 回の y 移動と n 回の z 移動の並べ方は2n−jCn通りである。よって∑j=0nn+j−1Cj2n−jCn=3nCn通りである。最後の等式は積を「n 個の x の最後の位置」で分類するVandermonde型の数え上げである。

(2) 3方向のうち最後に初めて現れる方向を選ぶ方法は3通りである。例えば z が最後とする。最初の z より前には x,y がともに現れ、どちらか一方はすでに n 回現れている。

x が n 回、y が j 回 (1≦j≦n) 現れてから最初の z が現れる経路数はn+jCj2n−j−1Cn−1.x,y を入れ替えたものを2倍し、両方が n 回の場合の重複 2nCn を引く。ここで∑j=0nn+jCj2n−j−1Cn−1=3nCnであり、j=0 の項は 2n−1Cn−1=122nCn である。従って最後の方向を固定した個数は2(3nCn−122nCn)−2nCn=2(3nCn−2nCn).求める総数は6(3nCn−2nCn).

総評

立方体表面の制約を語の初出条件へ変換する最難関級の数え上げで目安は30分。表面条件を落として単純な多項係数にしないことと、最後に現れる方向の重複を正確に引くことが核心である。

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

出典: 京都大学 1992年度 後期 数学。問題文はHTML表示のために再入力・数式組版しています。