FOFO 12 Años - Problema 6

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
Mensajes: 1076
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 19
Nivel: Exolímpico
Ubicación: Santa Fe

FOFO 12 Años - Problema 6

Mensaje sin leer por Fran5 »

Sea $n$ un número natural. Decimos que una permutación $a_1,a_2,\ldots ,a_n$ de $1,2,\ldots ,n$ es súper divisible si para todo entero $m$ tal que $1\leq m\leq n$ se cumple que $m$ divide a $2(a_1+a_2+\cdots +a_m)$. Determinar, para cada $n$, la cantidad de permutaciones súper divisibles.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
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
Mensajes: 1076
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 19
Nivel: Exolímpico
Ubicación: Santa Fe

Re: FOFO 12 Años - Problema 6

Mensaje sin leer por Fran5 »

Aquí publicaremos la solución oficial.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
El gran Filipikachu;

OFO - Medalla de Bronce-OFO 2021 FOFO 11 años - Mención-FOFO 11 años OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022
Mensajes: 23
Registrado: Dom 13 Dic, 2020 12:33 pm
Medallas: 4
Nivel: 2

Re: FOFO 12 Años - Problema 6

Mensaje sin leer por El gran Filipikachu; »

Spoiler: mostrar
Llamemos $P(n)$ a la cantidad de permutaciones súper divisibles de $n$ elementos.

Veamos que $P(1)=1$ ya que solo hay una permutación posible. $P(2)=2$ ya que las dos permutaciones cumplen. Y $P(3)=6$ ya que $1|2a_1$, $2|2(a_1+a_2)$ y $3|2(a_1+a_2+a_3)=12$.

A partir de ahora $n \geq 4$.
Tomemos $m=n-1$
$n-1|2(a_1+...+a_{n-1}) \Rightarrow n-1|2(a_1+...+a_{n-1}+a_n-a_n) \Rightarrow n-1|2(\frac{n\cdot(n+1)}{2}-a_n)$
$\Rightarrow n-1| n \cdot (n+1) - 2a_n \Rightarrow n-1|1\cdot 2 -2a_n \Rightarrow n-1|2a_n-2$

Como $1 \leq a_n \leq n \Rightarrow 0 \leq 2a_n-2 \leq 2n-2 \Rightarrow 0 \leq \frac{2a_n-2}{n-1} \leq 2$
Entonces como $\frac{2a_n-2}{n-1}$ es entero, puede ser $0$, $1$ o $2$. Resolviendo cada caso obtenemos que $a_n$ es $1$, $\frac{n+1}{2}$ o $n$ respectivamente.

Separemos en estos 3 casos.

Caso 1: $a_n=n$
Ahora nos quedan $n-1$ números que son una permutación de los primeros $n-1$ naturales y cumplen que son súper divisibles. Por lo tanto la cantidad de permutaciones súper divisibles en este caso es $P(n-1)$.

Caso 2: $a_n=1$
Ahora nos quedan $n-1$ números que son una permutación de los números entre $2$ y $n$.
Definamos una nueva sucesión de forma que $b_i=a_i-1$ $\forall 1\leq i \leq n-1$.
Entonces la condición es equivalente a:
$m|2(a_1+...+a_m) \Rightarrow m|2[(a_1-1)+...+(a_m-1)+m] \Rightarrow m|2(b_1+...+b_m)+2m \Rightarrow m|2(b_1+...+b_m)$
Notemos que esta condición es la misma que antes pero para nuestra nueva sucesión y que además esta sucesión es una permutación de los números entre $1$ y $n-1$. Por lo tanto la cantidad de permutaciones súper divisibles en este caso también es $P(n-1)$.

Caso 3: $a_n=\frac{n+1}{2}$
Como $a_n$ es entero, $n$ debe ser impar.
Tomemos $m=n-2$ y hagamos lo mismo que antes.
$n-2|2(a_1+...+a_{n-2}) \Rightarrow n-2|2(a_1+...+a_{n-2}+a_{n-1}+a_n-a_{n-1}-a_n) \Rightarrow n-2|2(\frac{n\cdot(n+1)}{2}-a_{n-1}-a_n)$
$\Rightarrow n-2| n \cdot (n+1) - 2a_{n-1}-2a_n \Rightarrow n-2| n \cdot (n+1) - 2a_{n-1}-(n+1) \Rightarrow n-2|2\cdot 3 -2a_{n-1}-3 \Rightarrow n-2| 3-2a_{n-1} \Rightarrow n-2|2a_{n-1}-3$
Como $1 \leq a_{n-1} \leq n \Rightarrow -1 \leq 2a_{n-1}-3 \leq 2n-3 \Rightarrow \frac{-1}{n-2} \leq \frac{2a_{n-1}-3}{n-2} \leq \frac{2n-3}{n-2}=2+\frac{1}{n-2}$
Al tener $n \geq 4$, el lado izquierdo es mayor a $-1$ y el lado derecho es menor a $3$. También como $\frac{2a_{n-1}-3}{n-2}$ es entero, tenemos que puede ser $0$, $1$ o $2$.
Resolviendo cada caso obtenemos que $a_{n-1}$ es $\frac{3}{2}$, $\frac{n+1}{2}$ o $n-\frac{1}{2}$ respectivamente. Veamos que $a_{n-1}$ no puede tomar el primer o último valor porque no son enteros y tampoco puede pasar que sea $\frac{n+1}{2}$ ya que este número es $a_n$ y no se pueden repetir.
Por lo tanto no hay permutaciones súper divisibles en este caso.

Sumando los 3 casos obtenemos que $P(n)=2P(n-1)$ para todo $n \geq 4$. Como $P(3)=6$ podemos ver que $P(n)=2^{n-2}\cdot3$.
Podemos probar esto por inducción. Para $3$ se cumple. Digamos que para $n-1$ se cumple, vamos a demostrarlo para $n$.
$P(n)=2P(n-1)=2\cdot2^{n-3}\cdot3=2^{n-2}\cdot3$
Queda terminada la inducción.

Entonces $P(1)=1$, $P(2)=2$ y $P(n)=2^{n-2}\cdot3$ para todo $n \geq 3$.
Spoiler: mostrar
Para agregar, si queremos poner los casos $1$ y $2$ en la fórmula podemos hacer la siguiente extensión:
$P(n)= \lceil | 2^{n-2}\cdot3 - \lfloor \frac{2}{n} \rfloor | \rceil$
usuario250

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

Re: FOFO 12 Años - Problema 6

Mensaje sin leer por usuario250 »

Un hiper-mega-pequeño comentario.
Spoiler: mostrar
Para el caso 2, en vez de usar $\Rightarrow$ en cada uno de los pasos, usar $\Leftrightarrow$.
El gran Filipikachu; escribió: Mar 18 Oct, 2022 6:02 pm
Spoiler: mostrar
Llamemos $P(n)$ a la cantidad de permutaciones súper divisibles de $n$ elementos.

Veamos que $P(1)=1$ ya que solo hay una permutación posible. $P(2)=2$ ya que las dos permutaciones cumplen. Y $P(3)=6$ ya que $1|2a_1$, $2|2(a_1+a_2)$ y $3|2(a_1+a_2+a_3)=12$.

A partir de ahora $n \geq 4$.
Tomemos $m=n-1$
$n-1|2(a_1+...+a_{n-1}) \Rightarrow n-1|2(a_1+...+a_{n-1}+a_n-a_n) \Rightarrow n-1|2(\frac{n\cdot(n+1)}{2}-a_n)$
$\Rightarrow n-1| n \cdot (n+1) - 2a_n \Rightarrow n-1|1\cdot 2 -2a_n \Rightarrow n-1|2a_n-2$

Como $1 \leq a_n \leq n \Rightarrow 0 \leq 2a_n-2 \leq 2n-2 \Rightarrow 0 \leq \frac{2a_n-2}{n-1} \leq 2$
Entonces como $\frac{2a_n-2}{n-1}$ es entero, puede ser $0$, $1$ o $2$. Resolviendo cada caso obtenemos que $a_n$ es $1$, $\frac{n+1}{2}$ o $n$ respectivamente.

Separemos en estos 3 casos.

Caso 1: $a_n=n$
Ahora nos quedan $n-1$ números que son una permutación de los primeros $n-1$ naturales y cumplen que son súper divisibles. Por lo tanto la cantidad de permutaciones súper divisibles en este caso es $P(n-1)$.

Caso 2: $a_n=1$
Ahora nos quedan $n-1$ números que son una permutación de los números entre $2$ y $n$.
Definamos una nueva sucesión de forma que $b_i=a_i-1$ $\forall 1\leq i \leq n-1$.
Entonces la condición es equivalente a:
$m|2(a_1+...+a_m) \Rightarrow m|2[(a_1-1)+...+(a_m-1)+m] \Rightarrow m|2(b_1+...+b_m)+2m \Rightarrow m|2(b_1+...+b_m)$
Notemos que esta condición es la misma que antes pero para nuestra nueva sucesión y que además esta sucesión es una permutación de los números entre $1$ y $n-1$. Por lo tanto la cantidad de permutaciones súper divisibles en este caso también es $P(n-1)$.

Caso 3: $a_n=\frac{n+1}{2}$
Como $a_n$ es entero, $n$ debe ser impar.
Tomemos $m=n-2$ y hagamos lo mismo que antes.
$n-2|2(a_1+...+a_{n-2}) \Rightarrow n-2|2(a_1+...+a_{n-2}+a_{n-1}+a_n-a_{n-1}-a_n) \Rightarrow n-2|2(\frac{n\cdot(n+1)}{2}-a_{n-1}-a_n)$
$\Rightarrow n-2| n \cdot (n+1) - 2a_{n-1}-2a_n \Rightarrow n-2| n \cdot (n+1) - 2a_{n-1}-(n+1) \Rightarrow n-2|2\cdot 3 -2a_{n-1}-3 \Rightarrow n-2| 3-2a_{n-1} \Rightarrow n-2|2a_{n-1}-3$
Como $1 \leq a_{n-1} \leq n \Rightarrow -1 \leq 2a_{n-1}-3 \leq 2n-3 \Rightarrow \frac{-1}{n-2} \leq \frac{2a_{n-1}-3}{n-2} \leq \frac{2n-3}{n-2}=2+\frac{1}{n-2}$
Al tener $n \geq 4$, el lado izquierdo es mayor a $-1$ y el lado derecho es menor a $3$. También como $\frac{2a_{n-1}-3}{n-2}$ es entero, tenemos que puede ser $0$, $1$ o $2$.
Resolviendo cada caso obtenemos que $a_{n-1}$ es $\frac{3}{2}$, $\frac{n+1}{2}$ o $n-\frac{1}{2}$ respectivamente. Veamos que $a_{n-1}$ no puede tomar el primer o último valor porque no son enteros y tampoco puede pasar que sea $\frac{n+1}{2}$ ya que este número es $a_n$ y no se pueden repetir.
Por lo tanto no hay permutaciones súper divisibles en este caso.

Sumando los 3 casos obtenemos que $P(n)=2P(n-1)$ para todo $n \geq 4$. Como $P(3)=6$ podemos ver que $P(n)=2^{n-2}\cdot3$.
Podemos probar esto por inducción. Para $3$ se cumple. Digamos que para $n-1$ se cumple, vamos a demostrarlo para $n$.
$P(n)=2P(n-1)=2\cdot2^{n-3}\cdot3=2^{n-2}\cdot3$
Queda terminada la inducción.

Entonces $P(1)=1$, $P(2)=2$ y $P(n)=2^{n-2}\cdot3$ para todo $n \geq 3$.
Spoiler: mostrar
Para agregar, si queremos poner los casos $1$ y $2$ en la fórmula podemos hacer la siguiente extensión:
$P(n)= \lceil | 2^{n-2}\cdot3 - \lfloor \frac{2}{n} \rfloor | \rceil$
1  
Responder