Asian Pacific Mathematical Olympiad 2010 Problem 3
Source:
May 7, 2010
inductionstrong inductioncombinatorics proposedcombinatoricsintuitive
Problem Statement
Let be a positive integer. people take part in a certain party. For any pair of the participants, either the two are acquainted with each other or they are not. What is the maximum possible number of the pairs for which the two are not acquainted but have a common acquaintance among the participants?