FOFO 12 Años - Problema 6

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

[Fran5]

Aquí publicaremos la solución oficial.

[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]

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

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$