この問題の解説と、これまでの解答の記録です。
図1のA₁地点からC₂地点へ行くとき，通過する地点が最も少なくてすむ最短経路は，図2のように数えることによって3通りあることが分かる。A₁地点から，C₂地点を経由して，D₄地点へ行く最短経路は何通りあるか。 図1 格子状の地点配置（縦に4行，横に4列）。各行・各列の地点は格子状の経路で隣接地点とつながっている。
| 行＼列 | 1列目 | 2列目 | 3列目 | 4列目 |
|---|---|---|---|---|
| D行（最上行） | D₁ | D₂ | D₃ | D₄ |
| C行 | C₁ | C₂ | C₃ | C₄ |
| B行 | B₁ | B₂ | B₃ | B₄ |
| A行（最下行） | A₁ | A₂ | A₃ | A₄ |
出発地点はA₁（左下），経由地点はC₂，目的地点はD₄（右上）。 図2 A₁からC₂までの最短経路の数え方。矢印は最短経路の進行方向，（ ）内数字は，A₁からその地点までの最短経路の数を表す。 - A₁ → B₁（1） - A₁ → A₂（1） - B₁ → C₁（1） - B₁ → B₂（2） - A₂ → B₂（2） - C₁ → C₂（3） - B₂ → C₂（3）
6 は、前半 3 通りと後半 3 通りを 3 + 3 と足してしまった値。前半と後半は「どちらか一方を選ぶ」関係ではなく「前半を選んだうえで後半も選ぶ」関係なので、和の法則ではなく積の法則を使う。足し算でつなぐと、A₁ → C₂ の 3 通りそれぞれに C₂ → D₄ の 3 通りが対応するという組合せの広がりを数え落とすことになる。
正解 正解は イ (9 通り)。図1 の格子は行が下から A・B・C・D、列が左から 1・2・3・4 で、A₁ が左下、D₄ が右上、C₂ が経由点である。最短経路とは遠回りをせず、右か上にだけ進む経路のこと。まず前半の A₁ → C₂ は、右へ 1 区間・上へ 2 区間、合計 3 区間進む。3 区間のうちどの 1 区間を右向きにするかを選べばよいので 3 通りで、これは図2 が示す （3） と一致する。次に後半の C₂ → D₄ は、右へ 2 区間・上へ 1 区間、やはり合計 3 区間で、3 区間のうちどの 1 区間を上向きにするかを選ぶので 3 通り。前半のどの経路を選んでも後半は独立に 3 通り選べるため、積の法則により 3 × 3 = 9 通りとなる。図2 と同じく各地点へ左と下から来る経路数を足し上げる数え方でも確かめられ、C₂ を 1 と置き直すと C₃ = 1、C₄ = 1、D₂ = 1、D₃ = D₂ + C₃ = 2、D₄ = D₃ + C₄ = 3 となり、3 × 3 = 9 通りが得られる。
12 は 3 × 4 の形で、後半 C₂ → D₄ を 4 通りと数え違えた場合に出る値。C₂ から D₄ までは右へ 2 区間・上へ 1 区間の合計 3 区間しかないため、上へ進む区間の選び方は 3 通りであって 4 通りにはならない。図2 と同じ足し上げ方を C₂ を起点にやり直せば、D₄ は 3 になることが確認できる。
20 は、C₂ を経由するという条件を無視して A₁ から D₄ へ行く最短経路をすべて数えた値。A₁ → D₄ は右へ 3 区間・上へ 3 区間の合計 6 区間で、6 区間のうち右向きの 3 区間を選ぶ数え方により 20 通りになる。本問は経由点 C₂ を必ず通る経路だけを問うているので、C₂ を通らない残り 11 通りを除かなければならない。