$8$ people participate in a party. (1) Among any $5$ people there are $3$ who pairwise know each other. Prove that there are $4$ people who paiwise know each other. (2) If Among any $6$ people there are $3$ who pairwise know each other, then can we find $4$ people who pairwise know each other?
Problem
Source: CGMO 2006
Tags: combinatorics unsolved, combinatorics
11.08.2006 17:43
who can solve it?
12.08.2006 00:25
Well it's not hard to come up with a counterexample for (2): just take the vertices (=people) of a regular octagon, join the sides, and segments skipping 1 vertex. Removing 2 vertices still guarantees a triangle but there is no K_4... haven't finished (1) yet though
12.08.2006 17:17
I think this may work for the first part
10.08.2019 22:21
Here is a solution for $(1)$. Inspired by the fact that $4$ is half of $8$, we decide to use the funny trick of showing that the complement of the graph is bipartite. Actually, this is not true, but fortunately the cases where the complement is not bipartite are easy to deal with. So, supposing that the complement wasn't bipartite, we have three cases. Case $1$: There is a triangle. Then, there exist three people $A, B, C$, who are pairwise unacquainted. Now, for any two other people $D$ and $E$, by applying the condition on $(A, B, C, D, E)$ it is apparent that $D$ and $E$ are acquainted with each other. Therefore, we conclude that all of the other five people are pairwise acquainted, and so taking any $4$ of them yields the conclusion. Case $2$: There is a $5$-cycle. Then, there exist five people $A, B, C, D, E$ such that $A$ is not acquainted with $B$, $B$ is not acquainted with $C$, $C$ is not acquainted with $D$, $D$ is not acquainted with $E$, and $E$ is not acquainted with $A.$ However, applying the condition of the problem on $(A, B, C, D, E)$ yields a clear contradiction. Hence, this case is absurd and can be disposed of. Case $3$: There is a $7$-cycle. Let $A_1, A_2, \cdots, A_7$ be seven people such that $A_i$ is unacquainted with $A_{i+1}$ for each $1 \le i \le 7$, with indices modulo $7.$ By applying the condition on $(A_i, A_{i+1}, A_{i+2}, A_{i+3}, A_{i+4})$, it's clear that the triple of pairwise acquainted people must be $(A_i, A_{i+2}, A_{i+4}).$ This yields that $A_i, A_{i+2}$ are acquainted for each $i$, and so are $A_i, A_{i+4}.$ In particular, we know that $A_i$ and $A_j$ are acquainted if and only if $j \neq i, i \pm 1.$ Consider now the other person $V.$ We claim that $V$ must be acquainted with at least $5$ people among the $A_i$'s. Call a person $A_i$ good if he/she is acquainted with $V$, and bad otherwise. We desire to show that at most two people are bad. Observe that if $A_i, A_{i+3}$ are both bad, then applying the condition on $(A_i, A_{i+1}, A_{i+2}, A_{i+3}, V)$ yields a contradiction. Therefore, for each $i$ we know that one of $A_i, A_{i+3}$ is good. This immediately yields that at most half of the people are bad, so $\le 3$. Furthermore, if there are actually three people who are bad, some simple casework using the fact that one of $A_i, A_{i+3}$ is good yields that they must be $A_i, A_{i+1},$ and $A_{i+2}$ for some $1 \le i \le 7.$ However, in this case applying the condition on $(V, A_i, A_{i+1}, A_{i+2}, A_{i+3})$ yields a contradiction. Hence, we obtain that there are at most $2$ bad people. As a result, we know that there exists some $1 \le i \le 7$ such that $A_i, A_{i+2}, A_{i+4}$ are all good, because $2 < \frac{7}{3}.$ From here, we conclude that $(V, A_i, A_{i+2}, A_{i+4})$. As we've exhausted all cases, we have resolved the problem in the case where the complement graph is not bipartite. If the complement graph is actually bipartite, then we are done by a simple application of Pigeonhole. $\square$