Let G be a directed graph whose vertex set is the set of numbers from 1 to…
2005
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is
- A.
4
- B.
7
- C.
23
- D.
99
Attempted by 141 students.
Show answer & explanation
Correct answer: B
Answer: 7 edges.
Key idea: Work backwards from 100 using the inverse operations (subtract 1, or divide by 3 when divisible). Each backward operation corresponds to one forward edge; this yields a shortest path.
100 is not divisible by 3, so do 100 - 1 = 99 (1 step).
99 is divisible by 3, so do 99 / 3 = 33 (2 steps).
33 is divisible by 3, so do 33 / 3 = 11 (3 steps).
11 is not divisible by 3, so do 11 - 1 = 10 (4 steps).
10 is not divisible by 3, so do 10 - 1 = 9 (5 steps).
9 is divisible by 3, so do 9 / 3 = 3 (6 steps).
3 is divisible by 3, so do 3 / 3 = 1 (7 steps).
Reverse this sequence to obtain a forward path from 1 to 100:
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100, which uses 7 edges.
Therefore the minimum number of edges in a path from vertex 1 to vertex 100 is 7.