Maths Olympiad Prep

Library / /29 of 46

Combinatorics Difficulty 6.4 National olympiad Prove it Russia

On a party a company of 20 persons is to be arranged to sit around 4 tables. An arrangement is called successful if each two persons sharing a table are friends. It appears that there exists at least one successful arrangement, and for each successful arrangement exactly 5 persons sit around each table. Find the greatest possible number of pairs of friends in a company.

Solution

Answer. 160160.

If two people are not friends, we will say that they are enemies. The total number of pairs of people in this company is 20192=190\frac{20 \cdot 19}{2} = 190, so it is enough to prove that the minimal number of pairs of enemies is 3030.

Let us prove that there cannot be fewer than 3030 pairs of enemies. Suppose the contrary. Then there is a person AA who has at most two enemies (if every person has at least three enemies, the number of pairs of enemies is at least 3202=30\frac{3 \cdot 20}{2} = 30). Suppose AA is seated at some table TT in a successful arrangement. By the condition, there are exactly 55 people at table TT. Since AA has at most two enemies, at one of the remaining three tables, all the people are friends of AA. Therefore, if we move AA to that table (and do not change the rest of the arrangement), the new arrangement will also be successful, but table TT will have only 44 people, which contradicts the condition.

Let us give an example satisfying the condition, in which there are exactly 3030 pairs of enemies. Divide all people into 55 groups of 44, and let any pair of people from the same group be enemies, and any pair from different groups be friends. In this case, each person has exactly 33 enemies, and there are 3202=30\frac{3 \cdot 20}{2} = 30 pairs of enemies in total. In the described situation, an arrangement is successful if and only if people from the same group are seated at different tables. Thus, successful arrangements exist, and in any successful arrangement, each table will have exactly one person from each group, that is, exactly 55 people.

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 and solution reproduced as published; topic and difficulty added by this site.