Question

Sara has just joined Facebook. She has 5 friends. Each of her five friends has twenty five friends. It is found that at least two of Sara's friends are connected with each other. On her birthday, Sara decides to invite her friends and the friends of her friends. How many people did she invite for her birthday party?

• A. \(\ge 105\)
• B. \(\le 123\)
• C. \(< 125\)
• D. \(\ge 100 \text{ and } \le 125\)
• E. \(\ge 105 \text{ and } \le 123\)

Hint:

When counting ``friends of friends,'' use inclusion--exclusion to avoid double counting. If each of \(k\) friends has \(d\) friends including the center, start from \(k(d-1)\) and subtract guaranteed overlaps. A statement like “at least two are connected” forces \(\ge 2\) overlaps (each direction), tightening the upper bound.

Answer 1

The Correct Option is B

Step 1: Let \(F\) be Sara's set of friends. Then \(|F|=5\). Each friend has \(25\) friends total (including Sara). For a single friend, the number of other people in their list (excluding Sara) is \(25-1=24\).
Step 2: If there were no overlaps among these ``friends-of-friends,'' the maximum number of distinct people reachable at distance \(\le 2\) (excluding Sara) would be \[ |F| + 5\times 24 \;=\; 5+120 \;=\; 125. \] Step 3: We are told at least two of Sara's friends are connected with each other. That guarantees that within the five friend-lists, one friend appears in another friend's list, and vice versa. Thus among the \(5\times 24\) positions, at least \(2\) of them are occupied by members of \(F\) (not new people). Hence, the number of distinct outsiders is reduced by at least \(2\): \[ \text{distinct outsiders} \;\le\; 120-2 \;=\; 118. \] Step 4: Therefore, the total number of invitees (all five friends \(+\) distinct outsiders), excluding Sara herself, satisfies \[ \text{invited} \;\le\; 5 + 118 \;=\; 123. \] So, Sara invited \(\le 123\) people.