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. .
If two people are not friends, we will say that they are enemies. The total number of pairs of people in this company is , so it is enough to prove that the minimal number of pairs of enemies is .
Let us prove that there cannot be fewer than pairs of enemies. Suppose the contrary. Then there is a person who has at most two enemies (if every person has at least three enemies, the number of pairs of enemies is at least ). Suppose is seated at some table in a successful arrangement. By the condition, there are exactly people at table . Since has at most two enemies, at one of the remaining three tables, all the people are friends of . Therefore, if we move to that table (and do not change the rest of the arrangement), the new arrangement will also be successful, but table will have only people, which contradicts the condition.
Let us give an example satisfying the condition, in which there are exactly pairs of enemies. Divide all people into groups of , 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 enemies, and there are 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 people.