### CAT 2007 Question 9

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 9

# For general n, how many enemies will each member of S have?

Solution

Any ordered pair has 2 elements => There are n-2 elements that are not present in the ordered pair.

The number of enemies of any ordered pair is all the ordered pairs in the set formed using the numbers other than these two elements = $$^{n-2}C_2$$ = $$1/2 * (n^2 - 5n + 6)$$.