Maths Olympiad Prep

Library / /20 of 39

Combinatorics Difficulty 6.4 National Olympiad Prove it Croatia

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 1010 people that both persons know and exactly 1010 people that both persons do not know. All acquaintances are mutual. How many people are there in all three committees?
(Russia 2008)

Solution

Let AA, BB, CC be committees and let them have exactly aa, bb, cc 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 xAx \in A, yBy \in B there are exactly 1010 monochromatic triangles (if xyxy is a blue segment, there are 1010 points zCz \in C such that segments xzxz and yzyz are blue, and analogously for red segments). Hence, the number of monochromatic triangles is 10ab10ab. In the same way we conclude that the number of monochromatic triangles is 10bc10bc and 10ca10ca, so we conclude a=b=ca = b = c.

The number of all triangles is a3a^3, while the number of monochromatic triangles is 10a210a^2. Let us count bichromatic triangles. For each pair xAx \in A, yBy \in B we have exactly 1010 bichromatic triangles such that the segments xzxz and yzyz have the same colour, i.e. there are 10a210a^2 such triangles, while there are 10a210a^2 triangles such that yxyx and zxzx are of the same colour, and 10a210a^2 triangles such that xyxy and zyzy are of the same colour. Hence there are 30a230a^2 bichromatic triangles.

Finally, we have a3=10a2+30a2a^3 = 10a^2 + 30a^2, so a=40a = 40. This means that there are in total 120120 members in all three committees.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.