+26 votes
2.1k views

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

1. $8$
2. $4$
3. $12$
4. $25$
asked in DS
edited | 2.1k views
+1
suppose it was given 1 to 1000. then what would be the answer?

@ Arjun, @ Mithilesh?
+4
you should tell :)
+2
then also 4 only ... right sir ??
+1
@vijaycs how can u explain ??
+2
U r Right @vijaycs
+3
@Gabbar, I think solution provided by Arjun sir below is sufficient to answer for 1000.
+2

## 4 Answers

+41 votes
Best answer
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$.
answered by Veteran (379k points)
edited by
0
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....
+6 votes
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......)
answered by Junior (791 points)
+6 votes

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

answered by Active (1.5k points)
+1
imposing explanation..👍
+4 votes

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

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

answered by Boss (12.1k points)
edited by
0

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.

Answer:

+14 votes
3 answers
1
+12 votes
2 answers
2
+13 votes
3 answers
3
+27 votes
2 answers
4
+22 votes
4 answers
5
+20 votes
2 answers
6
+29 votes
6 answers
7