APMO 2020 Problema 4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 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 COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

APMO 2020 Problema 4

Mensaje sin leer por Turko Arias »

Sea $\mathbb{Z}$ el conjunto de todos los enteros. Hallar todos los polinomios $P(x)$ con coeficientes enteros que satisfacen la siguiente propiedad:
Para cada sucesión infinita $a_1, a_2,...$ de enteros en la que cada entero de $\mathbb{Z}$ aparece exáctamente una vez, existen subíndices $i<j$ y un entero $k$ tal que $a_i+a_{i+1}+...+a_j=P(k)$.
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
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 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: APMO 2020 Problema 4

Mensaje sin leer por Joacoini »

Spoiler: mostrar
Voy a llamar suma de la sucesión a las sumas de la forma $a_i+a_{i+1}+...+a_j$ con $i<j$.
Separo el problema en 3 casos.

Si el grado de $P(x)$ es $1$.
Spoiler: mostrar
$P(x)=nx+r$ recorre todos los enteros con resto $r$ modulo $n$.

Sea $S_i$ la suma de los primeros $i$ elementos si $S_j-S_i\equiv r$ mod $n$ con $j>i+1$ entonces hay una suma de la sucesión con resto $r$ modulo $n$.

$S_i$ puede tomar $n$ valores modulo $n$, algunos de estos valores van aparecer finitamente en la sucesión de sumas parciales y otros infinitamente así que existe un $m$ tal que para todo $M\geq m$ el resto de $S_M$ modulo $n$ se repite infinitamente en la sucesión de sumas parciales.

Como cada entero tiene que aparecer en la sucesión entonces hay infinitos números con resto $r$ modulo $n$ en la sucesión así que existe $k\geq m$ tal que $a_k\equiv r$ mod $n$ por lo tanto $S_{k}-S_{k-1}\equiv r$ mod $n$ y como $k\geq m$ existe $k'>k=(k-1)+1$ tal que $S_{k'}\equiv S_k$ mod $n$.
Así que obtenemos una suma de la sucesión, $S_{k'}-S_{k-1}$, la cual tiene resto $r$ modulo $n$ por lo que es uno de los valores que toma el polinomio.

Concluimos que todos los polinomios de grado $1$ cumplen la propiedad.
Si el grado de $P(x)$ es par.
Spoiler: mostrar
Si el polinomio tiene grado par entonces existe un entero $k$ tal que $P(x)$ es menor o mayor (dependiendo del signo del coeficiente principal) a $k$ para todo $x$.

La sucesión $|k|, |k|+1,|k|+2, |k|-1, |k|+3, |k|+4, |k|-2, |k|+5, |k|+6, |k|-3, ... $ cumple que todas las sumas de la sucesión son estrictamente mayor a $|k|$
La sucesión $-|k|, -|k|-1, -|k|-2, -|k|+1, -|k|-3, -|k|-4, -|k|+2, -|k|-5, -|k|-6, -|k|+3, ... $ cumple que todas las sumas de la sucesión son estrictamente menor a $-|k|$

Dependiendo del signo de la constante que sea $P(x)$ elegimos la primera o la segunda. Por lo tanto los polinomios de grado par no cumplen la propiedad.
Si el grado de $P(x)$ es impar y mayor a $1$.
Spoiler: mostrar
Voy a trabajar con los polinomios cuyo coeficiente principal es positivo, en el caso de que sea negativo agarras la sucesión que le voy a asignar a $-P(x)$ y cambias el signo de todos los elementos, de esta forma la nueva sucesión no tiene ninguna suma que coincida con uno de los puntos del polinomio.

Los polinomios de grado impar mayor a $1$ tienen la propiedad de que existe un valor $m$ lo suficientemente grande para el cual se cumple que para $M\geq m$ $P(M)<P(M+1)$, que $P(x)<P(m)$ para todo $x<m$ y que $P(M+1)-P(M)$ crece tanto como uno quiera.

Voy a construir la sucesión con lo que seria una especie de inducción.

Supongamos que tenemos una sucesión de finitos términos todos distintos donde toda suma de la sucesión no toma valores del polinomio, en un inicio esta sucesión podría ser simplemente $0$.

Ahora queremos agregar a nuestra sucesión el número $k$, lo que vamos a hacer es agarrar un entero $n$ que no este en la sucesión tal que $n>P(m)$ y que este entre dos valores del polinomio $P(M)<n<P(M+1)$.

Si $S$ es el mayor valor absoluto de una suma de la sucesión (acá aceptamos $i=j$) entonces le vamos a pedir a $n$ que cumpla que $P(M)<n-S-|k|\leq n\leq n+S+|k|<P(M+1)$ lo cual es posible ya que $P(M+1)-P(M)$ crece tanto como uno quiera, además hay infinitas opciones de $n$ por lo que se puede elegir uno que no pertenezca a la sucesión.

Si agregamos a $n$ al final de la sucesión se cumple que si $s$ es una suma de la sucesión que contiene a $n$ entonces $P(M)< n-S-|k|\leq n-S\leq s\leq n+S\leq n+S+|k|<P(M+1)$
como ente $P(M)$ y $P(M+1)$ no hay valores del polinomio tenemos que $s$ no es un valor del polinomio.

Si agregamos a $k$ al final de la sucesión se cumple que si $s$ es una suma de la sucesión que contiene a $k$ entonces $P(M)< n-S-|k|\leq s\leq n+S+|k|<P(M+1)$
como ente $P(M)$ y $P(M+1)$ no hay valores del polinomio tenemos que $s$ no es un valor del polinomio.

Siguiendo con este procedimiento podemos agregar cualquier número que queramos a la sucesión por lo que eventualmente vamos a cubrir todos los enteros exactamente una vez.

Concluimos que todos los polinomios de grado impar mayor a $1$ no cumplen la propiedad.
NO HAY ANÁLISIS.
Responder