Let 𝐺 be a directed graph whose vertex set is the set of numbers from 1 to…
2020
Let 𝐺 be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex 𝑖 to a vertex 𝑗 if and only if either 𝑗=𝑖+1 or 𝑗=3𝑖. The minimum number of edges in a path in 𝐺 from vertex 1 to vertex 100 is ______ .
- A.
23
- B.
99
- C.
4
- D.
7
Attempted by 196 students.
Show answer & explanation
Correct answer: D
Key idea: work backwards from 100 using the inverse moves (subtract 1 or divide by 3 when divisible). Each backward move corresponds to one forward edge, so the number of backward moves equals the number of edges in a shortest forward path.
100 → 99 (subtract 1)
99 → 33 (divide by 3)
33 → 11 (divide by 3)
11 → 10 (subtract 1)
10 → 9 (subtract 1)
9 → 3 (divide by 3)
3 → 1 (divide by 3)
These are 7 backward moves, so the shortest forward path from 1 to 100 uses 7 edges. One explicit forward path is:
1 → 3 (multiply by 3)
3 → 9 (multiply by 3)
9 → 10 (add 1)
10 → 11 (add 1)
11 → 33 (multiply by 3)
33 → 99 (multiply by 3)
99 → 100 (add 1)
Justification of optimality: when working backward, reducing to the nearest number divisible by 3 (by subtracting 1 or 2 as needed) and then dividing by 3 always decreases the value faster than postponing division, so this greedy backward reduction yields a shortest sequence. Hence 7 is minimal.
A video solution is available for this question — log in and enroll to watch it.