Existen $2n+1$ personas. Para cada $n$ personas hay alguien que es amigo de cada una de ellas. Demuestra que hay una persona que "lo sabe todo".

Question

Tengo el siguiente problema.

Existen $2n+1$ gente en la sala. Para cualquier grupo de $n$ personas hay una persona (distinta de ellos) que es amiga de cada persona de este grupo. Demostrar que hay una persona, que conoce a todos $2n$ otras personas.

Es fácil ver que $\min_v \deg v = n$ . De aquí podemos obtener un límite inferior para el número de aristas $N_e$ : $$ N_e = \frac{1}{2}\sum_v \deg v \geq \frac{(2n+1) \cdot n}{2} $$ No sé hacia dónde moverme desde este punto (y no creo, que esta sea la dirección correcta) y bastante atascado en este momento. ¿Me puede dar una pista?

Answer 1

Digamos que un grupo $M$ est bien si todos en $M$ conoce a todo el mundo en $M$ . Obsérvese que dicho grupo existe (digamos con $2$ personas).

Tomar subgrupo bueno maximal $M$ . Si el tamaño de este grupo $M$ est $k\leq n$ entonces hay alguien que las conoce todas. Así que podemos añadirlo a este grupo y obtenemos nuevo buen grupo $M'$ que es mayor que $M$ . Una contradicción. Así que $M$ es de tamaño $k\geq n+1$ . Entonces en $M^C$ tenemos como máximo $n$ gente, así que hay alguien en $M$ que conocen a todo el mundo en $M^C$ . Pero este conoce a todo el mundo.

Answer 2

Transforma el problema a teoría de grafos y mira el complemento del grafo y usa la contradicción.

Tenemos un gráfico con $2n+1$ vértices en los que cada vértice tiene al menos un grado $1$ y debemos demostrar que podemos dividirnos en grupos de tamaño $n$ y $n+1$ tal que cada vértice del grupo de tamaño $n+1$ tiene una ventaja sobre el otro tamaño.

Esto está claro, toma una bipartición de cualquier spanning forest (que respete componentes) del grafo, y después empuja algunos vértices de la parte mayor a la menor para que los lados tengan el tamaño deseado.

Answer 3

Transforma el problema a la teoría de grafos y deja que $S$ sea el conjunto de $n$ vértices con la menor cantidad de aristas saliendo. Sea $v$ sea un vértice conectado a cada vértice de $S$ y observe que si $v$ no está conectado a ninguno de los otros $n$ vértices, entonces el conjunto de los otros $n$ vértices tiene menos aristas saliendo.