GATE CSE 1997 | Question: 6.2

Question

Let $G$ be the graph with $100$ vertices numbered $1$ to $100$.  Two vertices $i$ and $j$ are adjacent  if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of connected components in $G$ is

• A. $8$
• B. $4$
• C. $12$
• D. $25$

Comments

Plz have a look at :

https://gateoverflow.in/2258/gate1997_6-2

---

if que given was like this | i-j |=10, or | i-j |= 20 then ans will be 10 right .

---

Yes , right. Nice interpretation b/w

Answer 1

From the description it is clear that vertices are connected as follows:

$1-9-17-...-97$
$2-10-18-...-98$
$3-11-19-...-99$
$4-12-20-...-100$
$5-13-21-...-93$
$6-14-22-...-94$
$7-15-23-...-95$
$8-16-24-...-96$

We have covered all vertices using $8$ vertex sets considering only $\mid i - j \mid = 8$. Using $\mid i - j \mid = 12$ we can see the vertex $1$ is connected to $13, 2-14, 3-15$ and $4-16$, so the top $4$ vertex sets are in fact connected to the bottom $4$ sets, thus reducing the connected components to $4$.

Correct Answer: $B$

Comments

Arjun sir we can also strt with i-j=12 and after tha we ll get 12 components and by ysing i-j=8 we find that exactly 3 components r going 2 merge so total 12/3 = 4 components....

Answer 2

Lets reduce this problem to n=20 only, bcoz it doesn't matter if n=100 or 1000 or 20

Even this type of question can also be solved using GCD(8,12)=4. I have also tested drawing this above graph for GCD(5,7)=1 and many more.

So answer is 4 here.

Comments

@Verma Ashish

Can u tell me, what is the meaning of number of connected components?

First of all  $1-9-17-...-97$, it is going upto $97$, but not $100,$ then how it could be a connected component?

Secondly when difference of $12$ comes in picture, then why number of connected component reduced?

---

https://en.m.wikipedia.org/wiki/Component_(graph_theory)

Secondly when difference of 12 comes in picture, then why number of connected component reduced?

Because there exist some vertices in two different components (according to diff=8) such that difference between them is 12.

For example-- 1-9-17-25-33-41-... And 5-13-21-29-37-... are two components according to difference 8.

But 13-1=12, 25-13=12,... ==> 1and 13, 13and 25 are connected.

So these two components will form a single connected component

 

---

@Nitesh Singh 2 can you tell me how GCD is working on this question? and will it work everytime for these kind of variations?

Answer 3

there will be 4 connected component.(1 5 9 13 17......)(2 6 10 14 18....) (3 7 11 15 19 .....)(4 8 12 16......)

Answer 4

Answer is 4 because GCD(8,12) = 4 (means you can measure multiple of 4)

For more information related to applied method refer -->

https://mindyourdecisions.com/blog/2015/09/13/the-3-jug-riddle-sunday-puzzle/

https://math.stackexchange.com/questions/145346/diophantine-equations-with-multiple-variables

https://math.stackexchange.com/questions/514105/how-do-i-solve-a-linear-diophantine-equation-with-three-unknowns.

I hope this helps and now you can think about other variation of this question as well.

Comments

Another brute force approach as mentioned(just try for few numbers)

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	2	3	4	1	2	3	4	1	2	3	4	1	2	3	4	1	2	3	4

So answer is 4.