elnumerodeoro
Enhebramos 2n perlas blancas y 2 n perlas negras formando un collar abierto. Demuestre que, se haga en el
orden que se haga, siempre es posible cortar un segmento del collar con exactamente con n perlas blancas y n perlas negras.
brunoandrades
Llamaremos un subcollar a un string de 2 n perlas consecutivas. Enumeraremos a los subcollares de tal manera que el m-ésimo subcollar será aquel que contenga desde la m-ésima perla de izquierda a derecha hasta la (m+2n-1)-ésima perla de izquierda a derecha. Si el primer subcollar tiene la misma cantidad de perlas blancas que negras, ganamos. Si no; supongamos sin pérdida de generalidad que hay más perlas blancas que negras. Si revisamos el segundo subcollar, hay dos opciones; primero, que la perla nueva sea del mismo color que la que ya no está, en cuyo caso la cantidad de perlas de cada color se mantiene constante, o que la perla nueva sea de un color distinto al de la perla que ya no está, en cuyo caso la cantidad de perlas de un color aumentará en uno, y la cantidad de perlas del otro disminuirá en uno. Notemos que la paridad de la cantidad de perlas de cada color es igual; sin importar que subcollar, ya que en un principio la cantidad de perlas debe sumar un número par (2n) en cada subcollar. Además notemos que una vez que pasamos al siguiente subcollar; si no se mantuvo constante la cantidad de cada color, cada uno está en el número anterior o en el siguiente. Por lo tanto, si logramos demostrar que en el último paso, hay más negras que blancas habremos demostrado lo pedido, ya que como siempre van avanzando a lo más una unidad, deben haber tenido la misma cantidad de perlas en algún momento, ya que no puede pasar que sean cantidades consecutivas gracias a la propiedad de paridad. Pero notemos; que ya que la cantidad de blancas en el primer subcollar es mayor; debe ser mayor a n, y si además fuera mayor en el último subcollar; esto implicaría que, ya que el primer subcollar y el último subcollar son disjuntos que la cantidad de blancas total es mayor a n+n = 2n lo cual no puede ser. Por lo tanto la cantidad de negras en el último collar es mayor a la cantidad de blancas, así, en alguno de los subcollares debió haber la misma cantidad de negras que de blancas.
