Solución de problemas de USAMO

Nov 23 2020

Había pedido una pista aquí https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416Probé la inducción una vez pero pensé que no funcionaría, así que la dejé, pero después de ver el comentario de @lulu, decidí intentarlo de nuevo. Por favor, vea si mi solución es correcta.

[USAMO 2003] Demuestre que para cada entero positivo n existe un número de n dígitos divisible por $5^n$ todos cuyos dígitos son impares.

MI SOLUCIÓN: Primero, verifiqué algunos casos pequeños y pensé que podríamos generar el número con (n + 1) dígitos que satisfagan la propiedad agregando un número al frente, es decir. sumando b 10$^n$ al número con n dígitos.

Procederemos con la inducción, supongamos que P (n) significa que existe un número de n dígitos divisible por $5^n$ todos cuyos dígitos son impares.

P (1) es verdadero como 5 | 5.

Sea P (k) verdadero, es decir. deja 5$^k$ | $a_ka_{k-1}...a_1$ con $a_i$ $\neq$ 2l para yo $\in$ {1,2 ... k}.

Intentaré probar eso agregando $ b \cdot 10^k $ con $ b \in {1,3,5,7,9} $. podemos tener un número divisible por$5^{k+1}$.

Entonces queremos 5$^{k+1}$ $|$ $ b \cdot 10^k $ + $a_ka_{k-1}...a_1$. -> ecuación 1

Dejar $a_ka_{k-1}...a_1$ = $5^km $

Entonces de la eq. 1, ingresando$a_ka_{k-1}...a_1$ = $5^km $ , obtendremos

5$^{k+1}$ $|$ $ b \cdot 10^k $ + $5^k$m, luego dividiendo por $5^k$ , nosotros necesitamos

5 $|$ $2^k \cdot b + m$

como $ b \in {1,3,5,7,9} $ , $\equiv$ 0,1,2,3,4 (mod 5)

Así que ahora m $\equiv$ 0,1,2,3,4 (mod 5), sea m $\equiv$ r (mod 5),

Nosotros necesitamos $2^k \cdot b + r =0 (mod 5)$

ahora,$2^k \equiv$ 1,2,3,4 (mod 5)

tan minuciosamente revisando todos y cada uno de los casos de posibles valores de $2^k$ ym (mod 5) (hay 16 casos), probamos que podemos encontrar un $ b \in {1,3,5,7,9} $ tal que 5 $|$ $2^k \cdot b + m$ .

Esta es la primera vez que escribo tanto en látex, así que lamento si hay algún error.

Si fueras calificador, de 7, ¿cuántos puntos me darías?

Respuestas

1 J.G. Nov 23 2020 at 02:49

No creo que las respuestas de math.se puedan abordar cómo lo marcarían, pero puedo aconsejarle sobre una forma más limpia de escribir las respuestas, porque sus ideas son correctas, pero podrían hacerlo con claridad algebraica y claridad con respecto a la aritmética del módulo. (Si se encuentra afirmando que si hacemos algo, eventualmente obtendremos un resultado particular, intente enunciar esto como un teorema de existencia que sea obvio, bien conocido o probado en su trabajo).

Reclamamos alguna secuencia $a_n$ de $n$-números de dígitos en la base $10$, todos los dígitos impares, satisface $5^n|a_n,\,10^n|a_{n+1}-a_n$. En particular escribe$a_n=5^nb_n,\,a_{n+1}=a_n+10^nc_n$, entonces $b_1=1$ (porque $a_1=5$) y$$5^{n+1}b_{n+1}=a_{n+1}=c_n10^n+5^nb_n\iff5b_{n+1}=c_n2^n+b_n,$$entonces basta con elegir $c_n\in\{1,\,3,\,5,\,7,\,9\}$ con $5|c_n2^n+b_n$. Esta elección es posible porque estos$5$ elecciones de la $c_n$ cada uno logra un módulo de clase de residuo diferente $5$ (porque $5\nmid k2^n$ para $k\in\{2,\,4,\,6,\,8\}$), y exactamente uno logra $5|c_n2^n+b_n$.

1 BillDubuque Nov 23 2020 at 17:58

Hay un $\,x\in\Bbb Z\,$ con $\,5\mid 2^k x - m\!\iff\! \bmod 5\!:\ 2^k x \equiv m\,$ tiene una raíz $\,x.\,$ Por https://math.stackexchange.com/a/3290965/242

$$\begin{align} \color{#c00}c\ x &\equiv \, d\!\!\pmod{\!\color{#0a0}n}\ \ \text{has a root}\ x\!\iff\! \gcd(\color{#c00}c,\,\color{#0a0}n)\mid d\\[.3em] {\rm thus}\ \ \color{#c00}{2^k} x&\equiv m\!\!\!\pmod{\!\color{#0a0}5}\ \ \text{has a root}\ x,\ \, {\rm by}\ \ \gcd(\color{#c00}{2^k},\color{#0a0}5)\!=\!1\end{align}\qquad$$

y podemos elegir una raíz $\,x\in \{1, 3, 5, 7, 9\}\,$ ya que es un https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems $\!\bmod 5;\,$ alternativamente: $ $ Si $\,0\le x < 5\,$ es incluso entonces $\,x':= x\!+\!5\,$ es impar $< 10,\,$ y $\,x'$ sigue siendo una raíz por $\,x'\equiv x\pmod{\!5}$.