ISI2015-MMA-7

Question

Let $X$ be the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$. Define the set $\mathcal{R}$ by $\mathcal{R} = \{(x,y) \in X \times X : x$ and $y$ have the same remainder when divided by $3\}$.

Then the number of elements in $\mathcal{R}$ is

• A. $40$
• B. $36$
• C. $34$
• D. $33$

Answer 1

The given relation R is equivalence relation(since it satisfies reflexive,symmetric,transitive properties).

The  given equivalence relation R partitions the domain into 3 non empty,disjoint,exhaustive subsets {1,4,7,10}, {2,5,8}, {3,6,9}.

Together these 3 subsets form a partition.

we have to form the ordered pairs in equivalence relation from the partition.

The ordered pairs from {1,3,7,10}={(1,1),(1,4),(1,7),(1,10),(4,1),(4,4),(4,7),(4,10),(7,1)(7,4),(7,7),(7,10),(10,1),(10,4),(10,7),(10,10)}

or for the ordered pair(x,y) from the subset {1,3,7,10}, x has 4 choices and y also has 4 choices.

Therefore 16 ordered pairs are formed from subset {1,3,7,10}.

The ordered pairs from {2,5,8}={(2,2),(2,5),(2,8),(5,2),(5,5),(5,8),(8,2),(8,5),(8,8).

or for the ordered pair (x,y) from the subset {2,5,8} ,x has 3 choices and y also has 3 choices.

Therefore 9 ordered pairs are formed from subset {2,5,8}.

similarly 9 order pairs are formed from subset  {3,6,9}.

Therefore there are 16+9+9=34 ordered pairs possible.

 

Answer 2

We  can have 10 pairs that is $\{(1,1), (2,2),  \ldots ,(10,10)\}$ and each of the pair have same remainder.

For $1 \rightarrow \{4, 7, 10\} \text{ will have same remiander and they can form pair in 12 ways}$

For $2 \rightarrow \{5, 8\} \text{ will have same remiander and they can form pair in 6 ways}$

For $3 \rightarrow \{6, 9\} \text{ will have same remiander and they can form pair in 6 ways}$ with each other

$(3,6), (6,3), (3,9), (9,3), (6,9), (9,6)$

So total number of ways = $10 + 12 + 6 + 6 = 34$

Hence option $C$ is the answer

Comments

correct.