En una clase hay 20 estudiantes y cada estudiante odia exactamente a 3 otros estudiantes en la clase y este sentimiento es recíproco (Si X odia a Y, Y también odia a X).
El director quiere convocar a algunos de los estudiantes de esta clase e intenta que no haya ningún alumno que se odie en el grupo.
¿Cuál podría ser el número máximo de estudiantes convocados por el director?
Por ejemplo, supongamos que hay 6 estudiantes en la clase con el siguiente esquema de odio:
A odia a B, C, D
B odia a A, C, E
C odia a A, B, F
D odia a A, E, F
E odia a B, D, F
F odia C, D, E
entonces, si el director llamó a A, resulta que B, C, D no pueden estar en este grupo, entonces E podría ser el otro estudiante, y dado que E también odia a F, solo podría haber 2 personas en esta configuración.
Debes encontrar la configuración que permita un mayor número de alumnos en el grupo formado por el director.
Así de golpe… parece que [spoiler] 5 [/spoiler]
En un principio [spoiler]encuentro un caso con 8, pero fácilmente podrían existir mejores casos.[/spoiler]
Chapeau «pal» Norberx 🙂
Consigo [spoiler]9, pero ha sido probando, así que puede haber alguna mejor.[/spoiler]
[spoiler]10. Debería ser el máximo.[/spoiler]
Una solución válida para cualquier grupo par mayor que 4: [spoiler]
1(11,12,13)
2(11,12,14)
3(11,13,15)
4(12,14,16)
5(13,15,17)
6(14,16,18)
7(15,17,19)
8(16,18,20)
9(17,19,20)
10(18,19,20)
Los otros diez son recíprocos.[/spoiler]
Sí, 10 es el máximo.
3 (20 − n) ≥3n