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 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1293
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
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^{1021} + \frac{2^{1021}-2}{3} - 511 = 2^{1019} + \frac{2^{1019}-2}{3} - 511$$
$$\dots$$
$$S = 2^{1021} + 2^{1019} + \dots + 2^3 + 2 - 511$$

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

$$S = 2^{1021} + 2^{1019} + \dots + 2^3 + 2 - (2^9 -1)$$
$$\boxed{S = 2^{1021} + 2^{1019} + \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 > 1021$$
Última edición por drynshock el Mié 24 Jul, 2024 2:12 pm, editado 1 vez en total.
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
Ignacio Daniele

OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Copa-FOFO 13 años OFO - Medalla de Plata-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024 FOFO 14 Años - Medalla-FOFO 14 años
Mensajes: 46
Registrado: Jue 26 May, 2022 8:27 pm
Medallas: 5
Nivel: Exolímpico

Re: Selectivo de Ibero 2002 P3

Mensaje sin leer por Ignacio Daniele »

Spoiler: mostrar
Usé la misma idea que @drynshock, para llegar a que:
$S=\frac{2^{1023}-2}{3}-511$
A continuación:
$S=\frac{1}{2} \times (\frac{2^{1024}-4}{3}-2^{10}+2)$
$S=\frac{1}{2} \times (\frac{4^{512}-1}{4-1}-4^{5}+1)$
Ahora uso esta notación:
$a_x$ es cómo se ve un cierto número escrito en base x.
Notemos que hay una suma geométrica, y se puede escribir la parte de la derecha fácilmente en base 4, quedando:
$S=\frac{1}{2}_{10} \times (111...111_4-100000_4+1_4)$
$S=\frac{1}{2}_{10} \times 111...11011112_4$
Teniendo el factor de la derecha 512 cifras.
Un truco que se puede hacer como 4 es potencia de 2, es reemplazar cada cifras de base 4 a x cifras de base 2, en este caso x=2, esto se puede demostrar sacando factor común.
Sacando las equivalencias:
$0_4=00_2$
$1_4=01_2$
$2_4=10_2$
$3_4=11_2$
Usando eso:
$S=\frac{1}{10}_2 \times 01010101...0101000101010110_2$
$S=\frac{01010101...010101000101010110_2}{10_2}$
La división es igual que en sistema decimal, entonces:
$S=10101010101...01010100010101011_2$
Teniendo ese número $512 \times 2 - 2 = 1022$ cifras, y ahí queda expresado el número S en binario, donde es fácil expresarlo según la paridad de $i$ con $i<1022$, pero con las excepciones de $i=0$ e $i=9$.
@drynshock, cuidado al final, que pusiste que $a_{1023}=1$, porque fijate que ya de entrada tenías que $S<2^{1023}$, entonces es imposible eso, me parece que en $\frac{2^k}{3}=2^{k-2}+\frac{2^{k-2}}{3}$, te olvidaste del $"-2"$ en el exponente en $2^{k-2}$ cuando lo aplicaste a $k=2023$.
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: 1293
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Re: Selectivo de Ibero 2002 P3

Mensaje sin leer por drynshock »

Ignacio Daniele escribió: Mié 24 Jul, 2024 12:52 pm
Spoiler: mostrar
Usé la misma idea que @drynshock, para llegar a que:
$S=\frac{2^{1023}-2}{3}-511$
A continuación:
$S=\frac{1}{2} \times (\frac{2^{1024}-4}{3}-2^{10}+2)$
$S=\frac{1}{2} \times (\frac{4^{512}-1}{4-1}-4^{5}+1)$
Ahora uso esta notación:
$a_x$ es cómo se ve un cierto número escrito en base x.
Notemos que hay una suma geométrica, y se puede escribir la parte de la derecha fácilmente en base 4, quedando:
$S=\frac{1}{2}_{10} \times (111...111_4-100000_4+1_4)$
$S=\frac{1}{2}_{10} \times 111...11011112_4$
Teniendo el factor de la derecha 512 cifras.
Un truco que se puede hacer como 4 es potencia de 2, es reemplazar cada cifras de base 4 a x cifras de base 2, en este caso x=2, esto se puede demostrar sacando factor común.
Sacando las equivalencias:
$0_4=00_2$
$1_4=01_2$
$2_4=10_2$
$3_4=11_2$
Usando eso:
$S=\frac{1}{10}_2 \times 01010101...0101000101010110_2$
$S=\frac{01010101...010101000101010110_2}{10_2}$
La división es igual que en sistema decimal, entonces:
$S=10101010101...01010100010101011_2$
Teniendo ese número $512 \times 2 - 2 = 1022$ cifras, y ahí queda expresado el número S en binario, donde es fácil expresarlo según la paridad de $i$ con $i<1022$, pero con las excepciones de $i=0$ e $i=9$.
@drynshock, cuidado al final, que pusiste que $a_{1023}=1$, porque fijate que ya de entrada tenías que $S<2^{1023}$, entonces es imposible eso, me parece que en $\frac{2^k}{3}=2^{k-2}+\frac{2^{k-2}}{3}$, te olvidaste del $"-2"$ en el exponente en $2^{k-2}$ cuando lo aplicaste a $k=2023$.
Gracias por avisar, ahí lo edite.
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
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: 1293
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Till kingdom come

Mensaje sin leer por drynshock »

Otra más sencilla
Spoiler: mostrar
Tenemos $2^2 \equiv 1 \pmod 3 \Rightarrow 2^{2k} \equiv 1 \pmod 3 \Rightarrow 2^{2k+1} \equiv 2 \pmod 3$, luego

\begin{equation}
\begin{split}
S &= \frac{1-1}{3}+\frac{2-2}{3} + \frac{2^2-1}{3}+\frac{2^3-2}{3}+\dots+\frac{2^{1022}-1}{3} \\
& = \frac{1+2+2^2+2^3+\dots+2^{1022}-1(\frac{1022}{2}+1)-2(\frac{1022}{2})}{3} \\
&\underset{\text{serie geo.}}{=} \frac{2^{1023}-1-512-1022}{3} \\
&= \frac{2^{1023}-1+2-1024-512}{3}\\
&= \frac{2^{1023}+1-3.2^9}{3} \\
&= \frac{2.4^{511}+1}{3}-2^9 \\
&= \frac{2.4^{511}-2+3}{3}-2^{9}\\
&= 2\frac{4^{511}-1}{3}+1-2^{9}\\
&\underset{\text{serie geo.}}{=}2(1+4+4^2+\dots+4^{510})+1-2^{9} \\
&= 1+2+2^3+2^5+2^7+2^{11}+2^{13}+\dots+2^{1021} \\
\end{split}
\end{equation}

Entonces
$1 = a_0 = a_1 = a_3 = \dots = a_7 = a_{11} = a_{13} = \dots = a_{1021}$
$0 = a_2 = a_4 = a_6 = a_8 = a_9 = a_{10} = a_{12} = \dots = a_{1020}$
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
Responder