Demostrar que en una fiesta de $25$ de las personas hay una persona sabe al menos doce personas.

Question

Así, el pleno del problema va como esto:

Hay $25$ de la gente en una fiesta. Suponiendo que entre cualquiera de las tres personas, al menos dos de ellos saben el uno del otro, demostrar que existe una persona que debe saber al menos doce personas.

He estado atrapado en este problema por un tiempo y no he descubierto la manera de proceder. Estoy bastante seguro de que hay una respuesta que puede ser encontrado a través del principio del palomar o algunos de teoría de grafos, pero no estoy muy seguro de cómo empezar. Cualquier ayuda se agradece.

Answer 1

Si todo el mundo sabe todo el mundo, luego de que termines.

De lo contrario elija dos personas, A y B decir, que no conocen. Estas dos personas forman parte de $23$ triples. En cada uno de estos triples, A sabe a la tercera persona, o B sabe a la tercera persona.

Así uno de la A o B sabe (al menos) $12$ de las personas.

Answer 2

Elige un vértice $v$. Si $\deg(v) \geq 12$ está hecho.

De lo contrario, $v$ está conectado con un máximo de 11 vértices. Deje $C$ ser los vértices conectados a $v$ $N$ ser los vértices no está conectado a $v$. Tenga en cuenta que $N$ tiene al menos $13$ vértices.

Fijar un vértice $u \in N$.

Ahora, para cada una de las $w \in N$ buscar en el grupo $\{ u, v, w\}$. La única posible ventaja en este grupo es $uw$. Por lo tanto, $uw \in E(G)$.

Esto demuestra que $u$ está conectado a todos los otros vértices en $N$.

La nota de La prueba es básicamente el siguiente:

La condición dada demuestra que, si se fijan un vértice $v$, y la mirada a todos los vértices $N$ que no están conectados a $v$, entonces la inducida por el gráfico de $N$ es el grafo completo.

Así que si $|N| \geq 13$ está hecho, de lo contrario $|N| \leq 12$, lo que significa $\deg(v) \geq 12$.

Answer 3

Esto podría hacerse también la chimenea – Turán teorema:

El número máximo de los bordes de un gráfico triángulo-libre de $n$-vértice es ${\displaystyle \lfloor n^{2}/4\rfloor .}$

Que $G$ ser un grafo con vértices de $25$ y conectar dos Foro de personas que no conocen. Supongo que nadie sabe %#% de #% las personas, entonces el grado de cada vértice es al menos $12$ y el número de todos los bordes es $13$ donde

$\varepsilon$$

Pero ya que este gráfico es triángulo libre $$ 2\varepsilon = \sum _{i=1}^{25} d_i \geq 25\cdot 13 \Rightarrow \varepsilon \geq {25\cdot 26\over 4}$. Una contradicción.

Answer 4

De la prueba.

Elegir dos personas $P_1$ y $P_2$ que no saben entre sí (si no puedes, hemos terminado de todos modos). Ahora cualquier tercera persona $P$ sabe o $P_1$ o $P_2$, porque $\{P,P_1,P_2\}$ forma un grupo de tres personas y $\{P_1,P_2\}$ no puede ser el par conocerse. Hay tal otra personas $23$ $P$. Así que por el principio de pidgeonhole de $P_1$ y $P_2$ deben saber al menos $\lceil 23/2\rceil=12$ de ellos. $\quad\square$

Answer 5

Que $u$ sea una persona que conoce la mayoría de las personas (puede haber varios tales personas). Esta persona es parte de $\binom{24}{2}$ triples en cada uno de los cuales hay al menos un borde; cada tal borde aumenta el grado de un vértice. Así $\deg u\ge \binom{24}{2}/25 > 11$, por lo que concluimos que $u$ sabe por lo menos $12$ de las personas.