This question's explanation and your answers so far.
図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 is the value obtained by adding the 3 routes of the first half and the 3 routes of the second half as 3 + 3. The first half and the second half are not in an “either one or the other” relationship but in a “choose the first half, and then also choose the second half” relationship, so the product rule must be used rather than the sum rule. Joining them with addition misses the combinatorial spread in which each of the 3 routes of A₁ → C₂ is paired with the 3 routes of C₂ → D₄.
正解 The correct answer is イ (9 routes). In the grid of Figure 1, the rows are A, B, C, D from the bottom up and the columns are 1, 2, 3, 4 from the left, so A₁ is at the bottom-left, D₄ is at the top-right, and C₂ is the via point. A shortest route means a route that makes no detour and moves only to the right or upward. First, the first half A₁ → C₂ goes 1 segment to the right and 2 segments up, 3 segments in total. You only have to choose which 1 of those 3 segments goes to the right, so there are 3 routes, which matches the (3) shown in Figure 2. Next, the second half C₂ → D₄ goes 2 segments to the right and 1 segment up, again 3 segments in total, and you choose which 1 of the 3 segments goes upward, so there are 3 routes here as well. Whichever route you take in the first half, the second half can still be chosen independently in 3 ways, so by the product rule there are 3 × 3 = 9 routes. You can also check this with the same counting method as Figure 2, adding up the number of routes reaching each point from the left and from below: if C₂ is renumbered as 1, then C₃ = 1, C₄ = 1, D₂ = 1, D₃ = D₂ + C₃ = 2, D₄ = D₃ + C₄ = 3, which again gives 3 × 3 = 9 routes.
12 has the form 3 × 4, the value that appears when the second half C₂ → D₄ is miscounted as 4 routes. From C₂ to D₄ there are only 3 segments in total, 2 to the right and 1 upward, so the number of ways to choose the segment that goes upward is 3, not 4. If you redo the same adding-up count as Figure 2 starting from C₂, you can confirm that D₄ comes out as 3.
20 is the value obtained by ignoring the condition of going via C₂ and counting all the shortest routes from A₁ to D₄. A₁ → D₄ is 3 segments to the right and 3 segments up, 6 segments in total, and counting how to choose the 3 rightward segments out of the 6 gives 20 routes. This question asks only about routes that must pass through the via point C₂, so the remaining 11 routes that do not pass through C₂ must be excluded.