IMO 2019 - P4

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

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018
FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 149
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 15
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: IMO 2019 - P4

Mensaje sin leer por AgusBarreto »

El enfoque es el mismo que en otras, pero hay algunos detalles distintos y me gustó bastante (hay números combinatorios :o ).

Un pequeño cálculo auxiliar:
Spoiler: mostrar
Dado un entero $q \geq 0$, tenemos que por Legendre $v_2((2^q)!)=\dfrac{2^q}{2}+\dfrac{2^q}{4}+\cdots+\dfrac{2^q}{2^q}=2^{q-1}+2^{q-2}+\cdots+1=2^q-1$.
Ahora sí:
Spoiler: mostrar
Primero calculemos la cantidad de factores $2$ del lado derecho de la ecuación. Para eso, reescribamoslo como $\dfrac{(2^{n}-1)!}{(2^{n-1}-1)!}$.
La cantidad de factores $2$ del numerador es la misma que la de $(2^n)!$ pero restándole los $n$ factores $2$ que aporta $2^n$ al factorial. Es decir, $$v_2((2^n-1)!)=v_2((2^n)!)-n=2^n-1-n$$ Razonando de la misma forma con el denominador obtenemos $$v_2((2^{n-1}-1)!)=v_2((2^{n-1})!)-(n-1)=2^{n-1}-1-(n-1)=2^{n-1}-n$$ y finalmente, la cantidad de factores $2$ de la fracción incial es la resta entre los dos números recién calculados, o sea $$v_2\left(\dfrac{(2^{n}-1)!}{(2^{n-1}-1)!}\right)=2^n-1-n-(2^{n-1}-n)=2^{n-1}-1$$ Como esa fracción es igual a $k!$ concluímos que $v_2(k!)=2^{n-1}-1=v_2((2^{n-1})!)$ y como el valor $v_2(k!)$ crece con $k$ (de hecho, mientras $k$ aumenta, crece estrictamente cada vez que pasamos por un $k$ par), esto nos dice que o bien $k=2^{n-1}$ o bien $k=2^{n-1}+1$. El problema está casi terminado, veamos los dos casos:

Caso 1: $k=2^{n-1}$
Spoiler: mostrar
$$(2^{n-1})!=\dfrac{(2^{n}-1)!}{(2^{n-1}-1)!} \iff 1=\dfrac{(2^{n}-1)!}{(2^{n-1}-1)!(2^{n-1})!} = \binom{2^n-1}{2^{n-1}-1}$$ y esto sólo ocurre cuando $2^{n-1}-1=2^n-1$ (que no es posible) o cuando $2^{n-1}-1=0$, que nos dice $2^{n-1}=1$ y por lo tanto $n=1$. Este caso nos devuelve como solución el par $(k,n)=(1,1)$.
Caso 2: $k=2^{n-1}+1$
Spoiler: mostrar
$$(2^{n-1}+1)!=\dfrac{(2^{n}-1)!}{(2^{n-1}-1)!} \iff 2^n=\dfrac{(2^{n})!}{(2^{n-1}-1)!(2^{n-1}+1)!} = \binom{2^n}{2^{n-1}-1}$$ y esto sólo ocurre cuando $2^{n-1}-1=2^n-1$ (que no es posible) o cuando $2^{n-1}-1=1$, que nos dice $2^{n-1}=2$ y por lo tanto $n=2$. Este caso nos devuelve como solución el par $(k, n)=(3,2)$.
Las soluciones al problema son entonces $(k,n)=(1,1)$ y $(k, n)=(3,2)$. ■
4  

Responder