Cono Sur 2019 - Problema 3

Problemas que aparecen en el Archivo de Enunciados.
Sandy

OFO - Medalla de Bronce
Mensajes: 71
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 2

Cono Sur 2019 - Problema 3

Mensaje sin leer por Sandy » Mar 27 Ago, 2019 4:54 pm

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.

Peznerd
Mensajes: 108
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por Peznerd » Mar 27 Ago, 2019 6:33 pm

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 - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 893
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por Fran5 » Mié 28 Ago, 2019 2:33 pm

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 // Costa Rica te entro"

usuario250

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

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por usuario250 » Mié 28 Ago, 2019 3:37 pm

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.

Sandy

OFO - Medalla de Bronce
Mensajes: 71
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 2

Re: Cono Sur 2019 - Problema 3

Mensaje sin leer por Sandy » Dom 01 Sep, 2019 12:06 pm

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

Responder