lunes, 30 de mayo de 2011

Problema del dia Lunes 30 de Mayo (Centros)

Una representación chida de un entero positivo n, es una representación de n como suma de potencias de 2, con cada potencia apareciendo a lo mas 2 veces.
Por ejemplo,  5 = 4 + 1 = 2 + 2 + 1.
Cuales enteros positivos tienen un numero par de representaciones chidas? 

3 comentarios:

Juan dijo...

Te fijas en el binario de un número, y supongamos que es:
"$1...10...01...10...01...10...0$", con primero $b_1$ 1's consecutivos, luego $a_1$ 0's consecutivos, luego $b_2$ 1's consecutivos, ..., luego $b_k$ 1's consecutivos, luego $a_k$ 0's consecutivos. El único a o b que puede ser 0 es el $a_k$.
Una representación chida es el binario pero con 2's como dígito también. Comparando una representación chida con el binario, vemos que una representación chida se obtiene con el binario, poniendo un 1 como 0 y el 0 que le procede como 1, el 0 que le procede como 1, ..., el cero que le procede como 1 así hasta que en un cero le pones 2 (porque llegas a que la suma de unas potencias de 2 es igual a la suma de otras potencias de 2, y tomas la potencia de dos máxima, concluyes que está en las dos sumas, y así te vas y sale fácil). Así, el número de representaciones chidas es la multipliacción de todos los $(b_i+1)$. Para que sea impar, el número debe ser de la forma:
$1...10...0.....$, pero cada cadena de 0's debe tener longitud par.

Juan dijo...

Perdón, multiplicas los $(a_i+1)$

Enrique dijo...

Otra idea puede ser definir la función que devuelve el número de representaciones buenas de cada entero positivo, así como otra función que devuelva el número de representaciones buenas sin usar 1's, luego encontrar una recursión para el número de representaciones buenas (dividiendo en casos par e impar) y demostrarla usando las funciones arriba mencionadas. De aquí es fácil sacar la paridad.

Publicar un comentario