The director has found out that six conspiracies have been set up in his department, each of them involving exactly $3$ persons. Prove that the director can split the department in two laboratories so that none of the conspirative groups is entirely in the same laboratory.
Problem
Source: baltic way, 2006
Tags: induction, combinatorics proposed, combinatorics
12.01.2011 19:42
Let us notice that $6$ is the best possible - the claim is no longer true for $7$ conspiracies (look at the $7$ "lines" of the Fano projective plane, on $7$ points). The proof for $6$ is quite convoluted - I do possess one, made of cute little steps, but it's too much to write down, so this is just to certify the claim is correct.
12.01.2011 21:05
It's quite easy but like mavropnevma said it's a bit too long. If you look at it like a graph we have a number of components. Each component consists of a few linked conspiracies. So if we prove that it is possible to do this in each component then we're done. We use induction on the number of conspiracies linked in one component. When a conspiracy is linked to the component it's done in either of these three ways: 1. By adding 2 new persons 2. By adding 1 new person 3. By adding 0 person to the component and linking two persons that only have one neighbour in common.( We use the number 6 here )
13.01.2011 10:29
It's not so hard to observe that if $n$ (the number of persons) is less than $7$, the conclusion follows. If $n \geq 7$, use induction. Observe that for $n \geq 7$, there are at least two persons who are not involved in the same conspiracy. Let $x_1$ and $x_2$ be those persons. Now, if we consider $(x_1, x_2)$ as a single person and apply the induction hypothesis, we are done.
13.01.2011 15:05
Indeed, we must have $n\geq 5$, since $\binom {4} {3} = 3 < 6$. For $n=5$, we have $\binom {5} {3} = 10 > 6$, so we can split into a laboratory of $3$ which is not a conspiracy, and the remaining $2$. For $n=6$, we have $\binom {6} {3} = 20$ possible triplets, i.e. $10$ pairs $(T,\overline{T})$; since there are $6$ conspiracies, there must exist such a pair free of conspiracies.
10.11.2011 06:14
just a few discussions will do. it suffices to discuss whether $n\le 5$ or $n\ge 6$ the former one is trivial;the latter one can be proved by Fubini principle.