Maths Olympiad Prep

Library / /67 of 136

, 1997

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

Define a kk-clique to be a set of kk people such that every pair of them know each other (knowing is mutual). At a certain party, there are two or more 33-cliques, but no 55-clique. Every pair of 33-cliques has at least one person in common. Prove that there exists at least one, and not more than two persons at the party, whose departure (or simultaneous departure) leaves no 33-clique remaining.

Solution

We consider two cases.

Case 1. There exist two 33-cliques sharing two common people.
Suppose the two 33-cliques are {A,B,C}\{A, B, C\} and {A,B,D}\{A, B, D\}. If all 33-cliques contain AA or BB, we are done as we can remove AA and BB. If there exists a 33-clique without AA and BB, it must be {C,D,E}\{C, D, E\} since every pair of 33-cliques has a common person. We claim that there is no 33-clique if CC and DD are removed.
Indeed, note that {A,C,D}\{A, C, D\}, {B,C,D}\{B, C, D\} and {C,D,E}\{C, D, E\} are existing 33-cliques since all pairs of people in these 33-cliques know each other from above. Therefore, the only possible 33-clique without CC and DD is {A,B,E}\{A, B, E\}. Then {A,B,C,D,E}\{A, B, C, D, E\} forms a 55-clique, which is a contradiction.

Case 2. Any pair of 33-cliques shares exactly one common person.
Suppose two 33-cliques are {A,B,C}\{A, B, C\} and {A,D,E}\{A, D, E\}. If all 33-cliques contain AA, we are done as we can remove AA. If there exists a 33-clique without AA, it must be {B,D,F}\{B, D, F\} up to renaming of the people. Then we have a 33-clique {A,B,D}\{A, B, D\} sharing two common people with {A,B,C}\{A, B, C\}. This is a contradiction.
The proof is complete since all cases are covered.

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.