In a party with $1982$ persons, among any group of four there is at least one person who knows each of the other three. What is the minimum number of people in the party who know everyone else?
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, combinatorics unsolved, combinatorics
23.09.2011 19:40
Mrdavid445 wrote: In a party with $1982$ persons, among any group of four there is at least one person who knows each of the other three. What is the minimum number of people in the party who know everyone else. problem from Russian Saint Peterburg olympiad
23.09.2011 22:58
Let the graph $G(V,E)$ have $n$ vertices. If there exists a vertex $u$ such that $\deg u \leq n-3$, let $v,w$ be such that $uv, uw \not \in E$. Then for any other vertex $z$, considering $\{z,u,v,w\}$ implies $zu,zv,zw \in E$. Moreover, for any other vertices $x,y$, considering $\{x,y,u,v\}$ implies $xy \in E$. Therefore $G - \{u,v,w\} = K_{n-3}$, and this is a viable model. So assume $\deg u \geq n-2$ for all $u$. If there is one with $\deg u = n-2$, let $v$ be the (only) vertex with $uv \not \in E$; it follows that also $\deg v = n-2$, so for any other vertex $z$ we must have $zu,zv \in E$. Moreover, for any other vertices $x,y$, considering $\{x,y,u,v\}$ implies $xy \in E$. Therefore $G - \{u,v,\} = K_{n-2}$, and this is a viable model. Finally, if $\deg u = n-1$ for all $u$, that means $G = K_n$. The first model provides the minimum number of vertices connected to all other, namely $n-3$.