UGC NET CSE | October 2020 | Part 2 | Question: 26

Question

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 and only 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. $23$
• B. $99$
• C. $4$
• D. $7$

Answer 1

Option D) is correct

GATE 2005

Answer 2

Edge set consists of edges from i to j, using either two conditions are j = i + 1 or j = 3i
Second choice helps us to move from 1 to 100. The trick to slot this is to think the other way
around. Try to find a 100 to 1 trail, instead of having a 1 trail to 100.
So, the edge sequence with the minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
Hence the correct answer is 7.