Maths Olympiad Prep

Library / /9 of 13

, 2015

Combinatorics Difficulty 8.1 Shortlist Prove it Baltic Way

In the parliament of Neverland, all legislative work is carried out in committees of three people. The constitution dictates that any four people can be in at most two committees. We call a collection of committees a clique if any two of them have exactly two people in common, and any manner of including another committee in the collection would break this condition. Prove that two different cliques cannot have two committees in common.

Solutions — 2

Solution 1

It is easy to see that, given three different committees, each pair of them can have two people in common only if all three committees share the same two people, for otherwise the people in the committees would contain four people from whom three committees have been formed. As a corollary, for any clique, there are some two people who belong to all the committees in the clique, and these people are unique.
To derive a contradiction, let us consider two cliques C1C_1 and C2C_2 with two committees in common. There are some two people AA and BB who belong to all the committees in C1C_1. These two people must also belong to the two committees shared by C1C_1 and C2C_2. But then all the committees in C2C_2 must also include AA and BB. Now, we can extend the clique C1C_1 into C1C2C_1 \cup C_2, which violates the definition of a clique. □

Solution 2

Consider three committees in a clique. As above, each pair of them can have two people in common only if all three of them share the same two people. Therefore, all committees in a clique share the same two people, and the clique with intersection {A,B}\{A, B\} consists, by maximality, of all possible committees
{A,B,P1},,{A,B,Pn}. \{A, B, P_1\}, \dots, \{A, B, P_n\}.
The clique is thus uniquely determined by the intersection of any two of its elements. □

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.