IMO 2019 - P4

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

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 925
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

IMO 2019 - P4

Mensaje sin leer por Matías V5 » Mié 17 Jul, 2019 9:12 am

Encontrar todos los pares $(k,n)$ de enteros positivos tales que
$k! = (2^n - 1)(2^n - 2)(2^n - 4) \cdots (2^n - 2^{n-1})$.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 380
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 10
Nivel: 2

Re: IMO 2019 - P4

Mensaje sin leer por jujumas » Mié 17 Jul, 2019 2:09 pm

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$.
1  

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 925
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Re: IMO 2019 - P4

Mensaje sin leer por Matías V5 » Mié 17 Jul, 2019 7:50 pm

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$
1  
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 400
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Re: IMO 2019 - P4

Mensaje sin leer por Martín Vacas Vignolo » 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<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$.
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 1042
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: IMO 2019 - P4

Mensaje sin leer por Gianni De Rico » Mié 24 Jul, 2019 9:54 pm

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$.
[math]

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 143
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: IMO 2019 - P4

Mensaje sin leer por BrunZo » Jue 25 Jul, 2019 4:23 pm

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)$.

Matías

OFO - Medalla de Bronce FOFO Pascua 2019 - Medalla OFO - Medalla de Plata FOFO 8 años - Medalla Especial OFO - Medalla de Oro
Mensajes: 189
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 7
Nivel: 3

Re: IMO 2019 - P4

Mensaje sin leer por Matías » Lun 29 Jul, 2019 12:03 am

Spoiler: mostrar
Para $n=1$ tenemos que $\prod_{i=0}^{n-1}(2^n-2^i)=(2-1)=1=1!$, el par $(1,1)$ cumple.
Para $n=2$ tenemos que $\prod_{i=0}^{n-1}(2^n-2^i)=(4-1)(4-2)=6=3!$, el par $(3,2)$ cumple.
Para $n=3$ tenemos que $\prod_{i=0}^{n-1}(2^n-2^i)=(8-1)(8-2)(8-4)=168$ no es factorial, así que $n\neq 3$.
Para $n=4$ tenemos que $\prod_{i=0}^{n-1}(2^n-2^i)=(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^{(n^2)}<(\frac{(n-1)n}{2}+1)!$
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_{i=\frac{(n-1)n}{2}+2}^{\frac{n(n+1)}{2}+1}i$
(ya que $2^{2n+1}=8\prod_{i=1}^{n-1}4$ es el producto de $n$ números naturales menores o iguales a $8$, mientras que $\prod_{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^{(n^2)}2^{2n+1}<(\frac{(n-1)n}{2}+1)!\prod_{i=\frac{(n-1)n}{2}+2}^{\frac{n(n+1)}{2}+1}i=(\frac{n(n+1)}{2}+1)!$
Supongamos que para cierto $n\in N$, $n\geq 5$ existe $k\in N/k!=\prod_{i=0}^{n-1}(2^n-2^i)$.
Como $\prod_{i=0}^{n-1}(2^n-2^i)=2^{\frac{(n-1)n}{2}}\prod_{i=1}^{n}(2^i-1)$ tenemos que $v_2(k!)=\frac{(n-1)n}{2}$.
Además, $v_2(k!)=\sum_{r=1}^{\infty}\lfloor\frac{k}{2^r}\rfloor<\sum_{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
$(\frac{(n-1)n}{2}+1)!\leq k!=\prod_{i=0}^{n-1}(2^n-2^i)<\prod_{i=0}^{n-1}2^n=2^{(n^2)}$ (absurdo).
Así que $n<5$.

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

Responder