P1N3 - Nacional OMA 2000

Problemas que aparecen en el Archivo de Enunciados.
chescopilo
Mensajes: 4
Registrado: Mar 19 Jun, 2012 9:12 pm

P1N3 - Nacional OMA 2000

Mensaje sin leer por chescopilo »

Se escriben en sucesión los números naturales, formando una secuencia de dígitos$$12345678910111213141516171819202122232425262728293031\ldots$$Determinar cuántas cifras tiene el número natural que contribuye a esta secuencia con el dígito de la posición $10^{2000}$.

Aclaracion: El número natural que contribuye a la secuencia con el dígito de la posición $10$ tiene $2$ cifras, porque es el $10$; el número natural que contribuye a la secuencia con el dígito de la posición $10^2$ tiene $2$ cifras, porque es el $55$.
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: P1 N3 - Nacional OMA 2000

Mensaje sin leer por Ivan »

Spoiler: mostrar
Hay $9$ números de $1$ dígito. O sea que las primeras $9$ posiciones corresponden a números de un dígito.

Hay $90$ números de $2$ dígitos. O sea que los dígitos en las posiciones $10$ a $189=9+2\cdot 90$ corresponden a números de $2$ dígitos.

Hay $900$ números de $3$ dígitos. O sea que los dígitos en las posiciones $190$ a $189+3\cdot 900$ corresponden a números de $3$ dígitos.

Ahora tratemos de escribir esto para un número de $n$ dígitos (obviamente no vamos a poder hacer la cuenta a mano hasta $10^{2000}$).

La cantidad de números de $n$ dígitos, es $9\cdot 10^{n-1}$ (para el primer dígito hay $9$ opciones, para los demás hay $10$).

Las posiciones que corresponden a números de $n$ dígitos son las que van entre $$l(n)=9 + 2\cdot 90 + 3 \cdot 900 + \ldots + (n-1) \cdot 9 \cdot 10^{n-2} + 1$$ y $$r(n)=9 + 2\cdot 90 + 3 \cdot 900 + \ldots + (n-1) \cdot 9 \cdot 10^{n-2} + n \cdot 9 \cdot 10^{n-1}$$

Ejemplo: $l(1)=1$, $r(1)=9$, $l(2)=10$, $r(2)=189$, $l(3)=190$, etc.

Entonces queremos encontrar el mínimo $n$ tal que $$10^{2000}\leq r(n)=\sum_{i=1}^{n}i\cdot 9 \cdot 10^{i-1}$$
(la notación $\sum$ significa que estamos sumando eso para cada valor de $i$ entre $1$ y $n$, lo escribo así para no poner los primeros y los últimos términos con puntos suspensivos en el medio.)

Resulta que el $n$ que buscamos es $1997$. Lo más razonable que se me ocurre para conjeturar que da eso es mirar solamente el término más grande de la suma, que es $9\cdot n \cdot 10^{n-1}$ y notar que para $n=1996$ este término es mas chico que $10^{2000}$ pero que para $n=1997$ ocurre lo contrario.

Esto muestra que $10^{2000}<1997\cdot 9 \cdot 10^{1997-1}<r(1997)$. Lo único que falta probar es que $r(1996)<10^{2000}$.

Queremos probar que $\sum_{i=1}^{1996}i\cdot 9 \cdot 10^{i-1}<10^{2000}$. Pero notemos que $$\sum_{i=1}^{1996}i\cdot 9 \cdot 10^{i-1}<\sum_{i=1}^{1996}10^4 \cdot 9 \cdot 10^{i-1}=\sum_{i=4}^{1999}9 \cdot 10^{i}<10^{2000}$$ Esto muestra que el número que contribuye a la posición $10^{2000}$ tiene $1997$ dígitos.
Si no se entiende algo preguntá :P
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: P1N3 - Nacional OMA 2000 (AYUDAAAA)

Mensaje sin leer por Ivan »

Otra opción para terminarlo es esta:
Spoiler: mostrar
Habíamos dicho que lo que buscamos es el menor natural $n$ tal que $r(n)\geq 10^{2000}$.

La idea es probar que $$r(n)=n\cdot 10^n -\frac{10^n-1}{9}$$

Esto se puede probar por inducción. Notemos que $r(1)=9$, así que la fórmula vale para $n=1$. Ahora suponiendo que la fórmula vale para $n$ vamos a probar que también vale para $n+1$ (y con esto queda claro que vale para cualquier valor de $n$).
Notemos que $$\begin{align*}r(n+1)&=r(n)+(n+1)\cdot 9\cdot 10^{n}\\ & =n\cdot 10^n -\frac{10^n-1}{9}+(n+1)\cdot 9\cdot 10^{n}\\ &=(n+1)\cdot 10^n-10^n -\frac{10^n-1}{9}+(n+1)\cdot 9\cdot 10^{n}\\ &=(n+1)\cdot 10^{n+1}-10^n -\frac{10^n-1}{9}\\ &=(n+1)\cdot 10^{n+1}-\frac{10^{n+1}-1}{9} \end{align*}$$ y entonces la fórmula vale para todo $n$.

En el post anterior vimos que $n \cdot 9 \cdot 10^{n-1}\leq r(n )$ (esto vale porque es un término de la suma).

Ahora tenemos
$$r(1996)=1996\cdot 10^{1996} -\frac{10^{1996}-1}{9}<1996\cdot 10^{1996}<10^{2000}< 1997\cdot 9 \cdot 10^{1997-1}\leq r(1997)$$

Entonces la respuesta es $1997$.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
chescopilo
Mensajes: 4
Registrado: Mar 19 Jun, 2012 9:12 pm

Re: P1N3 - Nacional OMA 2000 (AYUDAAAA)

Mensaje sin leer por chescopilo »

Muchas gracias, te pasaste!!!! :D
Avatar de Usuario
biank
Mensajes: 38
Registrado: Vie 02 Dic, 2022 9:57 pm
Nivel: 3

Re: P1N3 - Nacional OMA 2000

Mensaje sin leer por biank »

Comentario: se parece a este https://cses.fi/problemset/task/2431
Spoiler: mostrar
Hay $10^d - 10^{d - 1}$ números de $d$ dígitos, por lo que los números de $d$ dígitos van a ocupar $9 \cdot 10^{d - 1} \cdot d$ dígitos en total.

Sea $C(n)$ la cantidad de dígitos que ocupan los números de $d \leq n$ dígitos.

Veamos que $C(n) = \dfrac{10^n (9n - 1) + 1}{9}$
Spoiler: mostrar
$9 \cdot 1 + 90 \cdot 2 + \cdots + 9 \cdot 10^{n - 1} \cdot n = C(n) \\
90 \cdot 1 + 900 \cdot 2 + \cdots + 9 \cdot 10^{n} \cdot n = 10C(n) \\
9 + 90 + 900 + \cdots + 9 \cdot 10^{n - 1} - 9 \cdot 10^{n} \cdot n = -9C(n)$

Prueba de que $\sum_{x=0}^{n - 1} 9\cdot10^{x} = 10^{n} - 1$
Spoiler: mostrar
$S = 9 + 90 + 900 + \cdots + 9 \cdot 10^{n - 1} \\
10S = 90 + 900 + 9000 + \cdots + 9 \cdot 10^{n} \\
9S = 9 \cdot 10^{n} - 9 \\
S = 10^{n} - 1$
$10^{n} - 1 - 9 \cdot 10^{n} \cdot n = -9C(n)$
$\dfrac{10^n (9n - 1) + 1}{9} = C(n)$
Buscamos el menor $n$ donde $C(n) \geq 10^{2000}$.

Como llegué a la cota:
Spoiler: mostrar
$C(n) = 10^n (n - \frac{1}{9}) + \frac{1}{9}$
$\log_{10}(C(n)) = \log_{10}\left(10^n (n - \frac{1}{9}) + \frac{1}{9}\right) \approx n + \log_{10}(n)$
$n + \log_{10}(n) \geq 2000$

$n + \log_{10}(n)$ es creciente por lo que podemos acotar.
$\log_{10}(n) \leq 3 \Rightarrow n \leq 1000 \Rightarrow n + \log_{10}(n) \leq 1003$
Por lo que $\log_{10}(n) > 3 \Rightarrow n + \log_{10}(n) > n + 3$
$n + 3 \geq 2000 \Rightarrow n \geq 1997$
Comprobación:
Spoiler: mostrar
$\dfrac{10^n (9n - 1) + 1}{9} \geq 10^{2000}$
$10^n(9n - 1) \geq 9 \cdot 10^{2000} - 1$

Para $n=1997$ se cumple
$9 \cdot 1997 - 1 > 10^4$
$10^{1997}(9\cdot1997 - 1) > 10^{2001} = 10 \cdot 10^{2000} > 9 \cdot 10^{2000} - 1$

Para $n=1996$ no se cumple
$9\cdot 1996 - 1 < 2 \cdot 10^4$
$10^{1996}(9\cdot 1996 - 1) < 2 \cdot 10^{2000} < 9 \cdot 10^{2000} - 1$
Por lo que la respuesta son $1997$ dígitos.
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1128
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Re: P1N3 - Nacional OMA 2000

Mensaje sin leer por drynshock »

Este se va a la lista de tryhardeadas
Spoiler: mostrar
Ordenamos los números de $1$ digito, $2$ dígitos, $\dots$ cada uno con si grupito

$1, 2, \dots, 9$
$10, 11, \dots, 99$
$100, 101, \dots, 999$
$\vdots$

En el primer grupo tenemos $9$ números, en el segundo $90$, en el tercero $900$, en general en el grupo $k$ tenemos $9.10^{k-1}$ números. Y notemos que la posición del último digito de los números $9, 99, 999, 9999, \dots$ va a ser la suma

$$9\sum_{k=1}^{n}k.10^{k-1}= 9+2.9.10+3.9.10^2+4.9.10^3+\dots+9n.10^{n-1}$$

Siendo $n$ la cantidad de dígitos de $999\dots9$. Notemos que $[x^{k}]' = kx^{k-1}$ de donde es intuitivo ver que

$$S = \sum_{k=1}^{n}(k.x^{k-1}) \Rightarrow \int S dx = \int\sum_{k=1}^{n}(k.x^{k-1})dx = \sum_{k=1}^{n}\int(k.x^{k-1})dx = \sum_{k=1}^{n} x^{k}+c$$
Spoiler: mostrar
Bueno, en realidad el paso de arriba no hacia falta, pero hay que admitir que esas S se ven cool.
$$\therefore S = \bigg[\sum_{k=1}^{n} x^{k}\bigg]' = \bigg[\frac{x^{n+1}-x}{x-1}\bigg]' = \frac{((n+1)x^{n}-1)(x-1)-(x^{n+1}-x)}{(x-1)^2} = \frac{x^{n}((x-1)n-1)+1}{(x-1)^2}$$

Por lo tanto, si tomamos $x = 10$ obtenemos $9\sum_{k=1}^{n}k.10^{k-1} = \frac{10^{n}(9n-1)+1}{9}$.

Debemos acotar esa suma para que sea mayor a $10^{2000}$ (igual no puede ser por $\pmod 9$) y al mismo tiempo lo mas chica posible, es decir

$$10^{2000} < \frac{10^{n}(9n-1)+1}{9} \Rightarrow 9.10^{2000} \leq 10^{n}(9n-1) \Rightarrow \log(9.10^{2000}) \leq \log(10^{n}(9n-1))$$
$$\log(9)+2000 \leq n+\log(9n-1) \Rightarrow 0 \leq n+\log(9n-1)-\log(9)-2000$$

Y notar que $\log(9n-1) < \log(10n) < 1+\log n$ donde $\log n$ nos dice (con decimales) cuantos dígitos tiene $n$, entonces a simple vista podemos ver que $n = 1996$ o $n = 1997$, sin embargo si ponemos $n = 1996$ en la calculadora, vemos que no se cumple, mientras que $n = 1997$ si. Por lo tanto el menor $n$ posible es $1997$.
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
Responder