Demostrar que en un grupo de 60 personas siempre se pueden encontrar dos personas con número par de conocidos comunes.
Sólo quiero una pequeña sugerencia para este problema, no una solución completa.
Respuesta
¿Demasiados anuncios?
He tratado de dar una simple sugerencia, pero las cosas se pusieron complicadas, así que hay varias sugerencias, y la solución se divide en dos partes (con lo que se puede comprobar que uno de ellos si usted está atascado de nuevo).
Sugerencia 1:
Demostrar que en un grupo de $2n$ no existen dos personas con un número de conocidos comunes.
Sugerencia 2:
Asumir que cualquier pareja tiene número impar de conocidos comunes y la prueba de que todo el mundo tiene un número par de amigos.
La solución de la parte I:
Denotar por $F(x)$ el conjunto de amigos de $x$. Suponga que $$\forall x \neq y.\ \big|F(x) \cap F(y)\big| \text{ is odd}. \tag{$\spadesuit$}$$ Observar que $\sum_{y \in F(x)} |F(x) \cap F(y)|$ es aún, debido a que $z \in F(y)$ implica $y \in F(z)$ (en la suma de ambos son conocidos de $x$). Sin embargo, por $(\spadesuit)$ sabemos que cada intersección es de tamaño impar y por lo $|F(x)|$ es incluso.
Sugerencia 3:
Demostrar que en un grupo de $2n$ para cualquier persona existen otro de esos que comparten un número par de conocidos.
Sugerencia 4:
Considere la posibilidad de $$\sum_{y \in F(x)} \big|F(y) \setminus \{x\}\big|$$ and change the summation order (now you sum people other than $x$ by friends of $x$, try to sum friends of $x$ per each person other than $x$).
La solución de la parte II:
Considere la posibilidad de $$\sum_{y \in F(x)} \big|F(y) \setminus \{x\}\big|.$$ Incluso, debido a $|F(x)|$ es incluso y $|F(y)\setminus \{x\}|$ es impar. Este se mantiene fiel cuando cambiamos la suma fin $$ \sum_{z \neq x} \Big|\big\{y \in F(x)\ \big|\ z \in F(y) \big\}\Big| = \sum_{z \neq x} \Big|F(x) \cap F(z)\Big|, $$ pero por $(\spadesuit)$ la suma de $2n-1$ elementos de la extraña tamaño tiene que ser impar, contradicción. $\blacksquare$
Espero que esto ayude a $\ddot\smile$
