MathLabs

Problem 3

Let nn be a positive integer. nn people take part in a party. For each pair, either the two people are acquainted or they are not. What is the maximum possible number of pairs that are not acquainted but have a common acquaintance among the participants?
Step 6 of 6: Conclusion
Previous stepNext step
(n−1)(n−2)/2\boxed{(n-1)(n-2)/2}
Detailed analysis

The star construction attains the upper bound, so the maximum is (n−1)(n−2)/2(n-1)(n-2)/2.