Cono Sur 2019 - Problema 3

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

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Cono Sur 2019 - Problema 3

Mensaje sin leer por Sandy »

Sea $n \geq 3$ un entero. Determinar si existen permutaciones $(a_1, a_2, ... , a_n)$ de los números $(1, 2, ... , n)$ y $(b_1, b_2, ... , b_n)$ de los números $(n+1, n+2, ... , 2n)$ tales que $(a_1b_1, a_2b_2, ... , a_nb_n)$ sea una progresión aritmética estrictamente creciente.
Fallo inapelable.
Peznerd
Mensajes: 113
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por Peznerd »

No entiendo jajaja, ¿qué son las permutaciones? ¿De dónde sacamos los números $b_n$? ¿Qué tienen que ver los números $n+1,n+2,...,2n$?
Un día vi una vaca sin cola vestida de uniforme

$$\int u \, dv=uv-\int v \, du\!$$
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 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
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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por Fran5 »

Una permutación es un reordenamiento de los números.

Por ejemplo, si $n = 5$, entonces una permutación de $(1,2,3,4,5)$ podría ser $(5,1,3,4,2)$ y una permutación de $(6,7,8,9,10)$ podría ser $(6,8,7,10,9)$.

En este caso, te queda que $(a_1b_1, a_2b_2, \ldots, a_5b_5) = (36, 56, 56, 90, 90)$ que no es una progresión aritmética
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por usuario250 »

Para n primo mirar los siguientes casos:
Spoiler: mostrar
1) Para n=3 se puede ver a mano que no se puede (son 6 casos)
2) Para n primo mayor a 3:
a) Fijarse qué pasa cuando n y 2n están juntos (n*2n es el mayor de la progresión aritmética, fijarse el máximo del número anterior en la progresión y ver qué pasa con la razón aritmética)
b) Sin n y 2n no están juntos, hay dos números de la progresión que son múltiplos de n con una diferencia múltiplo de n. ver qué pasa al ser n primo.
Para n no primo:
Spoiler: mostrar
2) a) Creo que se puede generalizar fácil
b) Habría que ver cómo generalizarlo.
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por Sandy »

Spoiler: mostrar
Supondremos que en efecto forman una progresión aritmética y procederemos por el absurdo.

Digamos que $r$ es la ratio de la progresión.

Si $d|r$, sabemos que todos los términos de la progresión son congruentes en módulo $d$. Luego, tomemos $2<p<2n$ primo.

Es claro que en el intervalo $[1, 2n]$ hay a lo sumo $\frac{2n}{p}<\frac{2n}{2}=n$ múltiplos de $p$. Esto implica que, para todo primo distinto de $2$ y menor que $2n$, no alcanzan sus múltiplos para hacer que los $n$ términos de la progresión sean divisibles por $p$. Pero como $p<2n$, hay al menos un término que sí es divisible por $p$. Por lo tanto, si $p$ dividiera $r$, todos los términos serían congruentes en módulo $p$, y como sabemos con certeza que hay uno al menos que es congruente a $0$, todos deberían serlo, pero vimos que eso no puede pasar.
Luego $r$ es de la forma $2^m\cdot Y$, con $Y$ sólo divisible por primos mayores a $2n$. (1)

Además, veamos que el término que tiene al $1$ puede ser como mucho $2n$, mientras que los demás son al menos $2\cdot (n+1)>2n$, luego $a_1=1$. (2)

Supongamos la existencia de $Y$ (es decir, que a $r$ lo divide algún primo mayor a $2n$)

Por lo tanto nos queda que $a_nb_n=a_1b_1+(n-1)(2^m\cdot Y)$

$2n\cdot n > (n+1)+(n-1)(2^m\cdot Y) \Rightarrow 2n\cdot n > (n-1)+(n-1)(2^m\cdot Y)$.

$2n\cdot \frac{n}{n-1} > 1+(2^m\cdot Y) \Rightarrow \frac{2n^2}{n-1} > (2^m\cdot Y)$

Pero $Y\geq 2n$, luego $Y\cdot \frac{n}{n-1} > (2^m\cdot Y)$, es decir, $\frac{n}{n-1} > 2^m$, luego $m=0$

Entonces $r\equiv 1(mod2)$, es decir que al menos $\left\lfloor\frac{n}{2}\right\rfloor$ de los términos son impares. Luego como mucho hay $\left\lceil\frac{n}{2}\right\rceil$ términos pares (y viceversa). Es decir, hay un término que tiene un par y un impar, y el resto de los $k$ cumplen que $a_k\equiv b_k (mod2)$. Pero como $r$ es coprimo con $4$, debería recorrer todos los restos módulo $4$ cada $4$ términos. Pero entonces tendría que haber como mucho $\left\lceil\frac{n}{4}\right\rceil$ múltiplos de $4$, pero vimos que hay al menos $\left\lfloor\frac{n}{2}\right\rfloor-1$ términos en los que hay dos términos pares de las permutaciones multiplicándose, es decir, en la progresión hay al menos $\left\lfloor\frac{n}{2}\right\rfloor-1$ términos múltiplos de 4, absurdo.

Luego no existe $Y$, por lo tanto $r=2^m$.
Podemos descartar el caso $m=0$ por el mismo argumento que antes.

Luego, si $m\geq 1$, $r\equiv 0(mod2)$, es decir que todos los términos son pares (ya que son todos congruentes en módulo $r$ y hay al menos un término par). Esto sólo es obtenible si los pares están absolutamente distribuidos (es decir, $a_k$ y $b_k$ tienen distinta paridad siempre). Pero eso implica que, por ejemplo, el término en el que $a_k=2$ es congruente a $2$ en módulo 4, por lo tanto, si $4|r$, todos los términos son congruentes a $2(mod4)$, lo cual es absurdo ya que existe un término en el que $a_k=4$ (o en el caso de $n=3$, $b_k=4$).

Recapitulando: tenemos que $r=2^m$, $r\geq 1$ y $4$ no divide a $r$. Luego $r=2$.

Ahora, por Rearrangement, tenemos que $\sum_{k=1}^{n}a_kb_k \geq \sum_{k=1}^{n} k\cdot (2n+1-k)$.

Además, como sabemos que es una progresión aritmética con diferencia 2, $\sum_{k=1}^{n}a_kb_k=a_1b_1\cdot n+\sum_{k=1}^{n-1}2k=b_1\cdot n+n\cdot (n-1)$

Luego:

$\sum_{k=1}^{n}k\left(2n+1-k\right)=\left(2n+1\right)\sum_{k=1}^{n}k-\sum_{k=1}^{n}k^2=\left(2n+1\right)\frac{n\left(n+1\right)}{2}-\frac{n\left(n+1\right)\left(2n+1\right)}{6}=\frac{\left(2n+1\right)\left(n+1\right)n}{3}$

Entonces tenemos que:

$b_1\cdot n+n\cdot (n-1) \geq \frac{\left(2n+1\right)\left(n+1\right)n}{3}$

$b_1+n-1 \geq \frac{(2n+1)(n+1)}{3}$

$b_1 \geq \frac{(2n+1)(n+1)}{3}-(n-1)$

$b_1 \geq \frac{2n^2+4}{3}$

Pero para todo $n\geq 3$ es claro que $\frac{2}{3}n^2 \geq 2n$, pero eso implicaría que $b_1>2n$, absurdo.

Luego no existen dichas permutaciones para ningún $n\geq 3$.
Fallo inapelable.
Mijail
Mensajes: 21
Registrado: Mié 11 Oct, 2017 9:56 pm
Nivel: 3
Ubicación: Peru, Lima

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por Mijail »

Un buen problema :mrgreen:
Spoiler: mostrar
Llamemos a $r$ como la razon de la progresion aritmetica entonces es claro que $a_1.b_1$ es al menos $n+1$ y que $a_n.b_n$ es a lo mas $2n^2$ de esto podemos obtener que la razon es a lo mas $2n+1$. Ahora si la razon es a lo mas $2n$ hay un numero de la secuencia que es multiplo de $r$ ya que esta contenida en el conjunto de $a_{i}'s$ o en el conjunto de los $b_{i}'s$ luego como uno de los terminos de la progresion es multiplo de $r$ entonces todos los terminos lo son, entonces en particular se cumple que el producto de todos los terminos de la secuencia es divisible por $r^ n$ entonces concluimos que: $r^ {n} \mid (2n)!$ y luego de esto solo viendo la maxima potencia en un primo de $r$ obtenemos que $r= 1$ o $r=2$ (Usarse la formula de Legendre o la igual de Kronecker) ahora no es posible que la razon sea $1$ o $2$ ya que como el $a_1.b_1$ es a lo mucho $2n$ ya que aparece el $1$ en la secuencia de los $a_{i}'s$ y de forma analoga tenemos que $a_n.b_n$ es al menos $n(n+1)$ de esto obtenemos que $r\geq n\geq 3$ lo cual implica que el caso en que $r \leq 2n$ sea imposible. Ahora si $r=2n+1$ tenemos que la igualdad se debe dar en lo primero que dijimos entonces $a_1.b_1= n+1$ y $a_n.b_n=2n^{2}$; ahora con esto es claro que $$a_k.b_k=n+1 + (2n+1).(k-1) \geq k(n+k) $$ ahora al realizar el producto de todos usando la desigualdad vemos que el producto de los terminos de la secuencia es al menos $(2n)!$ entonces se debe dar la igualdad para todo $k$ en la ultima desigualdad lo cual no es posible para $k=2$. Entonces no es posible que $r=2n+1$, luego con lo que dijimos al inicio hemos terminado :mrgreen:
Responder