El problema: hay una clase. En cada grupo de tres estudiantes en la clase hay un par de amigos y un par de "enemigos". Encuentra el número máximo de estudiantes en la clase.
Intenté jugar con combinatoria, para encontrar números de pares y trillizos. También se tuvo la idea de asignar 0 (enemigos) o 1 (amigos) a cada pareja e intentar limitar las sumas de pares y trillizos utilizando esta medida. No funciono ¿Alguien tiene una idea de cómo resolverlo?
Pretendemos que en una clase de $6$ a los estudiantes, uno siempre puede encontrar $3$ a las personas que vienen de a pares amigos de pares enemigos.
Deje $v_1, \ldots, v_6$ ser todas las personas en la clase. De las cinco personas $v_2, \ldots, v_6$, al menos $3$ de ellas tienen los mismos sentimientos hacia a $v_1$, es decir, cualquiera de las tres son los enemigos o los tres son amigos de $v_1$.
Digamos, sin pérdida de generalidad, que el $v_2, v_3$ $v_4$ tiene el mismo sentimiento hacia la $v_1$, y asume, de nuevo sin pérdida de generalidad, que este sentimiento es el de la amistad.
Tenga en cuenta que si $v_2$ es amigos con $v_3$ $v_1, v_2$ $v_3$ son tres las personas que son pares de amigos y hemos terminado.
Así que podemos suponer que la $v_2$ $v_3$ son enemigos. Del mismo modo, podemos suponer que la $v_2$ $v_4$ son enemigos, y $v_3$ $v_4$ son enemigos.
Pero, a continuación, $v_2, v_3$ $v_4$ son tres las personas que son pares de enemigos y de nuevo tenemos que hacer.
Así vemos que, tan pronto como el tamaño de la clase llega a $6$, la condición requerida en la pregunta no puede ser satisfecho. Por lo tanto, pueden ser atmost $5$ a los estudiantes en una clase. Uno puede construir fácilmente un ejemplo a mano donde una clase de tamaño de cinco satisface las condiciones requeridas para el máximo tamaño de la clase es $5$.
En la discusión anterior, hemos supone implícitamente que la amistad y la enemistad son mutua entre dos personas, y también que dadas dos personas, ellos son amigos o enemigos, pero no tanto.
Modele el grupo como un gráfico completo, donde cada línea entre estudiantes es azul (amigo) o roja (enemigo).
El número Ramsey $R(3,3)$ es igual a 6. Esto ya le da un límite superior, si lo piensa.
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.
