in Graph Theory edited by
8,274 views
55 votes
55 votes

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$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is

  1. $4$
  2. $7$
  3. $23$
  4. $99$
in Graph Theory edited by
8.3k views

1 comment

If anyone approaches the question thinking

“There is another path also which gives the same answer.

1-->3-->4-->12-->11-->33-->99-->100  (so 7 edges required)”

then this approach is wrong. since there is path from (11 to 12) but not (12 to 11) directed graph is given.
0
0

3 Answers

84 votes
84 votes
Best answer

Edge set consists of edges from $i$ to $j$ using either 

  1. $ j = i+1$ (or)
  2. $ j=3i.$

Second option will help us reach from $1$ to $100$ rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from $1$ to $100$, try to find a path from $100$ to $1$.

The edge sequence with minimum number of edges is $1\rightarrow3\rightarrow9\rightarrow10\rightarrow11\rightarrow33\rightarrow99 - 100$ which consists of $7$ edges. 
The answer is option ($B$).

edited by

4 Comments

ans y not a) thts 4 beacuse 1-3-9-27-51

by condition j=3i..

kindly explain
1
1
finally u r at  51 not at 100.. do j = i+1 until u reach 100..
8
8
sir , i was solving in this without see answer

p(A∪B)=P(A)+P(B)-P(A∩B)

P(A) i assume here: j=i+1 with this i get ..99 edges

P(B) i assume J=3i with this i got  4 edges

P(A∩B)=got 80 edges.

therfore ans is 23. finally wt i see my ans was wrong.! why ans is not 23.????
0
0

union of two set is not minimum one,thats why..In qs minimum was asked..if minimum keyword was not given..Then 23 should be answer.

1
1
63 votes
63 votes

The conditions are given
Edge set consists of edges from i to j using either

  1.  j = i+1 OR
  2.  j=3i

What we think from here :  Minimum we take vertex 1 max we take vertex 100


Now one important point is to reach 100 the maximum number  which gets   j = 3*i where i= 33 so j = 3*33 = 99


Half problem is solved.
We got                                                                   1--33--99--100
Now see to reach 33 how many minimum edges needed.
Maximum number between which get value j= 3i, i= 11 so j= 3*11= 33


What we get                                                               1--11--33--99--100
So, problem solved almost minimum edge need to reach 11 from 1


Max number i which get j= 3i, i= 3 so j= 3*i =9 to reach 11 ..9--10--11
So we got another point
                                                                                  1--9--10--11--33--99--100

Now to reach 11 from 1
Max value of i = 3 so j= 3*i= 9 so 3--9
                                                                                 1--3--9--10--11--33--99--100

Note: Solved problem into half give u an idea how to get minimum for rest of the graph.

edited by

4 Comments

Great explanations sir
0
0
easy to understand this solution.

Thanks
0
0
"DIVIDED & CONQUERED" algorithms at it's best😄
0
0
0 votes
0 votes
The desired path (from end to begin) will be 100--99--33--11--10--9--3—1

The edges between them is as per the condition mentioned in the question. Hence min. path length is 7.

1 comment

Thanks a lot
0
0
Answer:

Related questions