Partition a group of nine people
by liberator, Apr 10, 2015, 6:43 PM
Problem: In a group of nine people it is not possible to choose four people such that every one knows the three others. Prove that this group of nine people can be partitioned into four groups such that nobody knows anyone from his or her group.
[Bulgarian IMO TST 2005 Problem 6]
My solution (long)
[Bulgarian IMO TST 2005 Problem 6]
My solution (long)
We consider a graph with vertices representing the people. The edge 
is blue when people 
and 
know each other, and red otherwise. The problem is equivalent to showing that the edge-induced subgraph of blue edges in 
is 
-colorable. We start with a lemma.
Lemma. The edges of
are colored red or blue in such a way that there is no blue 
and if 
is the edge-induced subgraph of blue edges, then 
. Then all the red edges of form a cycle of length 
.
Proof. We first claim that under the conditions of the lemma, there is no red
. It is well known that 
(see here for a proof), so there is a monochromatic . Label the vertices of 
. Suppose, for contradiction, that there is a red , which, WLOG, we label 
. If some edge , where 
, is red, then the 
-partition 
, where 
, shows that 
, which is forbidden. Hence 
is a blue . 
.
Hence
, otherwise we would have a blue . Suppose, WLOG, that 
are red. Then 
is a red , so that 
is a blue from . If now 
is blue, then 
is a blue . Otherwise, is red, and we have the -partition 
, so that , and we have our contradiction.
Therefore there is no red, and our claim is true.
We now show that all the red edges of form a cycle of length . WLOG, let 
be red. If all edges , where 
are red, then we have a -partition 
, which is forbidden. Hence, WLOG, let 
be blue. One of the edges in the vertex-induced subgraph 
must be red: WLOG, let this be 
. Then 
is blue (otherwise 
is a red ) and 
is blue (otherwise we have a -partition 
).
If
is red, then 
must be blue and 
is red. Then 
are all blue, so our red edges are 
, which form a cycle of length .
If is blue, then similar arguments produce a contradiction. Thus our proof of the lemma is complete. 
Consider now the complete graph, with vertices 
. It is well known that 
(see here for a proof), and since there is no blue , there must be a red . WLOG, we let 
be the red . If the edge-induced subgraph of blue edges in the vertex-induced subgraph 
is -colorable, then we are done.
Otherwise, from the lemma, we can assume, WLOG, that
are red. For 
, we have four cases depending on how many of the 
are blue.
Case 1. None of the are blue. Then we have the -partition 
.
Case 2. Exactly one of the is blue (WLOG 
). Then at least three of the edges 
, for ![$i \in [1,5]$](//latex.artofproblemsolving.com/f/d/a/fdabbebe31f9e9134b40e7c34cda90f84914c4e6.png)
are red, otherwise we have a blue . WLOG, suppose is red when 
, so that we have a -partition 
.
Case 3. Exactly two of the are blue (WLOG 
). Then as before, for at least three of the and three of the 
are red. We can easily find the desired -partition.
Case 4. All the are blue. By similar arguments to before, we can find a -partition.
Hence the edge-induced subgraph of blue edges in is -colorable, as required.
is blue when people 
and 
know each other, and red otherwise. The problem is equivalent to showing that the edge-induced subgraph of blue edges in 
is 
-colorable. We start with a lemma.Lemma. The edges of
are colored red or blue in such a way that there is no blue 
and if 
is the edge-induced subgraph of blue edges, then 
. Then all the red edges of form a cycle of length 
.Proof. We first claim that under the conditions of the lemma, there is no red
. It is well known that 
(see here for a proof), so there is a monochromatic . Label the vertices of 
. Suppose, for contradiction, that there is a red , which, WLOG, we label 
. If some edge , where 
, is red, then the 
-partition 
, where 
, shows that 
, which is forbidden. Hence 
is a blue . 
.Hence
, otherwise we would have a blue . Suppose, WLOG, that 
are red. Then 
is a red , so that 
is a blue from . If now 
is blue, then 
is a blue . Otherwise, is red, and we have the -partition 
, so that , and we have our contradiction.Therefore there is no red
, and our claim is true.We now show that all the red edges of
form a cycle of length . WLOG, let 
be red. If all edges , where 
are red, then we have a -partition 
, which is forbidden. Hence, WLOG, let 
be blue. One of the edges in the vertex-induced subgraph 
must be red: WLOG, let this be 
. Then 
is blue (otherwise 
is a red ) and 
is blue (otherwise we have a -partition 
).If
is red, then 
must be blue and 
is red. Then 
are all blue, so our red edges are 
, which form a cycle of length .If
is blue, then similar arguments produce a contradiction. Thus our proof of the lemma is complete. 
Consider now the complete graph
, with vertices 
. It is well known that 
(see here for a proof), and since there is no blue , there must be a red . WLOG, we let 
be the red . If the edge-induced subgraph of blue edges in the vertex-induced subgraph 
is -colorable, then we are done.Otherwise, from the lemma, we can assume, WLOG, that
are red. For 
, we have four cases depending on how many of the 
are blue.Case 1. None of the
are blue. Then we have the -partition 
.Case 2. Exactly one of the
is blue (WLOG 
). Then at least three of the edges 
, for ![$i \in [1,5]$](http://latex.artofproblemsolving.com/f/d/a/fdabbebe31f9e9134b40e7c34cda90f84914c4e6.png)
are red, otherwise we have a blue . WLOG, suppose is red when 
, so that we have a -partition 
.Case 3. Exactly two of the
are blue (WLOG 
). Then as before, for at least three of the and three of the 
are red. We can easily find the desired -partition.Case 4. All the
are blue. By similar arguments to before, we can find a -partition.Hence the edge-induced subgraph of blue edges in
is -colorable, as required.
October 2018
April 2018