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

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

---

As @Arjun sir's answer,

We have vertices and edges formed as follows:

1 connected to 9

2 connected to 10

3 connected to 11

4 connected to 12

5 connected to 13  but 1 is connected to 13 so 13 is in the same connected component. Now only 1,2,3,4 are 4 different connected components that have all the vertices.

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....

---

The explanation above is correct. I tried to help those who could still not visualize how the vertices set of difference 8 got connected with its own bottom sets to reduce the total connected components to 4.

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

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

---

@halfcodeblood 

How GCD is working for this question : 

$|i-j|= 8$ or $|i-j|=12$

for any two numbers if we subtract them either we get 8 or we get 12,

let's take a small example : 

$|1-9|= 8$  or $|1-13| = 12$
$|2-10| = 8$ or $|2-14| = 12$
$|3-11| = 8$ or $|3-15| = 12$
$|4-12| = 8$ or $|4-16| = 12$

the only common thing in this examples is when you divide each of the i and j with the GCD you will get the same remainder

the $\gcd(8,12)$ is 4

case I:

$\frac{1}{4}$, remainder would be 1 && $\frac{9}{4}$, remainder would be 1

$\frac{2}{4}$, remainder would be 2 && $\frac{10}{4}$, remainder would be 2

$\frac{3}{4}$, remainder would be 3 && $\frac{11}{4}$, remainder would be 3

$\frac{4}{4}$, remainder would be 0 && $\frac{12}{4}$, remainder would be 0

$\frac{5}{4}$, remainder would be 1 .....

case II:

$\frac{1}{4}$, remainder would be 1 && $\frac{13}{4}$, remainder would be 1

$\frac{2}{4}$, remainder would be 2 && $\frac{14}{4}$, remainder would be 2

$\frac{3}{4}$, remainder would be 3 && $\frac{15}{4}$, remainder would be 3

$\frac{4}{4}$, remainder would be 0 && $\frac{16}{4}$, remainder would be 0

$\frac{5}{4}$, remainder would be 1 .....

from these we can see 4 unique groups (remainders) are forming {0,1,2,3} which are connected components

and GCD will work everytime for these kind of varitions,

please correct the above explanation 😀

---

But i think GCD are use And operation like i and j are adjacent of 8 and 12 then use  am i wrong ?  Then please correct me 

Answer 3

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.

---

how is this ques related to linear  Diophantine equation ?

Answer 4

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 5

This makes easier to understand..!

Answer 6

A method I tried, Arjun sir, Rajesh Pradhan sir please check:

P(Number of disconnected components with |i-j|=12)   floor(12/100)/100= 8/100

P(Number of disconnected components with |i-j|=8)   floor(8/100)/100= 12/100

P(Number of disconnected components with |i-j|=12 or |i-j|=8)   12/100 * 8/100 = 96/100

Therefore connected components=1-96 = 4/100 i.e 4? 

Does it makes sense? please check