### CAT 2007 Question 10

Instructions

Directions for the following two questions:

Let S be the set of all pairs (i, j) where 1 <= i < j <= n , and n >= 4 (i and j are natural numbers). Any two distinct members of S are called “friends” if they have one constituent of the pairs in common and “enemies” otherwise.

For example, if n = 4, then S = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}. Here, (1, 2) and (1, 3) are friends, (1,2) and (2, 3) are also friends, but (1,4) and (2, 3) are enemies.

Question 10

# For general n, consider any two members of S that are friends. How many other members of S will be common friends of both these members?

Solution

For n, the number of elements in set S is $$^nC_2$$.

Lets say the 2 friends are (x,a) and (y,a)

These two friends have 3 numbers in total and 1 common element(say a) (as both elements cannot be exactly same)

They have 2 non common elements(x, y)

The number of common friends is formed by the non-common elements of the friends (x,y) + the number of elements in the set which have the common element other than the two friends (a,c), (a,d) and so on = 1 + (n-1 - 2) = n-2.

For the example in question, if the friends are (1,2) and (1,3), then common friends are (2,3) and all other elements with 1

All elements with 1 = n-1= 3 which are (1,2) (1,3) (1,4) excluding the friends (1,2) and (1,3) only 1 other friend is common. Hence it is 1+(n-1)-2=n-2