Maths Olympiad Prep

Library / /25 of 29

Combinatorics Difficulty 6.3 National Olympiad Prove it Croatia

At a party among each group of four people there are three that all know each other or three that don't know each other. Acquaintances are mutual. Prove that all the participants at that party can be separated into two rooms so that in one room everybody knows everyone, and in the other room nobody knows anyone.

Solution

People and acquaintances can be represented by a complete graph in two colours, where the vertices represent people, blue edges connect people who know each other, and red edges connect people who don't know each other. We call a set with mm vertices a blue (red) mm-gon if all of the vertices are connected by a blue (red) edge. On the figures, red edges are represented by full lines, and blue edges by dashed lines.

Notice that the given condition implies that the graph contains a red or blue triangle (in the nontrivial cases where the graph has n4n \ge 4 vertices).

Without loss of generality, we can assume that the graph contains a red triangle. Let us observe the largest red kk-gon. Let A={A1,A2,,Ak}\mathcal{A} = \{A_1, A_2, \dots, A_k\} be the set of its vertices. If the remaining nkn-k vertices are all connected by blue edges, we can place the people from A\mathcal{A} in one room and everyone else in the other room, and the problem is solved.

We will show that the other case is not possible. Suppose there exist vertices B,CAB, C \notin \mathcal{A} connected by a red edge. Then there exists ABAA_B \in \mathcal{A} which is connected to BB by a blue edge, because otherwise we would have a red (k+1)(k+1)-gon. Analogously, there exists ACAA_C \in \mathcal{A} which is connected to CC by a blue edge.

Figure 1

We have two possibilities. If ABACA_B \neq A_C, then it is clear (see the left figure above) that no three of the vertices B,C,AB,ACB, C, A_B, A_C can form a monochromatic triangle, which is in contradiction with the initial condition.

On the other hand, suppose AB=AC=AA_B = A_C = A, for some AAA \in \mathcal{A}. Let AAA' \in \mathcal{A} be an arbitrary vertex different from AA. The right figure represents the situation between vertices A,A,BA, A', B and CC. Clearly, in order to have a monochromatic triangle, AA' must be connected to BB and CC by a red edge. So, BB and CC are connected by a red edge, and they are both connected by a red edge with every vertex from A{A}\mathcal{A} \setminus \{A\}. But then (A{A}){B,C}(\mathcal{A} \setminus \{A\}) \cup \{B, C\} is a red (k+1)(k+1)-gon, which is again in contradiction with the maximality of kk.

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.