Friends and enemies in pairs set S

CAT 2007 Slot 1 · QA · Hard · Combinatorics

All CAT 2007 Slot 1 questionsMore Combinatorics questionsAll CAT QA

Passage / data set

Let SS be the set of all pairs (i,j)(i, j) where 1≤i<j≤n1 \le i < j \le n and n≥4n \ge 4. Any two distinct members of SS are called "friends" if they have one constituent of the pairs in common and "enemies" otherwise. For example, if n=4n = 4, then S={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}S = \{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}. Here, (1,2)(1, 2) and (1,3)(1, 3) are friends, (1,2)(1, 2) and (2,3)(2, 3) are also friends, but (1,4)(1, 4) and (2,3)(2, 3) are enemies.

Question 1 of 2

For general 'nn', how many enemies will each member of SS have?

  1. A.

    n−3n - 3

  2. B.

    \frac{1}{2}(n^2 - 3n - 2)

  3. C.

    2n−72n - 7

  4. D.

    \frac{1}{2}(n^2 - 5n + 6)

  5. E.

    \frac{1}{2}(n^2 - 7n + 14)

Answer

D

Explanation

For a pair (i,j)(i, j), an enemy pair must contain neither ii nor jj. The number of elements other than i,ji, j is n−2n - 2. The number of pairs formed from these n−2n - 2 elements is (n−22)=(n−2)(n−3)2=12(n2−5n+6)\binom{n-2}{2} = \frac{(n-2)(n-3)}{2} = \frac{1}{2}(n^2 - 5n + 6).

Question 2 of 2

For general 'nn', consider any two members of SS that are friends. How many other members of SS will be common friends of both these members?

  1. A.

    \frac{1}{2}(n^2 - 5n + 8)

  2. B.

    2n−62n - 6

  3. C.

    \frac{1}{2}n(n - 3)

  4. D.

    n−2n - 2

  5. E.

    \frac{1}{2}(n^2 - 7n + 16)

Answer

D

Explanation

Let the two friendly pairs be (1,2)(1, 2) and (1,3)(1, 3). Common friends must share an element with both (1,2)(1, 2) and (1,3)(1, 3). These can be of the form (1,k)(1, k) where k≠2,3k \neq 2, 3 (n−3n - 3 options), or (2,3)(2, 3) (1 option). Total =(n−3)+1=n−2= (n - 3) + 1 = n - 2.

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace