MathDB

Problem 3

Part of 2013 CIIM

Problems(1)

CIIM 2013 Problem 3

Source:

8/9/2016
Given a set of boys and girls, we call a pair (A,B)(A,B) amicable if AA and BB are friends. The friendship relation is symmetric. A set of people is affectionate if it satisfy the following conditions:
i) The set has the same number of boys and girls.
ii) For every four different people A,B,C,DA,B,C,D if the pairs (A,B),(B,C),(C,D)(A,B),(B,C),(C,D) and (D,A)(D,A) are all amicable, then at least one of the pairs (A,C)(A,C) and (B,D)(B,D) is also amicable. iii) At least 12013\frac{1}{2013} of all boy-girl pairs are amicable.
Let mm be a positive integer. Prove that there exists an integer N(m)N(m) such that if a affectionate set has al least N(m)N(m) people, then there exists mm boys that are pairwise friends or mm girls that are pairwise friends.
CIIMCIIM 2013undergraduate