Entrenamiento Ibero 2019 P14

Problemas que aparecen en el Archivo de Enunciados.
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 202
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Entrenamiento Ibero 2019 P14

Mensaje sin leer por Matías » Dom 22 Dic, 2019 10:36 pm

Sea $n\geq 3$ entero, y sea $1\leq a<2^n$ un entero impar. Definimos $c(a)$ como el menor entero no negativo tal que $a^{2^{c(a)}}-1$ es múltiplo de $2^n$. Hallar el valor de la suma
$$\sum_{k=1}^{2^{n-1}}c(2k-1)$$

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 356
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Entrenamiento Ibero 2019 P14

Mensaje sin leer por Joacoini » Lun 23 Dic, 2019 9:44 pm

Spoiler: mostrar
Lifiting the Exponent para $p=2$ nos dice que si $x$ e $y$ son impares y $m$ es par entonces

$v_2(x^m-y^m)=v_2(x-y)+v_2(x+y)+v_2(m)-1$

Veamos que para $1<a<2^n-1$, $c(a)=n+1-v_2(a-1)-v_2(a+1)$

$v_2(a^{2^{c(a)}}-1)=v_2(a-1)+v_2(a+1)+v_2(2^{c(a)})-1=v_2(a-1)+v_2(a+1)+n+1-v_2(a-1)-v_2(a+1)-1=n$

Y si $c(a)<n+1-v_2(a-1)-v_2(a+1)\Rightarrow v_2(a^{2^{c(a)}}-1)<v_2(a-1)+v_2(a+1)+n+1-v_2(a-1)-v_2(a+1)-1=n$

La justificación de arriba no sirve para $c(a)=0$ ya que en LTE se requiere que el exponente sea par pero como $1<a<2^n-1$ tenemos que $c(a)\neq 0$, el caso de $a=1$ lo apartamos por esta razón ya que en este $c(1)=0$.

Para $a=2^n-1$ lo que pasa es que $n+1-v_2(2^n-2)-v_2(2^n)=0$ y no podemos usar LTE para ver si anda y como no anda y $1$ si tenemos que $c(2^n-1)=1=n+1-v_2(2^n-2)-v_2(2^n)+1$.


$\sum_{k=1}^{2^{n-1}}c(2k-1)=(2^{n-1}-1)(n+1)-v_2(2)-v_2(4)-v_2(4)-...-v_2(2^n-2)-v_2(2^n-2)-v_2(2^n)+1=(2^{n-1}-1)(n+1)-2(v_2(2)+v_2(4)+...+v_2(2^n-2)+v_2(2^n))+v_2(2)+v_2(2^n)+1$

Pero como
$v_2(2)+v_2(4)+...+v_2(2^n-2)+v_2(2^n)=\frac{2^n}{2}+\frac{2^n}{2^2}+...+\frac{2^n}{2^n}=2^{n-1}+2^{n-2}+...+1=2^n-1$

$\sum_{k=1}^{2^{n-1}}c(2k-1)=(2^{n-1}-1)(n+1)-2(2^n-1)+v_2(2)+v_2(2^n)+1=(2^{n-1}-1)(n+1)-2^{n+1}+2+1+n+1=2^{n-1}(n+1)-2^{n+1}+3=2^{n-1}(n-3)+3$
NO HAY ANÁLISIS.

Responder