P4. Ceros y Unos en un pizarrón.

Enviado por Samuel Elias el 19 de Octubre de 2024 - 14:08.

Sea $n$ entero positivo. Hay $2n$ números escritos en el pizarrón: $n$ 0’s y $n$ 1’s. Una movida consiste en escoger dos números del pizarrón, borrarlos y escribir 0 si eran iguales o 1 si eran distintos. Despues de hacer varias movidas, queda solo un número.

¿Para qué valores de $n$ te puede quedar un número par?
¿Para qué valores de $n$ te puede quedar un número impar?

Sugerencia

Sugerencia:

Invarianza? Observa que la paridad de la suma no cambia. ¿Cómo se comporta un movimiento de forma individual?

Solución

Solució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.