Si $n$ personas se colocan en una habitación, prueban que al menos $2$ de esas personas tendrán el mismo número de amigos en la sala.

Question

Si $n$ personas se colocan en una habitación, entonces al menos $2$ de esas personas tendrán el mismo número de amigos en la sala.

Quiero demostrar esta afirmación.

Estas son algunas de mis reflexiones:

1. Si todas las personas son desconocidas, está claro que todos tienen cero amigos en la sala. Por lo tanto, todos tienen el mismo número de amigos. Por lo tanto, es evidente que existe al menos una pareja en la sala con el mismo número de amigos. Considero que éste es el caso trivial.

2. Tal vez pueda demostrarlo asumiendo que, para cualquier colección de $n$ personas, todas las personas tienen un número diferente de amigos; tal vez entonces pueda encontrar una contradicción.

Siguiendo con la idea de la 2., he ideado la siguiente relación:

$$person #1 has 0 friends, person #2 has 1 friend, person #3 has 2 friends, ... , person (n-1) has (n-2) friends, person n has (n-1) friends$$

Ahora quiero encontrar una manera de utilizar esta relación para demostrar que surge una contradicción, es decir, al menos $2$ las personas deben tener el mismo número de amigos en la sala.

Answer 1

Pista: ¿cuál es el número posible de amigos en la habitación que puede tener cada persona?

Solución completa:

El número de amigos posibles es $n$ son $0,1,2\dots n-1$ . Sin embargo, si hay una persona $A$ con $0$ amigos entonces no puede haber una persona $B$ con $n-1$ amigos, ya que para que eso ocurra $A$ tendría que ser un amigo de $B$ pero $A$ no tiene amigos. Por lo tanto, a lo sumo $n-1$ valores para el número de amigos en la sala. Hay $n$ personas, por lo que, según el principio de encasillamiento, al menos dos personas deben tener el mismo número de amigos.

Answer 2

Asumiendo que la relación de amistad es simétrica, no se puede tener tanto una persona con $0$ amigos y una persona con $n-1$ amigos, ya que el $n-1$ -la persona amiga tiene que ser amiga de todos los demás en la sala, incluida la persona que se supone que tiene $0$ amigos.

Answer 3

Pista: Dibuja un grafo cuyos vértices correspondan a las personas de una habitación, y cuyas aristas correspondan a la amistad entre dos personas. La cuestión se reduce ahora a demostrar que existen dos vértices del mismo grado en un grafo de al menos dos vértices. Para más información, consulte aquí:

http://www.gottfriedville.net/mathprob/graph-samedeg.html

Answer 4

Sugerencia: Principio de encasillamiento.

Argumenta por qué si divides a las personas en una relación que mencionaste por qué no es posible que una persona tenga n amigos (usando la inyectividad de $f: {persons} \rightarrow$ {#amigos de la persona p})

Hay un segundo caso: la persona #1 tiene 1 amigo, ..., la persona #n tiene n amigos. Maneja esto de manera similar.