Solución a “El collar de perlas”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10 
Autor: 
Félix Rafael Horta Cuadrilla

En una bosque habitan dos clanes de enanos: los enanos rojos y los enanos verdes. Durante sus expediciones en las cuevas cercanas, un grupo de enanos rojos y verdes encontraron un collar formado por perlas blancas y negras que no tienen ningun valor, pero al final del collar hay un valioso diamante. Los dos clanes de enanos quieren apoderarse del diamante.

Para resolver el problema de manera pacifica deciden jugar el siguiente juego: a cada uno de los N enanos se le asigna un numero del 1 al N (un numero diferente para cada enano) y dos listas de numeros, una negra y una blanca (las listas pueden ser diferentes entre si). Cada lista contiene una cantidad diferente de numeros, cada numero i en cualquier lista representa al enano i.

Durante el juego, el collar se pasa de un enano a otro de acuerdo con las siguientes reglas: cuando un enano recibe el collar, el quita la primer perla en el collar y si la perla es blanca, entonces pasa lo que quedo del collar a cualquier enano que este en su lista blanca (al que el quiera), pero si la piedra es negra, entonces pasa lo que quedo del collar a algun enano de su lista negra. Para empezar el juego, el collar se le da a un enano aleatoriamente.

En algun momento el collar solamente va a tener el diamante, el enano que recibe el collar en este estado gana el diamante para su clan y el juego termina.

Continue reading “Solución a “El collar de perlas””