domingo, 10 de junio de 2007

La cadena blanca y negra

Enunciado

Como primera medida, deberemos probar la misma situación descrita sobre una cadena más pequeña. Supongamos que ponemos dos bolas blancas y dos negras (deben ser pares, para poder tomar la mitad) en una cadena abierta. Si tomamos las dos primeras bolas, puede que tengamos una de cada color (en cuyo caso ya tendremos resuelta la situación), o bien han de ser del mismo color, en cuyo caso las otras dos serán del color opuesto, así que bastará tomar la cadena formada por las dos centrales.

¿Y si tomamos seis blancas y seis negras? Procediendo de la misma forma, al tomar las seis primeras que encontremos, puede que ya sean tres de cada clase, o que predominen de uno de los dos tipos. Si se produce esta situación, podemos ir pasando bola a bola, tomando la siguiente de la cadena y soltando la otra. ¿Llegaremos a encontrar la mezcla adecuada? Pensemos un poco.

En el fragmento que queda la situación es exactamente al contrario (si tenemos en el primer fragmento, por ejemplo, cuatro negras y dos blancas, en el otro habrá dos negras y cuatro blancas). Si consideramos el valor "bolas negras menos bolas blancas", en este momento valdrá 2. Cuando pasamos a la bola siguiente y dejamos la anterior, puede que dejemos las cosas como estaban (si eran del mismo color) o bien que varíe en dos unidades (porque una sea de un tipo y la otra de otro). Cuando repetimos el proceso hasta el final de la cadena, llegamos a un valor de -2, por lo que en algún momento pasará de ser positivo a valer 0, antes de volverse negativo. En ese momento tendremos 6 bolas de forma que 3 serán de un color y 3 de otro.

Es fácil ver que, puesto que tenemos un número par de bolas de dos colores, el resultado de la diferencia siempre es par (en caso contrario, si partiésemos de una diferencia impar, podríamos pasar de positivo a negativo sin pasar por el cero, desde el 1 al -1).

Este resultado se puede extender a cualquier número de bolas de dos colores, siempre que sea par (por ejemplo, 2008 bolas blancas y 2008 negras).