In an organization there are three committees. Each person belongs to exactly one committee. For any two persons belonging to different committees, in the third committee there are exactly people that both persons know and exactly people that both persons do not know. All acquaintances are mutual. How many people are there in all three committees?
(Russia 2008)
Solution
Let , , be committees and let them have exactly , , persons, respectively. To each person assign a point in the plane so that no three points are collinear. We connect the points corresponding to persons that know each other by a blue segment, and for those that do not know each other by a red segment. Points corresponding to persons in the same committee are not connected.
First, let us count the monochromatic triangles (all three sides are of the same colour). For each pair of persons , there are exactly monochromatic triangles (if is a blue segment, there are points such that segments and are blue, and analogously for red segments). Hence, the number of monochromatic triangles is . In the same way we conclude that the number of monochromatic triangles is and , so we conclude .
The number of all triangles is , while the number of monochromatic triangles is . Let us count bichromatic triangles. For each pair , we have exactly bichromatic triangles such that the segments and have the same colour, i.e. there are such triangles, while there are triangles such that and are of the same colour, and triangles such that and are of the same colour. Hence there are bichromatic triangles.
Finally, we have , so . This means that there are in total members in all three committees.