Maths Olympiad Prep

Library / /92 of 104

Combinatorics Difficulty 6.9 National Olympiad Prove it Bulgaria

Problem:

In a group of 9 persons it is not possible to choose 4 persons such that every one knows the three others. Prove that this group of 9 persons can be partitioned into four parts in such a way that nobody knows anyone from his part.

Emil Kolev

Solution

Solution:

We have to prove that if the edges of a complete graph with 9 vertices are colored in blue and red in such a way that there is no blue quadrilateral then its vertices can be partitioned into 4 groups without any blue edges inside any group.

Lemma 1. The edges of a complete graph with 6 vertices are colored in blue and red in such a way that there is no blue quadrilateral and its vertices can not be partitioned into 3 groups without blue edges inside any group. Then the graph does not contain a red triangle.

Proof. It is well known that the complete graph with 6 vertices and edges colored in two colors (red and blue) has an one-colored triangle. Denote the vertices of the graph by v1,v2,,v6v_{1}, v_{2}, \ldots, v_{6} and assume the existence of a red triangle v1v2v3v_{1} v_{2} v_{3}. If some edge vivj,i,j{4,5,6}v_{i} v_{j}, i, j \in\{4,5,6\}, is red, then {v1,v2,v3},{vi,vj}\{v_{1}, v_{2}, v_{3}\},\{v_{i}, v_{j}\} and {vk},k1,2,3,i,j\{v_{k}\}, k \neq 1,2,3, i, j, is a partition which is supposed not to exist.
Therefore v4v5v6v_{4} v_{5} v_{6} is a blue triangle. Now the condition implies that for every i=1,2,3i=1,2,3 at least one of the edges vivj,j=4,5,6v_{i} v_{j}, j=4,5,6, is red. If the edges v1v4v_{1} v_{4} and v2v4v_{2} v_{4} are red then v1v2v4v_{1} v_{2} v_{4} is a red triangle and, as above, v3v5v6v_{3} v_{5} v_{6} is a blue triangle. Now, if the edge v3v4v_{3} v_{4} is blue, then v3v4v5v6v_{3} v_{4} v_{5} v_{6} is a blue quadrilateral and, if the edge v3v4v_{3} v_{4} is red, then we have the partition {v1,v2,v3,v4},{v5}\{v_{1}, v_{2}, v_{3}, v_{4}\},\{v_{5}\} and {v6}\{v_{6}\}, a contradiction, which completes the proof of the lemma.

Lemma 2. Under the conditions of Lemma 1 all red edges of GG form a cycle of length 5.

Proof. We know from Lemma 1 that GG does not contain a red triangle.
Without loss of generality we can assume that the edges v1v2v_{1} v_{2} and v3v4v_{3} v_{4} are red. If all edges vivjv_{i} v_{j} for i=1,2,j=3,4i=1,2, j=3,4 are red, then the partition {v1,v2,v3,v4},{v5}\{v_{1}, v_{2}, v_{3}, v_{4}\},\{v_{5}\} and {v6}\{v_{6}\} ensures a contradiction. So, let v2v4v_{2} v_{4} be blue. Since the quadrilateral v2v4v5v6v_{2} v_{4} v_{5} v_{6} can not be blue, we may assume without loss of generality that the edge v4v6v_{4} v_{6} is red. Now v3v6v_{3} v_{6} is blue (otherwise v3v4v6v_{3} v_{4} v_{6} is a red triangle) and v3v5v_{3} v_{5} is blue (otherwise we have the partition {v1,v2},{v3,v5}\{v_{1}, v_{2}\},\{v_{3}, v_{5}\} and {v4,v6}\{v_{4}, v_{6}\} for a contradiction).
If the edge v1v3v_{1} v_{3} is red then using the conditions of the problem we see that the edge v2v5v_{2} v_{5} is blue, the edge v2v6v_{2} v_{6} is red and the edges v1v6,v1v5,v4v5v_{1} v_{6}, v_{1} v_{5}, v_{4} v_{5} and v1v4v_{1} v_{4} are blue. We finally conclude that the red edges in GG are v1v2,v2v6,v6v4v_{1} v_{2}, v_{2} v_{6}, v_{6} v_{4}, v4v3v_{4} v_{3} and v3v1v_{3} v_{1} and they form a cycle of length 5 as desired.
If the edge v1v3v_{1} v_{3} is blue, then similar arguments lead to a contradiction. This completes the proof of the lemma.

Let us now consider a graph with 9 vertices v1,v2,,v9v_{1}, v_{2}, \ldots, v_{9}, satisfying the given conditions. It is known that such a graph contains a red triangle or a blue quadrilateral. Since the latter is impossible we have a red triangle v7v8v9v_{7} v_{8} v_{9}, say. If the induced graph v1v6v_{1} \ldots v_{6} can be divided into three groups without blue edges inside any group then we obtain the required division of GG.
Otherwise Lemma 2 implies that we may assume without loss of generality that the edges v1v2,v2v3,v3v4,v4v5v_{1} v_{2}, v_{2} v_{3}, v_{3} v_{4}, v_{4} v_{5} and v5v1v_{5} v_{1} are red.
If the edges viv6,i=7,8,9v_{i} v_{6}, i=7,8,9, are red then {v6,v7,v8,v9},{v1,v3},{v2,v4}\{v_{6}, v_{7}, v_{8}, v_{9}\},\{v_{1}, v_{3}\},\{v_{2}, v_{4}\} and {v5}\{v_{5}\} is the desired division. If the edge v7v6v_{7} v_{6} is blue while the edges v8v6v_{8} v_{6} and v9v6v_{9} v_{6} are red then at least three of the edges v7vi,i=1,2,,5v_{7} v_{i}, i=1,2, \ldots, 5, are red and we easily have the desired division (otherwise we get a red quadrilateral).
Similar arguments solve the two remaining cases: when two of the edges v6v7,v6v8v_{6} v_{7}, v_{6} v_{8} and v6v9v_{6} v_{9} are blue and one is red, and when all of them are blue.

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.