Selectivo de Ibero 2002 P3

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

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

Selectivo de Ibero 2002 P3

Mensaje sin leer por Ivan »

Se considera la suma de [math] sumandos
[math]

Sea [math] la sucesión de [math] y [math] formada, respectivamente, por los coeficientes de [math] en el desarrollo binario de [math]. Hallar la sucesión [math].

Aclaración: Los corchetes indican la parte entera del número que encierran.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Selectivo de Ibero 2002 P3

Mensaje sin leer por Prillo »

Spoiler: mostrar
Tenemos que [math]. Pero [math] y [math], luego [math]. Ahora bien, notemos que
[math]
Por lo tanto, la sucesión [math] verifica [math] si [math], [math] si [math]; [math] si [math] es par mayor que [math], y [math].
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
Mensajes: 686
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 3
Nivel: 3
Contactar:

Re: Selectivo de Ibero 2002 P3

Mensaje sin leer por drynshock »

Prillo escribió: Jue 17 Ene, 2013 12:01 am
Spoiler: mostrar
$\dots$ y $a_9=a_0=1$.
Me parece que fue un error de tipeo ya que
Spoiler: mostrar
$a_9 = 0$ en vez de $1$
Acá mi solución
Spoiler: mostrar
Veamos una idea bastante útil, si tenemos cuatro números, $a, b, r, q$ siendo $r$ el resto en la división de $a$ por $b$ y $q$ el cociente, entonces se cumple que $a = q.b + r \Rightarrow \lfloor \frac{a}{b} \rfloor = \lfloor \frac{q.b+r}{b} \rfloor = \lfloor q + \frac{r}{b} \rfloor = q + \lfloor \frac{r}{b} \rfloor$ Dado que $r < b$ entonces $\lfloor \frac{r}{b} \rfloor = 0$. Esto nos dice que
$$\boxed{\bigg\lfloor \frac{a}{b} \bigg\rfloor = \bigg\lfloor \frac{a-r}{b} \bigg\rfloor = \frac{a-r}{b}}$$

Ahora podemos aplicar este resultado para sacarnos de encima la función piso. Para continuar, $2^2 \equiv 1 \pmod 3 \Rightarrow 2^{2k} \equiv 1 \pmod 3 \Rightarrow 2^{2k+1} \equiv 2 \pmod 3$.

$$S = \bigg\lfloor \frac{1}{3} \bigg\rfloor + \bigg\lfloor \frac{2}{3} \bigg\rfloor + \dots + \bigg\lfloor \frac{2^{1022}}{3} \bigg\rfloor$$
$$S = \frac{1-1}{3} + \frac{2-2}{3} + \dots + \frac{2^{1022}-1}{3}$$
$$S = \frac{1-1+2-2+2^2-1+2^3-2+\dots+2^{1022}-1}{3}$$

Notar que la cantidad de términos con $-1$ que aparecen son $\frac{1022}{2} + 1 = 512$ y la cantidad de $-2$ que aparecen son $\frac{1022}{2} = 511$ debido a esto se cumple que:

$$S = \frac{1+2+2^2+\dots 2^{1022} -512 - 511.2}{3}$$


Y también por suma geométrica es cierto que $1+2+\dots+2^{1022} = 2^{1023}-1$. Por consiguiente:

$$S = \frac{2^{1023}-1 - 512 - 511.2}{3} = \frac{2^{1023} - 2 - 511 - 511.2}{3} = \frac{2^{1023} - 2 - 511.3}{3}$$

$$\boxed{S = \frac{2^{1023} - 2}{3} - 511}$$

Ahora que tenemos $S$ veamos el siguiente truco. Estamos familiarizados con expresar números en forma polinómica en base $10$, por ejemplo $2489 = 9 + 10.8 + 4.10^2 + 2.10^3$. Sin embargo, es cierto que esto también funciona en base $2$ y por lo tanto lo que debemos hacer es expresar $S$ de la siguiente manera $S = a_0 + a_1.10 + a_2.10^2 + a_3.10^3 + \dots$ con $a_i = 0, 1$. Entonces, intentemos llegar a eso:

Veamos que si tenemos $\frac{2^k}{3} = \frac{2^{k-2}.2^2}{3} = \frac{2^{k-2} + 3.2^{k-2}}{3} = \frac{2^{k-2}}{3} + 2^{k-2}$. Por esta razón podemos ir separando $\frac{2^{1023}-2}{3}$ en varios términos como se ve a continuación:

$$S = \frac{2^{1023} - 2}{3} - 511 = 2^{1023} + \frac{2^{1021}-2}{3} - 511 = 2^{1021} + \frac{2^{1019}-2}{3} - 511$$
$$\dots$$
$$S = 2^{1023} + 2^{1021} + \dots + 2^3 + 2 - 511$$

Ahora veamos que $511 = 512 - 1 = 2^9 - 1$, luego se cumple que:

$$S = 2^{1023} + 2^{1021} + \dots + 2^3 + 2 - (2^9 -1)$$
$$\boxed{S = 2^{1023} + 2^{1021} + \dots + 2^{13} + 2^{11} + 2^{7} + 2^5 + 2^3 + 2 + 1}$$

¡Exactamente como queríamos! Entonces la sucesión va a quedar de la siguiente forma:

$$a_0 = a_{2i+1} = 1, 2i+1 \leq 1023 \land 2i+1 \neq 9$$
$$a_9 = a_{2i} = 0, i > 0$$
$$a_i = 0, i > 1023$$
@Bauti.md ig
Math: Mental Abuse To Human
Responder