Answer to Question #145874 in Combinatorics | Number Theory for Asfandyar

Question

36 students are members of a sports club. Every two of them are either friends or enemies. (Friendship and enmity are reciprocal, i.e. if A is a friend to B then B is a friend to A, and the same applies to being enemies.) It has turned out that each of the students has exactly 8 enemies. Let us call a group of three students concurrent if they are either pairwise enemies or pairwise friends to each other. What is the maximum possible quantity of concurrent student triples in this sports club? (Two distinct concurrent student triples may have mutual students in them.)

Answer 1

The group where the students are pairwise enemies includes 9 students.

How many concurrent student triples can we choice from this group?

$$\dbinom{9}{3}=\dfrac{9!}{3!(9-3)!}=\dfrac{9(8)(7)}{1(2)(3)}=84$$

The group where the students are friends includes 27 students.

How many concurrent student triples can we choice from this group?

$$\dbinom{27}{3}=\dfrac{27!}{3!(27-3)!}=\dfrac{27(26)(25)}{1(2)(3)}=2925$$

What is the maximum possible quantity of concurrent student

triples in this sports club? 

$$84+2925=3009$$