Maths Olympiad Prep

Library / /2 of 4

Combinatorics Difficulty 6.2 National Olympiad Prove it Baltic Way

In a party of eight persons, each pair of persons either know each other or do not know each other. Each person knows exactly two of the other people.

Is the following situation possible: (i) no three persons know each other but (ii) there are no four persons such that no two of these know each other?

Solution

Figure 1

As each person in the party is acquainted to three others, the number of acquaintance relations must be 1283=12\frac{1}{2} \cdot 8 \cdot 3 = 12. Assume AA is one of the persons in the party. Denote by BB, CC and DD the three persons AA knows. To meet condition (i), none of BB, CC and DD know each other. So each of them has to know two persons in the set S={E,F,G,H}S = \{E, F, G, H\}. Up to now, we have used 9 acquaintances, so there are exactly 3 acquaintance relations between members SS. Again, no three persons in SS are to know each other. On the other hand, if one of the persons, say EE, is acquainted to all three others, FF, GG and HH, the set {A,F,G,H}\{A, F, G, H\} would violate condition (ii). So the only possibility is that the acquaintance relations are arranged in a linear manner: we may name the persons in such a manner that EE knows FF, FF knows GG and GG knows HH. Now EE knows exactly two persons in the set T={B,C,D}T = \{B, C, D\}. We may assume that they are BB and CC. FF knows exactly one person in the set TT and this person must be DD. GG cannot be acquainted with DD, so his acquaintance in TT is either BB or CC. If it is BB, then CC and DD can be the acquaintances of HH, and if it is CC, then HH can be acquainted to BB and DD. In fact, we can always name the members in TT to conform with the former alternative.

The construction has provided an arrangement consistent with (i); to see that (ii) is fulfilled, we just need to check for each member that among the four members not acquainted to the first one, there is at least one pair of acquaintances. Indeed: for AA such a pair is (EE, FF), for BB, (CC, HH), for CC, (DD, FF), for DD, (CC, EE), for EE, (AA, DD), for FF, (AA, CC), for GG, (AA, DD) and for HH, (AA, BB). – We note that there is essentially one solution, up to a renaming of the members.

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.