Nacional 2019 - Nivel 2 - Problema 6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 233
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 8
Nivel: Ñandú

Nacional 2019 - Nivel 2 - Problema 6

Mensaje sin leer por Monazo » Jue 14 Nov, 2019 11:09 am

Sea $n$ un número natural. Definimos $f(n)$ como la cantidad de maneras de escribir $n$ como suma de potencias de $2$, donde se tiene en cuenta el orden en que aparece cada término. Por ejemplo, $f(4)=6$ pues $4$ se puede escribir como $4;$$\ 2+2;$$\ 2+1+1;$$\ 1+2+1;$$ \ 1+1+2;$$\ 1+1+1+1.$
Hallar el menor $n$ mayor que $2019$ para el que $f(n)$ es impar.
El Diego es del Lobo! Y del Lobo no se va!

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 1293
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2019 - Nivel 2 - Problema 6

Mensaje sin leer por Gianni De Rico » Sab 22 Feb, 2020 11:36 pm

Dejo la solución que contó Juli, aunque un poquito más "suavizada"

Respuesta:
Spoiler: mostrar
El menor $n$ mayor que $2019$ tal que $f(n)$ es impar es $2047$.
Solución:
Spoiler: mostrar
Vamos a extender un poco la definición de $f$, a todos los enteros (esto nos va a servir para las cuentas que tenemos que hacer después). Ponemos entonces $f(0)=1$ y $f(k)=0$ para todo $k$ entero negativo. Vamos a demostrar entonces la siguiente relación, que podemos usar para calcular $f(n)$ si ya tenemos calculados valores anteriores, la primer mega afirmación es:$$f(n)=f(n-1)+f(n-2)+f\left (n-2^2\right )+f\left (n-2^3\right )+\ldots +f\left (n-2^t\right )$$donde $t$ es el mayor entero tal que $2^t\leqslant n$, además, podemos escribir la relación de una forma más compacta:$$f(n)=\sum \limits _{i=0}^tf\left (n-2^i\right )$$Veamos que esto es cierto, escribimos$$n=2^{a_1}+2^{a_2}+\ldots +2^{a_x}$$donde los $a_i$ son enteros no negativos. De esto se sigue que$$n-2^{a_1}=2^{a_2}+\ldots +2^{a_x}$$por lo que una vez que elegimos el valor de $a_1$, hay $f\left (n-2^{a_1}\right )$ formas de elegir los demás valores de los $a_i$, entonces mientras vamos variando $a_1$ por todos sus valores posibles (desde $0$ hasta $t$), vamos obteniendo todas las formas de escribir $n$ como suma de potencias de $2$, donde se tiene en cuenta el orden en el que aparece cada término, es decir, obtenemos $f(n)$. Pero también dijimos que para cada valor de $a_1$ hay $f\left (n-2^{a_1}\right )$ formas de escribir $n$ como suma de potencias de $2$, donde se tiene en cuenta el orden en el que aparece cada término, es decir, obtenemos $f(n-1)+f(n-2)+f\left (n-2^2\right )+f\left (n-2^3\right )+\ldots +f\left (n-2^t\right )=\sum \limits _{i=0}^tf\left (n-2^i\right )$. Por lo tanto$$f(n)=\sum \limits _{i=0}^tf\left (n-2^i\right )$$y demostramos la primer mega afirmación.

Ahora, tenemos una definición un poco más cómoda de $f(n)$, estaría buenísimo poder usar esto para hallar el valor de $f(n)$, pero es muy complicado, así que como solamente nos interesa ver si $f(n)$ es par o impar, vamos con la segunda mega afirmación, que dice:$$f(n)\equiv 1\pmod 2\iff n=2^k-1$$donde $k$ es un entero no negativo.
Vamos a demostrar esto por inducción fuerte en $n$.
El caso base es $n=0$, que vale pues $0=1-1=2^0-1$ y $f(0)=1$ por definición.
Supongamos como hipótesis inductiva que nuestra segunda mega afirmación vale para todo $m<n$, veamos entonces que vale para $n$.
En efecto, usando la fórmula para $f(n)$ tenemos que$$f(n)=f(n-1)+f(n-2)+f\left (n-2^2\right )+f\left (n-2^3\right )+\ldots +f\left (n-2^t\right )$$notemos que los términos que son $0\pmod 2$ no afectan a la suma, así que los únicos que importan son aquellos tales que $n-2^k=2^i-1$, ya que por hipótesis inductiva son los únicos para los que $f\left (n-2^k\right )\equiv 1\pmod 2$. Pero notemos que $n-2^k=2^i-1\iff n-2^i=2^k-1$, entonces a cada término $f\left (n-2^k\right )$ le corresponde un término $f\left (n-2^i\right)$, que también vale $1\pmod 2$. Entonces, si $k\neq i$, los términos son distintos, por lo que su suma es $f\left (n-2^k\right )+f\left (n-2^i\right )\equiv 1+1\equiv 0\pmod 2$, esto quiere decir que si ningún valor de $k$ es igual a un valor de $i$, entonces todos los términos quedan emparejados de forma que su suma es $0\pmod 2$, así que $f(n)$ es par, además, si $k=i$, resulta $n-2^k=2^k-1$, por lo que $n=2^k+2^k-1=2\cdot 2^k-1=2^{k+1}-1=2^x-1$. Esto nos dice que solamente puede haber un valor de $k$ que sea igual a algún valor de $i$, de forma que hay un único término que no puede emparejarse, es decir, la suma es $1\pmod 2$.
Entonces vimos que si $n\neq 2^k-1$ (esto pasa si $k\neq i$), $f(n)\equiv 0\pmod 2$, y si $n=2^k-1$, entonces $f(n)\equiv 1\pmod 2$. Por lo tanto, $f(n)\equiv 1\pmod 2\iff n=2^k-1$ para algún $k$ entero no negativo. Esto completa la inducción. Así que la segunda mega afirmación está demostrada.

Para hallar la respuesta del problema, vemos que el menor número de la forma $2^k-1$ que es mayor que $2019$ es $2047=2^{11}-1$. Y con eso estamos.
2  
Queda Elegantemente Demostrado

Responder