P4. Ceros y Unos en un pizarrón.

Vamos a usar el siguiente lema

 

Lema 1: La paridad de la suma de los números en el pizarrón nunca cambia.

 

Notemos que si eliminamos dos números iguales (digamos $a$) y agregamos un 0, entonces la suma disminuyó por $2a$ y aumentó por 0. Entonces la suma cambió por un número par por lo que su paridad no cambia. Si eliminamos dos números diferentes, entonces tiene que ser un 0 y un 1, y agregamos un 1, entonces la suma disminuyó en 1 y aumentó en 1 por lo que permaneció igual. Entonces la paridad no cambia.

 

Cómo los números en el pizarrón eran originalmente 0's y 1's, y cada vez que agregamos un número es un 0 o un 1, entonces únicamente solo habrán 0's y 1's en el pizarrón.

 

Si $n$ es impar entonces la suma original del pizarrón es $n$ que es impar por lo que el número final tendrá que ser impar para preservar la paridad por lo que será un 1. Si $n$ es par entonces la suma original es $n$ que es par lo que lo el número final tendrá que ser 0 para preservar la paridad.