Página 1 de 2

IMO 2019 - P4

Publicado: Mié 17 Jul, 2019 9:12 am
por Matías V5
Encontrar todos los pares $(k,n)$ de enteros positivos tales que$$k!=\left (2^n-1\right )\left (2^n-2\right )\left (2^n-4\right )\cdots \left (2^n-2^{n-1}\right ).$$

Re: IMO 2019 - P4

Publicado: Mié 17 Jul, 2019 2:09 pm
por jujumas
Adefesio

Solución:
Spoiler: mostrar
Sea $v_p(n)$ el exponente del primo $p$ en la factorización de $n$, sabemos que $v_3(k!)=v_3(\prod_{i=0}^{n-1} (2^n - 2^i))$. Claramente, $v_3(2^n-2^i) =v_3(2^i) + v_3(2^{n-i}-1)=v_3(2^{n-i}-1)$. Ahora, viendo la expresión módulo $3$ tenemos que esto es $0$ sí y sólo sí $n-i$ es impar. Luego, tenemos que:

$$v_3(\prod_{i=0}^{n-1} (2^n - 2^i)) = v_3 ((2-1)(2^2-1)(2^3-1)\dots(2^n-1)) = v_3 ((2^2-1)(2^4-1)\dots(2^{2 \lfloor \frac{n}{2} \rfloor}-1))$$

y esto último es igual a $v_3((4-1)(4^2-1)\dots(4^{\lfloor \frac{n}{2} \rfloor}-1))$. Ahora, como $3$ divide exactamente a $4-1$ y no divide ni a $4$ ni a $1$, podemos aplicar Lifting The Exponent y ver que $v^3(4^k-1)=v_3(k)+v_3(4-1)=v_3(k)+1$. Tenemos entonces que la valuación buscada es $\lfloor \frac{n}{2} \rfloor + v_3(1) + v_3(2) + \dots + v_3(\lfloor \frac{n}{2} \rfloor)$ y esto último resulta ser igual a:

$$\lfloor \frac{n}{2} \rfloor + \lfloor \frac{\lfloor \frac{n}{2} \rfloor}{3} \rfloor + \lfloor \frac{\lfloor \frac{n}{2} \rfloor}{3^2} \rfloor + \lfloor \frac{\lfloor \frac{n}{2} \rfloor}{3^3} \rfloor + \dots $$

Pero notemos ahora que $v_3(x!) = \lfloor \frac{x}{3} \rfloor + \lfloor \frac{x}{9} \rfloor + \dots $. Luego, tenemos que $v_3(3\lfloor \frac{n}{2} \rfloor)$ es exactamente esto, y que $v_3(k!)=v_3(3\lfloor \frac{n}{2} \rfloor!)$. Luego, el producto de los enteros positivos consecutivos entre $k$ y $3\lfloor \frac{n}{2} \rfloor$ no es múltiplo de $3$, de donde o bien $k=3\lfloor \frac{n}{2} \rfloor$, $k=3\lfloor \frac{n}{2} \rfloor + 1$ o $k=3\lfloor \frac{n}{2} \rfloor + 2$.

Vayamos entonces a la igualdad original (sin valuaciones): notemos que el lado izquierdo es menor o igual a $(3\lfloor \frac{n}{2} \rfloor + 2)!$ y el lado derecho es mayor a $(2^{n-1})^n)$. Luego, $(3\lfloor \frac{n}{2} \rfloor + 2)! > (2^{n-1})^n$. Notemos que si $n=5$ y $n=6$ esta desigualdad no se da y si no se da para $n=2m$, tampoco se va a dar para $n=2m+1$, ya que el lado derecho crece y el izquierdo no.

Entonces, para demostrar que la desigualdad no se cumple salvo para $n$ menor a $5$, vemos que $n=6$ no cumple, y si $n=2k$ no cumple, $n=2k+2$ tampoco ya que el lado izquierdo se multiplica por $(3k+3)(3k+4)(3k+5)$ y el lado derecho por $2^{8k+2}$, y $(3k+3)(3k+4)(3k+5)$ es menor a $2^{8k+2}$ para $k$ mayor o igual a $3$, ya que si $k=3$ es menor, y el lado izquierdo es una cúbica y el derecho una exponencial que crece más rápido.

Entonces, solo nos queda examinar los casos $n=1$, $n=2$, $n=3$, $n=4$ y obtenemos que las únicas soluciones son $k=1$, $n=1$ y $k=3$, $n=2$.

Re: IMO 2019 - P4

Publicado: Mié 17 Jul, 2019 7:50 pm
por Matías V5
Plan de solución (se puede leer a modo de pista):
Spoiler: mostrar
Podemos calcular (en función de $n$) cuántos factores $2$ tiene el lado derecho de la ecuación. Para que en $k!$ pueda haber esa cantidad de factores $2$, $k$ tiene que ser "grande". Pero si el $k$ es así de grande ocurre (salvo para valores muy pequeños de $n$) que $k!$ es más grande que el lado derecho. Por lo tanto no va a haber soluciones, salvo que $n$ sea muy chico.
Solución:
Spoiler: mostrar
Notemos que, para $j = 0,1,2,\ldots,n-1$, $2^n - 2^j = 2^j (2^{n-j}-1)$, y como el segundo factor es impar, vemos que $2^n - 2^j$ tiene exactamente $j$ factores $2$ en su descomposición en primos. Sumando esto sobre todos los $j$ obtenemos que el exponente del $2$ en la factorización de la expresión del lado derecho de la ecuación es $1+2+\ldots+(n-1)$.
Es un hecho conocido que el exponente del $2$ en la factorización de $k!$ se puede calcular haciendo la suma $\left \lfloor \frac{k}{2} \right \rfloor + \left \lfloor \frac{k}{2^2} \right \rfloor + \left \lfloor \frac{k}{2^3} \right \rfloor + \ldots + \left \lfloor \frac{k}{2^m} \right \rfloor$ donde $2^m$ es la mayor potencia de $2$ menor o igual que $k$. Esta suma es menor o igual que la suma análoga sin las partes enteras, es decir
$\frac{k}{2} + \frac{k}{2^2} + \frac{k}{2^3} + \ldots + \frac{k}{2^m} = k \left( \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \ldots + \frac{1}{2^m} \right) = k \left( 1 - \frac{1}{2^m} \right) < k.$
Dicho de otra forma, hay menos de $k$ factores $2$ en $k!$. Combinando esto con la observación anterior vemos que para que se pueda cumplir la igualdad del enunciado es necesario que $k$ sea mayor o igual que $1+2+\ldots+(n-1)$.
Ahora viene la parte más fea. Llamemos $F(n) = 1+2+\ldots+(n-1)$ y $G(n)$ al lado derecho de la ecuación del enunciado, es decir $G(n) = (2^n -1)(2^n - 2)(2^n - 4) \cdots (2^n - 2^{n-1})$. Vamos a probar que, si $n \geq 6$, entonces $F(n)! > G(n)$. De esto se deduce que no hay soluciones del problema con $n \geq 6$, ya que en ese caso tendríamos $k! \geq F(n)! > G(n)$.
La demostración será por inducción, pero antes necesitamos hacer un par de observaciones que nos van a servir para el paso inductivo.
La primera es que $F(n+1) = F(n)+n$ y en consecuencia
$F(n+1)! = F(n)! \times \left[ F(n)+1 \right] \left[ F(n)+2 \right] \cdots \left[ F(n)+n \right] > F(n)! \times n^n$,
donde en el último paso hemos usado simplemente que cada uno de los factores que agregamos al producto es mayor que $n$.
La segunda es que $G(n+1)$ se puede obtener multiplicando por $2$ cada uno de los $n$ factores que forman a $G(n)$ y agregando el factor $2^{n+1} - 1$. Es decir,
$G(n+1) = 2^n \times (2^{n+1} - 1) \times G(n) < 2^n \times 2^{n+1} \times G(n) = 2^{2n+1} \times G(n) = 2 \times 4^n \times G(n).$
Ahora sí, probemos lo que habíamos anticipado.

Lema: Para todo $n \geq 6$ es $F(n)! > G(n)$.
Demostración. Para $n=6$ tenemos $F(6)=1+2+3+4+5=15$ y
$G(6) = (64-1)(64-2)(64-4)(64-8)(64-16)(64-32) = 63 \cdot 62 \cdot 60 \cdot 56 \cdot 48 \cdot 32 < 64^6 = 2^{36}.$
Por otro lado, $15! > 7! \cdot 8^8 = 7! \cdot 2^{24}$, y como $7! = 5040 > 2^{12} = 4096$, nos queda $F(6)! = 15! > 2^{36} > G(6)$, como queríamos.
Ahora, supongamos que para cierto $n \geq 6$ se cumple $F(n)! > G(n)$ y veamos que $F(n+1)! > G(n+1)$. En efecto, por las observaciones hechas anteriormente tenemos que
$F(n+1)! > n^n \times F(n)! > n^n \times G(n) \geq 6^n \times G(n) > 2 \times 4^n \times G(n) > G(n+1).$
(Usamos que $6^n > 2 \times 4^n$, lo cual equivale a que $1.5^n > 2$, que es verdadero para todo $n \geq 2$.)
La inducción está completa. $\blacksquare$

Con todo el trabajo anterior sabemos que no hay soluciones del problema con $n \geq 6$. Sólo falta ver cuáles de los primeros $5$ valores de $G$ son factoriales. $G(1) = 1 = 1!$, $G(2) = 3 \cdot 2 = 3!$. Ahora (usando una de las observaciones anteriores),
$G(3) = 4 \cdot 7 \cdot G(2) = 7 \cdot 4!,$ que es mayor que $5!$ pero menor que $6!$;
$G(4) = 8 \cdot 15 \cdot G(3) = 4 \cdot (2 \cdot 3) \cdot 5 \cdot 7 \cdot 4! = 4 \cdot 7!,$ que es mayor que $7!$ pero menor que $8!$; y
$G(5) = 16 \cdot 31 \cdot G(4) = 8 \cdot 31 \cdot 8!,$ que es mayor que $10!$ pero menor que $11!$.
Concluimos que los únicos pares $(k,n)$ que cumplen lo pedido son $(1,1)$ y $(3,2)$. $\blacksquare$

Re: IMO 2019 - P4

Publicado: Mié 24 Jul, 2019 8:36 pm
por Martín Vacas Vignolo
Usando la observación de Mati sobre la cantidad de factores 2 a la derecha, y acotando el lado derecho, tenemos que:

$(\frac{n(n-1)}{2})!<2^nn<2^n2^n=4^n$ (*)

Ahora, notemos que si $n\geq 5$ se cumple que $\frac{n(n-1)}{2}>n+3>4$. Es decir, del lado izquierdo tenemos al menos $n$ términos mayores o iguales que $4$, y por lo tanto su producto será mayor o igual que $4^n$, haciendo imposible que se cumpla (*). Luego, queda chequear a mano los casos $n\leq 4$.

Re: IMO 2019 - P4

Publicado: Mié 24 Jul, 2019 9:54 pm
por Gianni De Rico
Martín Vacas Vignolo escribió: Mié 24 Jul, 2019 8:36 pm Usando la observación de Mati sobre la cantidad de factores 2 a la derecha, y acotando el lado derecho, tenemos que:

$(\frac{n(n-1)}{2})!<2^nn$
No termino de entender de dónde sale esto, pero fijate que en ese caso
Spoiler: mostrar
En el lado izquierdo tenés más de $n+1$ términos, de los cuales $n$ son mayores que $2$ y el otro es mayor que $n$ (o podés hacer inducción) para $n\geqslant 4$. Entonces ya tenés la contradicción y solamente hay que checkear para $n\leqslant 3$.

Re: IMO 2019 - P4

Publicado: Jue 25 Jul, 2019 4:23 pm
por BrunZo
Solución:
Spoiler: mostrar
No es difícil de ver que la valuación $p$-ádica de $k!$ viene dada por
$$v_p(k!)=\left\lfloor\frac{k}{p}\right\rfloor+\left\lfloor\frac{k}{p^2}\right\rfloor+\left\lfloor\frac{k}{p^3}\right\rfloor+\cdots$$
En particular
$$v_2(k!)=\left\lfloor\frac{k}{2}\right\rfloor+\left\lfloor\frac{k}{4}\right\rfloor+\left\lfloor\frac{k}{8}\right\rfloor+\cdots<\frac{k}{2}+\frac{k}{4}+\frac{k}{8}+\cdots=k$$
$$v_3(k!)=\left\lfloor\frac{k}{3}\right\rfloor+\left\lfloor\frac{k}{9}\right\rfloor+\left\lfloor\frac{k}{27}\right\rfloor+\cdots>\frac{k}{3}$$
donde la última desigualdad vale para $k\geq 9$. (*)

Por otro lado, tenemos que
$$P_n=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})=2^{\frac{n(n-1)}{2}}(2^n-1)(2^{n-1}-1)(2^{n-2}-1)\cdots (2-1)$$
Esto es
$$v_2(P_n)=\frac{n(n-1)}{2}$$
Ahora, vamos a usar el siguiente Lema conocido:
Si $g$ es una raíz primitiva módulo $p$ y módulo $p^2$, entonces $g$ es una raíz primitiva módulo $p^n$, para todo $n$.
En particular, como $2$ es raíz primitiva módulo $3$ y módulo $9$ (se chequea a mano), entonces lo es módulo $3^n$. Esto es $\text{ord}_{3^n}(2)=\varphi(3^n)=2\cdot 3^{n-1}$, lo que implica implica
$$v_3(P_n)=\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{6}\right\rfloor+\left\lfloor\frac{n}{18}\right\rfloor+\cdots<\frac{n}{2}+\frac{n}{6}+\frac{n}{18}=\frac{3}{4}n$$
Ahora, tener $k!=P_n$ implica $v_2(k!)=v_2(P_n)$ y $v_3(k!)=v_3(P_n)$, de lo que salen las desigualdades
$$k>\frac{n(n-1)}{2}$$
$$\frac{k}{3}<\frac{3}{4}n$$
Lo cual implica $\frac{n(n-1)}{2}<\frac{9}{4}n\Longrightarrow n-1<\frac{9}{2}$, que deja los casos $n=1$, $n=2$, $n=3$, $n=4$, $n=5$. Notemos que, además, los otros casos dejan $k>15$, por lo que no habría ningún problema con (*).
Finalmente, de los casos salen las soluciones $(1,1)$, $(2,3)$.

Re: IMO 2019 - P4

Publicado: Lun 29 Jul, 2019 12:03 am
por Matías
Spoiler: mostrar
Para $n=1$ tenemos que $\prod\limits_{i=0}^{n-1}\left (2^n-2^i\right )=(2-1)=1=1!$, el par $(1,1)$ cumple.
Para $n=2$ tenemos que $\prod\limits_{i=0}^{n-1}\left (2^n-2^i\right )=(4-1)(4-2)=6=3!$, el par $(3,2)$ cumple.
Para $n=3$ tenemos que $\prod\limits_{i=0}^{n-1}\left (2^n-2^i\right )=(8-1)(8-2)(8-4)=168$ no es factorial, así que $n\neq 3$.
Para $n=4$ tenemos que $\prod\limits_{i=0}^{n-1}\left (2^n-2^i\right )=(16-1)(16-2)(16-4)(16-8)=20160$ no es factorial, así que $n\neq 4$.

Lema: $\forall(n\in N\wedge n\geq 5)$
$2^{\left (n^2\right )}<\left (\frac{(n-1)n}{2}+1\right )!$
Spoiler: mostrar
Para $n=5$ tenemos que
$2^{25}=33554432<39916800=11!$
Ahora, si se cumple para $n$, para $n+1$ también, ya que como
$\forall(n\in N\wedge n\geq 5)$
$2^{2n+1}<\prod\limits_{i=\frac{(n-1)n}{2}+2}^{\frac{n(n+1)}{2}+1}i$
(ya que $2^{2n+1}=8\prod\limits_{i=1}^{n-1}4$ es el producto de $n$ números naturales menores o iguales a $8$, mientras que $\prod\limits_{i=\frac{(n-1)n}{2}+2}^{\frac{n(n+1)}{2}+1}i$ es el producto de $n$ números naturales mayores o iguales a $\frac{(n-1)n}{2}+2\geq\frac{4\times 5}{2}+2=12$)
Nos queda que
$2^{(n+1)^2}=2^{\left (n^2\right )}2^{2n+1}<\left (\frac{(n-1)n}{2}+1\right )!\prod\limits_{i=\frac{(n-1)n}{2}+2}^{\frac{n(n+1)}{2}+1}i=\left (\frac{n(n+1)}{2}+1\right )!$
Supongamos que para cierto $n\in N$, $n\geq 5$ existe $k\in N/k!=\prod\limits_{i=0}^{n-1}\left (2^n-2^i\right )$.
Como $\prod\limits_{i=0}^{n-1}\left (2^n-2^i\right )=2^{\frac{(n-1)n}{2}}\prod\limits_{i=1}^{n}(2^i-1)$ tenemos que $v_2(k!)=\frac{(n-1)n}{2}$.
Además, $v_2(k!)=\sum\limits_{r=1}^{\infty}\left \lfloor\frac{k}{2^r}\right \rfloor<\sum\limits_{r=1}^{\infty}\frac{k}{2^r}=k$, así que $v_2(k!)\leq k-1$ y $k\geq\frac{(n-1)n}{2}+1$.
Pero entonces nos queda que
$\left (\frac{(n-1)n}{2}+1\right )!\leq k!=\prod\limits_{i=0}^{n-1}\left (2^n-2^i\right )<\prod\limits_{i=0}^{n-1}2^n=2^{\left (n^2\right )}$ (absurdo).
Así que $n<5$.

Por lo tanto concluimos que los dos pares que cumplen son $(1,1)$ y $(3,2)$.

Re: IMO 2019 - P4

Publicado: Jue 26 Dic, 2019 4:51 pm
por Gianni De Rico
Solución:
Spoiler: mostrar
Notemos que como $\left (2^n-2^i\right )=2^i\left (2^{n-i}-1\right )$, entonces$$P=\prod \limits _{i=0}^{n-1}\left (2^n-2^i\right )=\prod \limits _{i=0}^{n-1}2^i\left (2^{n-i}-1\right )=2^{\frac{(n-1)n}{2}}\cdot \prod \limits _{i=0}^{n-1}\left (2^{n-i}-1\right )$$de donde$$v_2(P)=v_2\left (2^{\frac{(n-1)n}{2}}\right )+\sum \limits _{i=0}^{n-1}v_2\left (2^{n-i}-1\right )=\frac{(n-1)n}{2}$$Como $k!=P$, tenemos que $v_2(k!)=v_2(P)=\frac{(n-1)n}{2}$, pero por la Fórmula de Legendre$$v_2(k!)=\sum \limits _{j=0}^{\infty}\left \lfloor \frac{k}{2^j}\right \rfloor <\sum \limits _{j=1}^{\infty}\frac{k}{2^j}=k$$Entonces$$\frac{(n-1)n}{2}<k\quad (1)$$Ahora, por Lifting The Exponent, tenemos que, para $0\leqslant i\leqslant n-1$$$v_3\left (2^{n-i}-1\right )=v_3(2-1)+\nu _3(n-i)=v_3(n-i)$$si $n\equiv i\pmod 2$ y$$v_3\left (2^{n-i}-1\right )=0$$en otro caso, luego$$v_3(P)=v_3\left (2^{\frac{(n-1)n}{2}}\right )+\sum \limits _{i=0}^{n-1}v_3\left (2^{n-i}-1\right )=\sum \limits _{0\leqslant i\leqslant n-1,~i\equiv n\pmod 2}v_3(n-i)\leqslant \sum \limits _{i=0}^{n-1}v_3(n-i)=\sum \limits _{i=1}^nv_3(i)=v_3\left (\prod \limits _{i=1}^ni\right )=v_3(n!)$$Como $k!=P$, tenemos $v_3(k!)=v_3(P)\leqslant v_3(n!)$.
Supongamos que $k\geqslant n+3$, luego$$v_3(n!)\geqslant v_3(k!)=v_3(n!)+v_3((n+1)(n+2)(n+3))+v_3\left (\prod \limits _{r=4}^{k-n}(n+r)\right )\geqslant v_3(n!)+v_3((n+1)(n+2)(n+3))$$de donde $v_3((n+1)(n+2)(n+3))\leqslant 0$, pero $3\mid (n+1)(n+2)(n+3)$, por lo que $1\leqslant v_3((n+1)(n+2)(n+3))$, luego, $1\leqslant 0$, absurdo pues $1>0$.
Entonces$$k\leqslant n+2\quad (2)$$De $(1)$ y $(2)$ se sigue que$$\frac{(n-1)n}{2}<n+2$$por lo que$$n^2-3n-4<0$$Las raíces de $n^2-3n-4$ son $-1$ y $4$, y como el coeficiente principal de esta cuadrática es positivo, entonces es convexa, de donde toma valores negativos cuando $-1<n<4$. Como $n\in \mathbb{N}$, resulta $1\leqslant n\leqslant 3$.
Si $n=1$, tenemos $k!=2-1=1$, de donde $k=1$.
Si $n=2$, tenemos $k!=(4-1)(4-2)=3\cdot 2=6$, de donde $k=3$.
Si $n=3$ tenemos $k!=(8-1)(8-2)(8-4)=7\cdot 6\cdot 4$, que no tiene soluciones al ser múltiplo de $7$ pero no de $5$, pues ambos son primos y $7>5$.

Entonces los únicos pares $(k,n)$ que cumplen son $(1,1)$ y $(3,2)$.

Re: IMO 2019 - P4

Publicado: Sab 28 Dic, 2019 9:54 pm
por Hernan26
Para usar lifting no tenes que asegurarte que $p$ divida a $x-y$? en este caso $3$ no divide a $2-1$.

Re: IMO 2019 - P4

Publicado: Sab 28 Dic, 2019 11:27 pm
por Gianni De Rico
Tenés razón, creo que entonces llegué a la misma solución que Masli, jajaja