Nueva semana y nuevo problema de la Olimpiada Matemática Internacional (IMO, según sus siglas en inglés). Hoy es el turno del tercero de los seis problemas que se han propuesto en la de este año 2019, celebrada en Bath (Reino Unido).

Ahí va:

Una red social tiene 2019 usuarios, algunos de los cuales son amigos. Siempre que el usuario A es amigo del usuario B, el usuario B es amigo del usuario A. Eventos del siguiente tipo pueden ocurrir repetidamente, uno a la vez:

  • Tres usuarios A, B y C tales que A es amigo de B y de C pero B y C no son amigos, cambian su estado de amistad, de modo que B y C ahora son amigos pero A ya no es amigo ni de B ni de C. Las otras relaciones de amistad no cambian.

Inicialmente hay 1010 usuarios que tienen 1009 amigos cada uno, y hay 1009 usuarios que tienen 1010 amigos cada uno. Demostrar que hay una sucesión de este tipo de eventos después de la cual cada usuario es amigo como máximo de uno de los otros usuarios.

A por él.


Recuerdo que la idea de publicar estos problemas es que los intentemos resolver nosotros, no que alguien busque la solución en internet y la copie aquí. Confío en vuestro buen criterio en este sentido.

Print Friendly, PDF & Email