ITPEC IP October 2024 Question 4

Topic: Basic TheoryAlso asked in April 2019

When a path goes from node A1 to node C2 in Fig. 1 and the passing nodes are counted as shown in Fig. 2, there are three shortest paths with the minimum number of passing nodes. How many shortest paths are there available to go from node A1 to node D4 via node C2?

D1D2D3D4C1C2C3C4B1B2B3B4A1A2A3A4Fig. 1
A1B1(1)A2(1)C1(1)B2(2)C2(3)The number in parenthesesbelow a node represents thenumber of shortest pathsfrom A1 to that node.Fig. 2

Explanation

9 — multiply the 3 shortest paths from A1 to C2 by the 3 shortest paths from C2 to D4.

A shortest path only moves right or up. Fig. 2 already counts 3 shortest paths from A1 to C2. From C2 to D4 a shortest path takes two steps right (column 2 to 4) and one step up (row C to D); the up step can come first, second or third, so there are 3 paths: up-right-right, right-up-right, right-right-up.

Every path of the first leg can be followed by every path of the second, so the total is 3 × 3 = 9.

Answer (b)

Why not others:

  • •(a) 6 — adds the two legs, 3 + 3, instead of multiplying independent choices
  • •(c) 12 — would need 4 routes on one leg, but each leg has exactly 3 shortest paths
  • •(d) 20 — is the number of shortest paths from A1 to D4 with no constraint, 6C3 = 20 (3 right and 3 up in any order); the route must pass through C2

Key rule: Shortest paths through a fixed node = (paths to the node) × (paths from the node); a leg of r right and u up steps has r+uCr shortest paths.

Basic Theory · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official IP past-paper collection or Report an issue.