Vamos a tener una fiesta. Tenemos 100 amigos. Y todos ellos tienen exactamente 3 amigos en ese grupo de 100 personas. Pero no sabemos quién es el amigo con quien. Y en nuestro partido tiene que haber al menos 2 personas que es amigo con los demás. Cuántas personas que invitamos para asegurarse que va a ser al menos 2 amigos.
Me han estado buscando respuesta y encontré con teoría de Ramsey y casillero. Pero no pude introducir mis datos para ellos.
Podemos pensar en una amistad gráfico. Los vértices son los $100$ personas y las aristas representan un par de amigos. Estoy suponiendo que la amistad es mutua, que si C es amigos con D, por lo que es D amigos con C. Nos dice que es un cúbicos gráfico, lo que significa que cada vértice tiene tres bordes conectados a él. Puede convertir el problema en torno al invitar a todo el mundo, luego de la eliminación de personas de la sala y pregunta cuál es el número máximo de personas que puede quitar y la garantía de que hay dos vértices conectados por una arista que todavía están en la habitación.
El total de grados de la gráfica es $300$, por tanto, por el lema del apretón de manos hay $150$ bordes. Cuando se retire una persona que eliminar en la mayoría de los tres bordes. Podría ser menos si ya hemos eliminado uno o más bordes de la última persona que quitar. Esta muestra $n$ no puede ser mayor que $51$ porque si quitamos a menos de $50$ de las personas no debe ser algunos de los bordes de la izquierda.
Para mostrar $n=51$ podemos describir un gráfico que soporta. Dividir a la gente en grupos $A$ $B$ y el número de personas en cada grupo de$1$$50$. Cada persona es amigos con la persona número uno por encima de ellos y un número por debajo de ellos en su propio grupo (alrededor de ajuste en la final) y con el número correspondiente de la persona en el otro grupo, por lo $A25$ es amigos con $A24, A26, B25$. Ahora podemos invitar a todos los impares a la gente de grupo $A$ y todos los pares de la gente de grupo $B$, de un total de $50$ y no tienen ningún par de amigos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
