Rioplatense 2018 - N2 P4

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

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Rioplatense 2018 - N2 P4

Mensaje sin leer por Joacoini »

Sea $n$ un entero positivo. Demostrar que $n(2^n-1)$ se puede escribir como suma de $n$ potencias distintas de $2$.
NO HAY ANÁLISIS.
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Rioplatense 2018 - N2 P4

Mensaje sin leer por Joacoini »

Spoiler: mostrar
Mi solución permite cambiar al número que multiplica a $2^n-1$ por $k$ siempre y cuando $k\leq 2^{n-1}$.

A partir de ahora nos despedimos del sistema opresor decimal y nos pasamos al binario.
$2^n-1$ pasa a ser $11...(n)...11=1_n$ y nuestro objetivo pasa a ser demostrar que $k\times 1_n$ esta conformado por $n$ unos.

Veamos que $1_n$ tiene un criterio de divisibilidad idéntico al que tiene $9_n$ en el sistema decimal.
$100...(n)...00\equiv 1$ mod $(1_n)$
Si $a_ma_{m-1}a_{m-2}...a_{n+1}a_n...a_2a_1$ es un número en binario entonces
$a_ma_{m-1}a_{m-2}...a_{n+1}a_n...a_2a_1\equiv a_ma_{m-1}a_{m-2}...a_{n+1}\times 100...(n)...00+a_n...a_2a_1\equiv a_ma_{m-1}a_{m-2}...a_{n+1}+a_n...a_2a_1$ mod$(1_n)$
O sea separamos un número en bloques de a $n$ y la suma de esos bloques tiene que ser múltiplo de $1_n$

Para $k=100...(n-1)...00$, $k\times 1_n=11...(n)...1100...(n-1)...00$ tiene $2n-1$ dígitos por lo que para cualquier $k$ la cantidad de dígitos de $k\times 1_n$ es menor o igual a $2n-1$.

$k\times 1_n=a_{2n}a_{2n-1}...a_1$ (los primeros dígitos pueden ser $0$ y $a_{2n}=0$)

Como $a_{2n}a_{2n-1}...a_1$ es múltiplo de $1_n$, $a_{2n}a_{2n-1}...a_{n+1}+a_n...a_1$ también.
$a_{2n}a_{2n-1}...a_n+a_{n-1}...a_1\leq 1_{n-1}+1_n<1_n\times 10\Rightarrow a_{2n}a_{2n-1}...a_{n+1}+a_n...a_1=1_n$

Veamos esta ultima suma por partes, $a_1+a_{n+1}$ termina en $1$, hay tres opciones, ambos son $1$, ambos son $0$ y uno es cero y el otro uno, de las tres opciones solo la ultima funciona, como esta ultima opción no produce acarreo podemos analizar de la misma forma $a_2+a_{n+2}$ y de la misma forma uno es $1$ y el otro $0$, análogamente vemos que entre $a_j$ y $a_{n+j}$ uno es $1$ y el otro es $0$, como hay $n$ pares de esta forma el número $k\times 1_n$ esta conformado por $n$ unos y $n$ ceros como queríamos demostrar.
1  
NO HAY ANÁLISIS.
Avatar de Usuario
Tob.Rod

OFO - Mención-OFO 2021 OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Mención-FOFO 12 años OFO - Medalla de Plata-OFO 2023
FOFO 13 años - Copa-FOFO 13 años OFO - Medalla de Plata-OFO 2024
Mensajes: 28
Registrado: Vie 04 Dic, 2020 6:31 pm
Medallas: 7
Nivel: 3
Ubicación: Uruguay

Re: Rioplatense 2018 - N2 P4

Mensaje sin leer por Tob.Rod »

Spoiler: mostrar

Primero, probemos que se puede para todo $n = 2^k$, con $k ∈ \mathbb{Z}^+_0$.
Spoiler: mostrar
Reemplazamos $n = 2^k$
$$2^k \times (2^{2^k} - 1) = 2^{2^k + k} - 2^k$$
Podemos reescribir el lado derecho como:
$$2^{2^k + k} - 2^k = 2^{2^k+k-1} + 2^{2^k+k-2} + ... + 2^{k+1} + 2^k$$
Viendo los exponentes, vemos que hay $2^k +k-1 - k + 1 = 2^k=n$ potencias distintas de $2$, por lo que ya queda demostrado que se cumple para todo $n = 2^k$.
Ahora, probemos que se puede para todo $n = 2^k - a$, con $a ∈ \mathbb{Z}^+; 2^k > a > 2^{k-1}$
Spoiler: mostrar
Reemplazamos $n = 2^k - a$
$$(2^k-a)(2^{2^k-a}-1) = 2^{2^k-a+k}-2^k-a2^{2^k-a} +a$$
Utilizando el mismo truco que en el caso anterior, reescribimos: $2^{2^k-a+k}-2^k = 2^{2^k-a+k-1}+...+2^k$
Sabiendo que todo numero se puede escribir como suma de potencias distintas de $2$ (esto lo podemos deducir al utilizar la base binaria), reescribimos $a= 2^{x_1} + 2^{x_2} + ... + 2^{x_m}$. Como $a<2^k$, entonces $x_i < k$ para todo $x_i$.
Juntando todo, nos queda:
$$2^{2^k-a+k-1}+...+2^k - (2^{x_1} +...+ 2^{x_m}) \times 2^{2^k-a} + 2^{x_1} +...+ 2^{x_m}$$
$$2^{2^k-a+k-1}+...+2^k - (2^{2^k-a+x_1} +...+ 2^{2^k-a+x_m}) +2^{x_1}...+ 2^{x_m}$$

Notemos que en $2^{2^k-a+k-1}+...+2^k$ tenemos $2^k-a$ potencias distintas de $2$.
Luego, como $0 \leq x_i<k$, para todo $i$ entonces todos los términos de $2^{2^k-a+x_1} +...+ 2^{2^k-a+x_m}$ están incluidos en $2^{2^k-a+k-1}+...+2^k$, por lo tanto hay $m$ potencias que se cancelan.
Esto nos deja con $2^k-a-m$ potencias distintas de $2$, pero a esto le sumamos $2^{x_1}+...+ 2^{x_m}$, que no son mas que otras $m$ potencias de dos, por lo que al final nos quedamos con $2^k-a-m + m = 2^k-a = n$ potencias distintas de $2$.
Así queda demostrado que se puede para todo $n = 2^k - a$
Como ya mostramos que se puede para $n=2^k$ y $n=2^k-a$, entonces queda demostrado para todo $n∈ \mathbb{Z}^+$
Responder