Rioplatense 2022 - N3 P6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Rioplatense 2022 - N3 P6

Mensaje sin leer por Matías V5 »

Se tiene escrito en el pizarrón un entero positivo $N$. En cada paso Carla puede realizar cualquiera de las siguientes operaciones:
  • cambiar el número por un múltiplo positivo del número que estaba escrito;
  • cambiar el número por uno que tenga los mismos dígitos que el número que estaba escrito pero en otro orden (está permitido que el nuevo número comience con 0). Por ejemplo, si está escrito el $2022$, con esta operación se puede escribir cualquiera de los números $222$, $2202$ o $2220$.
Determine todos los valores de $N$ para los cuales Carla puede obtener el $1$ al cabo de sucesivos pasos.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Oro-OFO 2024
Mensajes: 211
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 5
Nivel: Exolímpico

Re: Rioplatense 2022 - N3 P6

Mensaje sin leer por enigma1234 »

Spoiler: mostrar
Primero veamos que $N$ no es múltiplo de $3$.
Spoiler: mostrar
Como $n\equiv S(n)\pmod{3}$, luego si tenemos un múltiplo de $3$, luego de una operación este seguirá siendo múltiplo de $3$. Luego, si $N$ es múltiplo de $3$ nunca podremos llegar a $1$.
Ahora, si $N$ no es múltiplo de $3$, veamos que siempre podemos llegar a $1$.
Primero veamos que con la segunda operación podemos eliminar los dígitos $0$ posibles.
Lema 1: Podemos dividir entre $2$ y $5$.
Spoiler: mostrar
Si tenemos $2k$ o $5k$, usando la primera operación llegamos a $10k$ eliminando el $0$ podemos obtener $k$.
Luego podemos dividir entre $2$ y $5$.
Lema 2: Si $N>1$ no es múltiplo de $3$ podemos llegar a $M<N$ tal que $M$ no es múltiplo de $3$.
Spoiler: mostrar
Tomaremos por cierto que los números obtenidos será no múltiplo de $3$ pues solo multiplicaremos por números no múltiplos de $3$ y la segunda operación nunca podría dar un múltiplo de $3$(si es que antes no lo era).

Supongamos que el Lema no es cierto. Sea $N$ el menor que contradice la propiedad. Luego todos los números a los que lleguemos deberían ser $\geq N$.
Veamos que $N$ tiene al menos $2$ cifras, debido a que, para los menores si se cumple la propiedad:
Spoiler: mostrar
A los pares los dividimos entre $2$, a $5$ podemos dividirlo entre $5$, y para $7$ hacemos lo siguiente:
$$7\to 56\to 65\to 13\to 52\to 25\to 5\to 1$$
Debido a la segunda operación, $N$ debe tener los dígitos ordenados de menor a mayor.
Sea $N=1\dots12\dots2\dots9\dots9$, donde hay $k_i$ dígitos $i$, y sea $2\leq k=k_1+k_2+\dots+k_9$ la cantidad de dígitos de $N$.
La estrategia será multiplicar $N$ por un numero $A$ no múltiplo de $3$, reordenar los dígitos y buscar una potencia de $2$ o $5$ mayor que $A$ tal que al dividirlo encontremos un numero menor a $N$.
Lema 2.1: $N$ no tiene cifras pares, es decir $k_2=k_4=k_6=k_8=0$.
Spoiler: mostrar
Supongamos lo contrario, es decir, que $N$ tiene una cifra par.
Digamos que $N=N_1N_2\dots N_k$.
$(1)$: Todos en $\{N_2,N_3,\dots,N_k\}$ son impares.
Spoiler: mostrar
Si alguno de $\{N_2,N_3,\dots,N_k\}$ es par, luego, con la segunda operación, llevamos este numero a las unidades, y dividimos entre $2$, y obtenemos $M$. Como $2M$ empieza con $N_1$, tenemos
$$N\leq M<\frac{(N_1+1)\times 10^{k-1}}{2}\leq N_1\times 10^{k-1}\leq N$$
Contradiciendo lo supuesto. Luego todos en $\{N_2,N_3,\dots,N_k\}$ son impares.
Luego, de $(1)$, $N_1$ debe ser par. Si realizamos la segunda operación para llevar $N_1$ a las unidades: $N\to J=N_2\dots N_kN_1$.
Tenemos que $J$ es par, luego podemos llegar a $\frac{J}{2}$ y entonces:
$$N_1\times 10^{k-1}<N\leq\frac{J}{2}<\frac{(N_2+1)10^{k-1}}{2}\to N_1<\frac{N_2+1}{2}\leq 5\to N_1=\{2,4\}$$

Si $N_1=4$, luego tenemos $2N_1-1=7<N_2$, como $N_2$ es impar, luego $N_2=9$, y por lo tanto $N=499\dots9$, con $k_9$ $9$s.
Luego con la segunda operación y dividiendo entre $2$ podemos obtener:
$$N=5\times 10^{k_9}-1\to 99\dots94=10^{k_9+1}-6\to 499\dots997= 5\times 10^{k_9}-3\to 4799\dots 9<N$$

Si $N_1=2$, luego, como $N_k$ es impar, $J\equiv N_kN_1\equiv 2N_k+2\equiv 0\pmod{4}$, luego podemos llegar a $\frac{J}{4}$. Luego:
$$N\leq \frac{J}{4}<\frac{10^k}{4}\to N_1N_2\times 10^{k-2}<\frac{10^k}{4}\to N_1N_2<25$$

Luego, debido a que $N_2$ es impar, $N_2=3$. Por lo tanto, $J$ empieza en $3$ y por lo tanto:
$$N\leq \frac{J}{4}<\frac{4\times 10^{k-1}}{4}=10^{k-1}<N_1\times 10^{k-1}<N$$

Luego, todas las cifras deben ser impares.
Lema 2.2: $N$ no tiene cifra $5$, es decir $k_5=0$.
Spoiler: mostrar
Supongamos que $k_5\geq 1$, luego $N_1\leq 5\to N<6\times 10^{k-1}$.
Con la segunda operación llevamos una cifra $5$ a las unidades y obtenemos $J$. Dividimos entre $5$, y tenemos:
$$N_1\times 10^{k-1}<N\leq \frac{J}{5}<\frac{10^{k}}{5}\to N_1<2\to N_1=1$$
Luego la primera cifra de $J$ es $1$, luego:
$$10^{k-1}<N\leq \frac{J}{5}<\frac{2\times 10^{k-1}}{5}<10^{k-1},$$
lo cual es una contradicción.
Lema 2.3:$N_1\neq 7$, es decir $N$ no empieza en $7$.
Spoiler: mostrar
Supongamos que $N_1=7$, luego como $k\geq 2$, $77\times 10^{k-2}<N<80\times 10^{k-2}\to 154\times 10^{k-2}<2N<160\times 10^{k-2}$.
Luego, la segunda cifra de $2N$ es $5$. Usando la segunda operación, llevamos el $5$ a las unidades, y dividimos entre $5$, y obtenemos $N\leq M$, luego como $5M$ tiene $k+1$ cifras y empieza en $1$:
$$7\times 10^{k-1}<N\leq M<\frac{2\times 10^k}{5}\to 35<20$$
lo que es una contradicción.
Lema 2.4: Si $k_7\geq 1$, luego $k_7=1$ y $k_9=0$.
Spoiler: mostrar
Supongamos que $k_7\geq 1$. Como hay un $7$, luego $N_1=1$ o $3$. Con esto, tenemos que $2N$ cumple que $2N_1\times 10^{k-1}<2N<(2N_1+2)\times 10^{k-1}$ tiene $k$ cifras, y su primera cifra es $2N_1$ o $2N_1+1$, en particular, no es $5$.

Si $k_7>2$ o $k_9>0$, luego el $7$ mas a la izquierda tiene un numero mayor que $5$ inmediatamente a la derecha, luego $2N$ va a tener un digito $5$ en misma posición que estaba dicho $7$ en $N$. Luego, podemos pasar este digito $5$ a las unidades con la segunda operación, y obtenemos un múltiplo de $5$, digamos $5M$, con su primera cifra igual a la primera cifra que $2N$, pues la primera cifra de $2N$ no es $5$ y por lo tanto no fue movida en la operacion.
Luego, dividimos entre $5$ y obtenemos $M$ con:
$$N_1\times 10^{k-1}<N\leq M\leq \frac{(2N_1+2)\times 10^{k-1}}{5}\to 3N_1<2,$$
lo que es una contradicción.
Lema 2.5: En $N$ no puede haber un $1$ junto a un $3$, es decir $k_1=0$ o $k_3=0$.
Spoiler: mostrar
Supongamos que $k_1,k_3>0$. Luego, tenemos $1\dots130\dots0<N<1\dots 140\dots0$, donde en cada lado hay $k_1$ unos y $k-k_1-1$ ceros. De esto obtenemos que $4\dots4520\dots 0<4N<4\dots4560\dots 0$, donde en cada lado hay $k_1-1$ cuatros y $k-k_1-1$ ceros$\dots(\alpha)$.

De esto tenemos que si vamos de $N\to 4N$, este tiene un digito $5$, luego podemos mover este digito a las unidades, y obtenemos un múltiplo de $5$, digamos $5M$. Por $(\alpha)$, inmediatamente a la derecha del primer $5$ de izquierda a derecha es $2,3,4$ o $5$, luego la primera cifra de $5M$ es $\leq 5$.Luego, dividimos entre $5$ y obtenemos $N\leq M$, de esto:
$$N_1N_2\times 10^{k-2}<N\leq M<\frac{6\times 10^{k-1}}{5}$$
Luego $N_1<12$, es decir $N_2=1\to k_1\geq 2$. De esto, la primera cifra de $4N$ era $4$ y cuando movimos el $5$ la primera cifra seguía siendo $4$, es decir $5M< 5\times 10^{k-1}$ y de esto $10^{k-1}<N\leq M<\times 10^{k-1}$, lo que es una contradicción.
De los lemas anteriores tenemos que los posibles valores de $N$ son:
$$N=1\dots1,N=1\dots17,N=1\dots19\dots9,N=3\dots37$$
(note que $N$ tiene al menos $2$ dígitos, y no puede tener solo dígitos $3$ y $9$ pues sino seria múltiplo de $3$)

Caso 1: $N=1\dots1$, es decir $k=k_1\geq 2$.
Spoiler: mostrar
Para $k_1=2$ podemos hacer:
$$11\to 121\to 112=16\times 7\to 7$$
y obtenemos un numero menor a $N=11$.
Como $N$ no es múltiplo de $3$, luego $k_1\neq 3$, es decir $k_1\geq 4$.
Podemos hacer $N\to 11N=122\dots21$, donde hay $k_1-1\geq 3$ digitos $2$.
Podemos reordenarlo y obtener $M=2\dots2112$, donde al inicio hay $k_1-2\geq 2$ dígitos $2$
Luego $M\equiv 22112\equiv 0 \pmod{32}$, luego podemos dividir entre $32$.
Si dividimos entre $32$ obtendremos un numero $<\frac{3\times 10^{k}}{32}<10^{k-1}<N$, lo que es una contradicción.
Caso 2: $N=1\dots17$, es decir $k=k_1+k_7=k_1+1\geq 2$.
Spoiler: mostrar
Si $k_1\geq 2$, luego $2N=2\dots234$, donde hay al menos un $2$. Luego podemos hacer:
$$N\to 2N\to 32\dots24$$
donde hay $k_1-1$ dígitos $2$. Claramente el ultimo numero es múltiplo de $4$, y como es menor que $4\times 10^{k_1}$, luego dividiendo entre $4$ obtenemos un numero menor a $10^{k_1}<N$. Lo que es una contradicción.

Ahora veamos que si $k_1=1$, multiplicando y dividiendo entre potencias de $2$ o $5$ y reordenando los dígitos, también podemos obtener un numero menor:
$$17\to 85\to 58\to 29\to 92\to 23\to 32\to 1$$
Caso 3: $N=1\dots19\dots9$, es decir $k=k_1+k_2, k_1\geq 1, k_2\geq 1$
Spoiler: mostrar
Si $k_1\geq 2$, luego $2N=2\dots239\dots98$, donde hay $k_1-1\geq 1$ dígitos $2$ y $k_2-1$ dígitos $9$.
Luego podemos reordenar los dígitos a $39\dots92\dots28$ que claramente es múltiplo de $4$. Luego, como es $<4\times 10^{k-1}$, si dividimos entre $4$ obtenemos un numero $<10^{k-1}<N$ lo que es una contradicción.

Luego $k_1=1$. Tenemos $N=19\dots9=2\times 10^{k-1}-1$. Luego podemos llegar a $4N=79\dots98$, donde en $4N$ hay $k_9-1$ dígitos $9$.
Si $k_9\geq 2$ tenemos que podemos reordenar los dígitos y obtener $M=9\dots978=10^{k}-32$. Como $k=k_9+1 \geq 3$, luego tenemos que $M$ es múltiplo de $8$. Si dividimos entre $8$ obtendremos:
$$\frac{M}{8}=\frac{10^{k}-32}{8}<\frac{16\times 10^{k-1}-32}{8}<2\times 10^{k-1}-1=N$$
lo que es una contradicción. Luego $N=19$, pero veamos que con este también podemos llegar a un numero menor:
$$19\to 152=19\times8\to 125\to 1$$
Caso 4: $N=3\dots37$, es decir $k=k_3+k_7=k_3+1\geq 2$
Spoiler: mostrar
Si $k_3\geq 2$, luego $2N=6\dots674$, donde hay al menos un $6$. Luego podemos hacer:
$$N\to 2N\to 76\dots64$$
donde hay $k_3-1\geq 1$ digitos $2$. Claramente el ultimo numero es múltiplo de $4$, y como es menor que $8\times 10^{k_1}$, luego dividiendo entre $4$ obtenemos un numero menor a $2\times 10^{k_1}<N$. Lo que es una contradicción.

Luego $N=37$, pero veamos que con este también podemos llegar a un numero menor:
$$37\to 37\times13=481\to 184=8\times23\to 23$$
lo que es una contradicción.
Luego, llegamos a que el Lema 2 es cierto.
Por lo tanto, como siempre podemos ir a un numero menor, claramente Carla podrá obtener el $1$ para cualquier numero $N$ no múltiplo de $3$.
Responder