Regional 2013 N3 P1

[Bar251]

no, al dividir por doce te da resto 42.

[Aldana]

Spoiler: mostrar

Observamos que [math]A(n) = \sum_{i=0}^{n-1} (n-i) \cdot 10^{i}
Queremos que [math]A(n) \equiv 0 (mod \, 45) y esto se verifica sii:

a) [math]A(n) \equiv 0 (mod \, 5) y
b) [math]A(n) \equiv 0 (mod \,9).

a) Claramente, esta condición equivale a exigir [math]n \cdot 10^{0} \equiv 0 (mod \, 5) es decir [math]n \equiv 0 (mod \, 5)

b) Como un natural [math]n tiene el mismo resto en la división por [math]9 que la suma de sus dígitos y como un natural [math]n = \sum_{i=0}^{n} a_i tiene el mismo resto en la división por [math]x que la suma de los restos de los [math]a_i en la división por [math]x (acá tomamos [math]x=9), [math]A(n) \equiv \sum_{i=0}^{n-1} (n-i) (mod \,9) o sea [math]A(n) \equiv \sum_{i=1}^{n} i (mod \,9)

Ahora el problema equivale a hallar el menor [math]n múltiplo de [math]5 tal que [math]9 divide a [math]\sum_{i=1}^{n} i = \frac{n \cdot (n+1)}{2}

Probamos a mano y vemos que el menor es [math]n=35.

[Hechicero]

Bueno mi solución poco casera! jaja

Primero vemos que debe ser múltiplo de [math]9 y [math]5 a la vez.
Para que sea múltiplo de [math]9 la suma de sus dígitos debe ser múltiplo de [math]9, y como son todos [math]1, la suma sera siempre la de Gauss, Así que tenemos:

Suma de [math]n [math]= [math]1 [math]+ [math]2 [math]+ ... [math]+ [math]n [math]= Múltiplo de [math]9.

Se resume en [math]\frac{n.(n+1)}{2}
Luego voy probando los números que satisfacen la operación y observo que son los múltiplos de [math]9 y su antecesor.
Es decir [math]8 y [math]9 , [math]17 y [math]18 , [math]26 y [math]27 , [math]35 y [math]36....Etc.
Luego, hay que ver cual termina en [math]0 o [math]5, para que la suma de las unidades sea múltiplo de [math]5, y como vemos el numero es [math]35. Y listo!
Esta bien?

[Gianni De Rico]

Spoiler: mostrar

Como $10^2\equiv 100\equiv 10\pmod{45}$, tenemos que $10^n\equiv 10\pmod{45}$ para todo $n\in \mathbb{N}$. Sea $f(k)$ el número formado por $k$ dígitos $1$, entonces $f(k)\equiv 10(k-1)+1\pmod{45}$ para todo $k\in \mathbb{N}$. Resulta así$$A(n)=\sum \limits _{k=1}^nf(k)$$$$A(n)\equiv \sum \limits _{k=1}^n10(k-1)+1\pmod{45}$$$$A(n)\equiv 5n(n-1)+n\pmod{45}$$$$A(n)\equiv n(5n-4)\pmod{45}$$En particular, $n\equiv n(5n-4)\equiv 0\pmod 5$. Entonces probamos los múltiplos de $5$ (son $9$ porque miramos módulo $45$) y vemos que el primero que cumple es $n=35$.

[drynshock]

Dejo una forma no tan compleja:

Spoiler: mostrar

Veamos que 45 = 3.3.5, entonces la suma de los dígitos tiene que ser múltiplo de 9 y también debe ser múltiplo de 5.

Como en cada A(n) se suma 1 en la unidad, la cantidad de términos debe ser múltiplo de 5, en otras palabras n es múltiplo de 5.

Luego para que sea múltiplo de 9, la suma de los dígitos debe ser múltiplo de 9. Notemos que para n = 1 suma = 1. n = 2 suma = 2, n = 3 suma = 3...
Entonces la suma de los dígitos de todo es 1 + 2 + 3 + ... + n, lo cual es igual a la suma de Gauss $\frac{n(n+1)}{2}$.

Como n era múltiplo de 5, expresémoslo como 5k y reemplacémoslo en la formula:
$\frac{5k(5k+1)}{2}$.

Acá podríamos usar teorema chino del resto en la congruencia por 9, pero también podemos ir probando k=1, k=2, k=3 hasta que nos de un múltiplo de 9. El primer k que cumple es 7, como n = 5k, entonces n = 35.

[magnus]

Spoiler: mostrar

Tenemos que $45=3^2\times 5$. Como el número de las únidades de todos los términos de la suma es $1$ tenemos que $A(n)\equiv n \mod 10$. Basandonos en el criterio de divisibilidad por $5$ tenemos que $5\mid A(n)\Rightarrow A(n)\equiv 0 \mod 5\Rightarrow n\equiv 0 \mod 5$.

Llamemos $S(l)$ a la sumade los dígitos de $m$:
Notemos que si tenemos un número $\underbrace{1\dots 1}_{k}$, la suma de sus cifras será $1\times k=k$. Notemos que $n=n_1+ n_2+ \dots +n_k \Rightarrow n\equiv n_1+n_2+\dots+n_k \mod m$. Digamos que $m=9$, tenemos que $n\equiv 1+11+111+\dots \underbrace{1\dots 1}_{n} \mod9$.Tenemos que podemos saber el resto de un número módulo $9$ sumando sus dígitos, entonces $n\equiv S(1)+S(11)+\dots+S(\underbrace{1\dots 1}_{n}) \mod 9$ y como ya sabemos que $S(\underbrace{1\dots 1}_{n} )=n$ tenemos que $n\equiv \frac{n(n+1)}{2}\equiv 0 \mod 9$.

Como $5\mid n$ tenemos que $\frac{5k(5k+1)}{2}\equiv 0 \mod 9$, vemos que el único posible valor es $k\equiv 7\mod 9$ tenemos que el menor valor posible de $k$ es $0\times 9 +7=7$ entonces el menor valor que puede tomar $n$ es $n=5\times 7= 35$