Grupo bien avenido.

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.

Sobre el autor

Jose

0 0 vote
Article Rating
Subscribe
Notify of
guest
7 Comments
Antiguos
Actuales Más votado
Inline Feedbacks
View all comments
Javier
Javier
20 días hace

Así de golpe… parece que Show ▼

Norberx
Norberx
19 días hace

En un principio Show ▼

Javier
Javier
19 días hace

Chapeau «pal» Norberx 🙂

Mmonchi
Mmonchi
19 días hace

Consigo Show ▼

Mmonchi
Mmonchi
19 días hace

Show ▼

Mmonchi
Mmonchi
19 días hace

Una solución válida para cualquier grupo par mayor que 4: Show ▼