OFO 2022 Problema 12

Problemas que aparecen en el Archivo de Enunciados.
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

OFO 2022 Problema 12

Mensaje sin leer por Fedex »

Hallar todos los polinomios $P(x)$ con coeficientes enteros tales que$$P(n!)=|P(n)|!$$para todo entero positivo $n$.
This homie really did 1 at P6 and dipped.
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: OFO 2022 Problema 12

Mensaje sin leer por Fedex »

Solución oficial:
Spoiler: mostrar
Durante la solución vamos a usar valuación $p$-ádica y suma de Legendre, pueden leer sobre estos temas en este apunte.

Notemos que en el lado izquierdo el polinomio toma valores positivos para $n!$ arbitrariamente grande. Lo que nos dice que el coeficiente principal de $P(n)$ es positivo.

Supongamos que $\deg P\geq 2$. Por lo dicho, para $n$ lo suficientemente grande se verifica que $P(n)\geq n$.
Sea $p$ un primo que satisface eso. Mirando la ecuación módulo $p$:$$P(p!)=|P(p)|!\to P(0)\equiv 0\;(p)$$Pero esto ocurre para infinitos primos, por lo que $P(0)=0$.
Sea $P(n)=n^kQ(n)$ para $k\geq 1$ y $Q(0)\neq 0$. Si ahora tomamos $n=p$ tal que $p\nmid Q(0)$. Notemos que por suma de Legendre:$$k=\nu _p(LHS)=\nu _p(RHS)=\sum \limits _{i=1}^{\infty }\left \lfloor \frac{|P(p)|}{p^i}\right \rfloor \geq \left \lfloor \frac{|P(p)|}{p}\right \rfloor =\frac{|P(p)|}{p}$$Donde LHS es lo que está del lado izquierdo de la igualdad, y RHS lo que está del lado derecho. Entonces$$kp\geq |P(p)|$$Lo cual es absurdo ya que un polinomio con coeficiente principal positivo y $\deg P\geq 2$ está acotado por arriba por uno de $\deg (kp)=1$ para infinitos valores de $p$.

Luego $\deg P\leq 1$:

Si $\deg P=0$. Entonces $c=|c|!$ lo cual solo se satisface para $c=1,2$.

Si $\deg P=1$. Entonces $P(n)=an+b$. Como dijimos $a\geq 1$. Si ocurre que $a\geq 2$ entonces para $n$ lo suficientemente grande $|P(n)|\geq n$ y de la misma forma que antes $b=0$. Luego:$$a(n!)=(an)!\to a=(n+1)(n+2)\dots (an)$$Lo cual es absurdo. Por lo que $a=1$. Si $n=1$ tenemos que $1+b=|1+b|!$ con lo cual $b=0,1$. Que nos arroja $P(n)=n$, $P(n)=n+1$.
Si $P(n)=n+1\to n!+1=(n+1)!$ que no verifica.
Si $P(n)=n\to n!=n!$ que sí verifica.

Luego las soluciones son:
$P(n)=1$
$P(n)=2$
$P(n)=n$
Última edición por Fedex el Mié 02 Feb, 2022 8:55 am, editado 2 veces en total.
This homie really did 1 at P6 and dipped.
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: OFO 2022 Problema 12

Mensaje sin leer por sebach »

Voy con una solución que no sé si está del todo bien pero no puedo esperar a la corrección de la OFO, si alguien encuentra errores y tiene ganas comenta!
Spoiler: mostrar
Del enunciado se ve que $P(n!)$ debe ser positivo para todo $n$ entero.

Primero, veamos qué pasa si $P$ es constante, es decir $P(x) \equiv a_0$.
En ese caso la igualdad del enunciado se transformar en $a_0 = |a_0|!$, por lo que $a_0$ deberá ser positivo dado que la función factorial de enteros siempre da un valor positivo, y de hecho $a_0 = 1 ó a_0 = 2$. Se puede ver que si $a_0 > 2$, luego $a_0! \geq a_0*2*1 > a_0$.
Luego encontramos dos polinomios que cumplen el enunciado, $P(x) \equiv 1$ y $P(x) \equiv 2$.

A partir de ahora, $P$ no será constante.

Como $P$ es un polinomio o bien $P(n)$ tiende a $\infty$ o bien $P(n)$ tiende a $- \infty$ cuando $n$ tiende a $\infty$. Por lo que dijimos antes, $P(n)$ debe tender a $\infty$ cuando $n$ tiende a $\infty$.

Esto significa que a partir de un cierto valor $n_0$, $P(n) > 0$ para todo $n > n_0$.

Tomemos un valor $q > n_0$. Esto significa que $P(q!) = P(q)!, P((q+1)!) = P(q+1)!$.

Ahora, sea $P(x) = a_m*x^m + a_{m-1}x^{m-1} … + a_1x + a_0$ el polinomio en cuestión.

Luego:

$P(q!) = a_m*(q!)^m + a_{m-1}(q!)^{m-1} … + a_1(q!) + a_0$

$P(q+1)! = P((q+1)!) = P(q!*(q+1)) = $
$a_m*(q!)^m*(q+1)^m + a_{m-1}(q!)^{m-1}*(q+1)^{m-1} … + a_1(q!)*(q+1) + a_0 $
$\leq (q+1)^m * P(q!) = (q+1)^m * P(q)!$

Esto significa que $\dfrac{P(q+1)!}{P(q)!} \leq (q+1)^m$.

Si ocurre que $(P(q+1) - P(q)) \geq m $ y $P(q) \geq q+2$, entonces la desigualdad de arriba no puede cumplirse (dado que si “cancelamos” los números desde $1$ hasta $P(q)$, arriba quedarían al menos $m$ términos de valor al menos $q+2$ que es mayor a $(q+1)^m$.

Notemos que el valor de $q$ elegido era cualquiera mayor a $n_0$.

El hecho de que $P(x)$ tiende a infinito cuando $x$ tiende a infinito nos dice que el coeficiente principal de $P$ debe ser positivo. Esto es porque si $x$ es un entero positivo, $|a_{m-1}x^{m-1} + … + a_1x + a_0| \leq x^{m-1} * max(|a_{m-1}|, …, |a_1|, |a_0|)$ y si tomo un $x_0$ más grande que el máximo de esos coeficientes, tendré que $x^m$ es mayor que todo eso para todo valor a partir de $x_0$, por lo que el coeficiente principal que multiplica a $x^m$ no puede ser negativo pues haría que la evaluación del polinomio sea negativa para todo $x > x_0$.

Esto nos dice que $P’$, el polinomio que surge de derivar $P$, tiene coeficiente principal igual a $m*a_m$ que es positivo, que indica que a partir de cierto momento $P’$ es positivo, por lo que a partir de ese momento el polinomio original $P$ aumenta (ya sabíamos esto). Esto se ve de que el coeficiente principal es positivo con un razonamiento similar al del párrafo anterior.

No solo eso, sino que $P’’$ es o bien $0$ o bien un polinomio de coeficiente principal positivo.

Veamos el caso primero de que $P’’$ no es $0$, es decir, el polinomio original es al menos de grado $2$.

En ese caso, lo que nos dice el hecho de que el coef. principal de $P’’$ sea positivo, es que a partir de un cierto valor $P’’$ es siempre positivo, y va creciendo. O sea que el polinomio original será convexo.

Esto significa que la diferencia entre $P(n)$ y $P(n+1)$ se hace cada vez más grande.

Por lo tanto, a partir de cierto momento, siempre ocurrirá que $(P(q+1) - P(q)) \geq m$, dado que $m$ es un valor fijo que indica el grado del polinomio.
Lo que significa, por lo que vimos antes, que al menos a partir de ahí nunca deberá ocurrir que $P(q) \geq q+2$, por lo que $P(q) \leq q+1$ para todo valor $q$ a partir de un cierto momento.
Ahora, como la función es convexa y tiende a $\infty$, no puede ocurrir que a partir de un valor el polinomio se queda siempre por debajo de la función $f(x) = x+1$.

Esto se puede pensar como que si a partir del momento digamos $s$ en el que $P’’$ es siempre positivo, es decir que $P$ es convexa y aumenta cada vez más rápido, $P$ está por debajo de la función $f(x) = x+1$, y tenemos una diferencia de $f(s) - P(s)$, como la función lineal $f$ aumenta de a $1$, y $P$ tiene coeficientes enteros, al evaluar $P$ en los siguientes enteros $s+1, s+2, …$ el valor de la evaluación aumenta en al menos $1$ al cambiar de $s$ a $s+1$, y luego aumenta en al menos $2$, y así sucesivamente, por lo que la diferencia entre $f$ y $P$ desciende en el menos $1$ al movernos al siguiente entero en la coordenadas $x$, llegando a valer $0$ en algún momento y luego en el siguiente entero $P$ pasa a ser mayor a $x+1$ justificando lo que dijimos antes.

Esto demuestra que no puede haber un polinomio no lineal que resuelva el enunciado.

Busquemos ahora rectas que cumplan con lo pedido.

$P(1!) = P(1) = |P(1)|!$ nos dice que, como vimos en el caso de $P$ constante, $P(1)=1$ ó $P(1)=2$. De la misma forma ocurre con $P(2!) = P(2) = |P(2)|!$.

Por lo que $P$ será una recta que pasa por alguno de los puntos $(1,1), (1,2)$ y además pasa por alguno de los puntos $(2, 1), (2, 2)$.

Si pasa por $(1,1) y (2,1)$ será el polinomio constante $P(x) \equiv 1$ que ya vimos antes.
Si pasa por $(2,2) y (2,2)$ será el polinomio constante $P(x) \equiv 2$ que ya vimos antes.

Si pasa por $(1, 2) y (2, 1)$, será la recta $P(x) = 3 - x$ que no cumple que $P(3!) = -3 = |P(3)|!$, por lo que no cumple con el enunciado.

Y si pasa por $(1, 1), (2, 2)$, será la recta $P(x) = x$, que siempre cumple que $P(n!) = n! = |P(n)|! = n!$.

Finalmente, demostramos que los únicos polinomios posibles que cumple con el enunciado son $P(x) = 1, P(x) = 2, P(x) = x$.


1  
juandodyk

OFO - Medalla de Oro-OFO 2022 OFO - Medalla de Oro-OFO 2023 OFO - Mención-OFO 2024
Mensajes: 42
Registrado: Mar 26 Jun, 2018 1:59 am
Medallas: 3
Nivel: Exolímpico

Re: OFO 2022 Problema 12

Mensaje sin leer por juandodyk »

Spoiler: mostrar
La idea es simplemente mostrar que si $P$ tiene grado mayor a 1, $|P(n)|!$ crece mucho mas rapido que $P(n!)$, asi que no pueden ser iguales. Esto es trivial usando $(\frac ne)^n \leq n! \leq n^n$. Luego para $P$ de grado 1 o 0 se ve facil que $P(x)=x$, $P(x)=1$ o $P(x)=2$. Asi que todos los polinomios que cumplen son esos tres.

Prop 0. Para todo $n$ entero positivo, $(\frac ne)^n \leq n! \leq n^n$.

Prueba. Que $n! \leq n^n$ es trivial. Para la otra, notar que $\log(k) \geq \int_{k-1}^k \log t\, dt$, luego $\log(n!) = \sum_{k=2}^n \log(k) \geq \sum_{k=2}^n \int_{k-1}^k \log t\, dt = \int_1^n \log t\, dt = n\log n - n + 1 \geq n \log(\frac ne)$, y $n! \geq (\frac ne)^n$, como queriamos.

Prop 1. Sea $P(x) = \sum_{i=0}^k a_i x^i$ con $a_k\neq0$, $k$ el grado. Sea $\epsilon>0$. Existe $n_0\in\mathbb N$ tal que $$(1-\epsilon)|a_k|x^k < |P(x)| < (1+\epsilon)|a_k|x^k$$ si $x\geq n_0$.

Prueba. Es simplemente ver que $\lim_{x\to\infty}\limits \frac{P(x)}{a_k x^k} = 1$. Ahora $\frac{P(x)}{a_k x^k} = \sum_{i=0}^k \frac{a_i}{a_k} x^{i-k}$. Los terminos con $i<k$ tienden a $0$, y el de $i=k$ tiende a 1 cuando $x\to\infty$.

Prop. El grado de $P$ no puede ser mayor que 1.

Prueba. Sea $P(x) = \sum_{i=0}^k a_i x^i$ con $a_k\neq0$, $k$ el grado. Suponemos $k\geq2$ y queremos llegar a un absurdo. Voy a mostrar que $|P(n)|! > P(n!)$ si $n$ es grande y par. Uso las Prop anteriores (con $\epsilon=\frac12$) y obtengo $|P(n)|! > (\frac12 |a_k| n^k)! \geq (\frac1{2e} |a_k| n^k)^{\frac12 |a_k| n^k}$ y $P(n!) < \frac32 |a_k| (n!)^k \leq \frac32 |a_k| n^{nk}$ si $n\geq n_0$ par. Basta probar, tomando logaritmos, que
$$(\frac12 |a_k| n^k) \log (\frac1{2e} |a_k| n^k) > \log(\frac32 |a_k|) + nk \log n.$$
Dividimos por $n \log n$ y hay que probar
$$\frac12 |a_k| n^{k-1} \frac{\log(\frac1{2e} |a_k|) + k \log(n)}{\log(n)} > \frac{\log(\frac32 |a_k|)}{n \log n} + k.$$
El lado izquierdo es $\frac12 |a_k| n^{k-1}(k + \frac{\log(\frac1{2e} |a_k|)}{\log n})$, que tiende a infinito cuando $n\to\infty$ ya que $k\geq 2$. El lado derecho tiende a $k$. Luego la desigualdad se cumple para $n$ suficientemente grande.

Prop. Si el grado de $P$ es 0 o 1, $P(x)=x$, $P(x)=1$ o $P(x)=2$.

Prueba. $P(x)=ax+b$ con $a,b\in\mathbb Z$. Tomamos $n=1$ y $n=2$ en $P(n!) = |P(n)|!$ y tenemos $a+b=|a+b|!$, $2a+b=|2a+b|!$. Es decir, $a+b$ y $2a+b$ son positivos y cumplen $k=k!$. Las unicas soluciones de esta ecuacion son $k=1$ y $k=2$ obviamente. Entonces $a+b,2a+b\in\{1,2\}$. Si $a+b=2a+b$, $a=0$. Si ademas $a+b=1$, $b=1$, y $P(x)=1$, que cumple la condicion del enunciado. Si ademas $a+b=2$, $b=2$ y $P(x)=2$, que tambien cumple la condicion. Si $a+b=1$, $2a+b=2$, $a=1$ y $b=0$, asi que $P(x)=x$, que cumple. Si $a+b=2$, $2a+b=1$, $a=-1$ y $b=3$, asi que $P(x)=-x+3$, pero con $n=3$ se ve que no cumple la condicion. Entonces las unicas posibilidades son $P(x)=x$, $P(x)=1$ y $P(x)=2$.
1  
Responder