preguntas centradas en el principio de encasillamiento

Question

Ayer nos dieron un par de preguntas de principio de encasillamiento, yo resolví la mayoría pero estas 3 no pude, no sé ni por dónde empezar.

1) 20 personas están sentadas alrededor de una mesa redonda, sobre ella hay una gran pizza (20 porciones) 10 de ellas con aceitunas y 10 sin ellas, a algunas de las personas les gusta la pizza con aceitunas mientras que a otras no, demuestre que se puede rotar la pizza de tal manera que al menos la mitad de las personas (al menos 10) estén contentas?

2) Dado un grafo con 6 vértices demostrar que hay al menos 3 vértices que no tienen ninguna arista entre cada dos de ellos o que todos están conectados ?

3) Dado $x \in \mathbb{R}$ y $x \not \in \mathbb{Q}$ demostrar que para todo $\epsilon >0$ hay $n>0$ tal que $\{ n x \} < \epsilon$ ?

cualquier ayuda es apreciada, incluso si usted sabe cómo resolver una pregunta, por favor, deje un comentario que me muestra cómo probarlo, o publicar una respuesta,

Gracias.

Answer 1

2:

Este problema se puede retocar para que sea así: En lugar de considerar la ausencia de borde frente a la existencia de un borde, considere $K_6$ (el gráfico completo de 6 vértices) tal que cada arista tiene un color. Una arista roja corresponde a las aristas del grafo que queremos considerar conectadas, y una arista azul significa que esos vértices no tienen arista. Buscamos demostrar que hay al menos un triángulo rojo o uno azul.

Consideremos un vértice arbitrario $v$ . Por el principio de casillero generalizado, el vértice $v$ debe tener al menos 3 aristas del mismo color, WLOG dice que tiene 3 aristas rojas, además conecta esas aristas a los vértices $a,b$ y $c$ . Para evitar un triángulo monocromático, los bordes $\{a,b\}$ y $\{b,c\}$ debe ser azul.

Pero no importa la elección del borde de color para $\{a,c\}$ se obtiene un triángulo monocromático (un triángulo rojo en $v,a,c$ o un triángulo azul en $a,b,c$ , lo que lleva a la situación descrita (tres vértices todos conectados o tres vértices sin arista entre ellos).