Entrenamiento Cono 2018 P15

[Matías]

Sea $A$ una colección finita de enteros positivos (puede haber números repetidos). Dado un entero positivo $k$ decimos que $A$ es divisible por $k$ si es posible dividir a todos los elementos de $A$ en dos grupos $B$ y $C$ tales que $\frac{S(B)}{S(C)}=k$ donde $S(X)$ es la suma de todos los elementos del grupo $X$.
Para cada entero positivo $n$, demostrar que existe una colección $A$ de $n+1$ enteros positivos que es divisible por cada uno de los números $1$, $2$, ..., $n$. Más aún, entre todas estas colecciones $A$ de $n+1$ enteros positivos, hallar una colección para la cual $S(A)$ sea mínima.

[Joacoini]

Spoiler: mostrar

$S(A)=S(B)+S(C)\Rightarrow S(B)=S(A)-S(C)$
$\frac{S(B)}{S(C)}=\frac{S(A)-S(C)}{S(C)}=k\Rightarrow S(A)-S(C)=kS(C)\Rightarrow S(A)=(k+1)S(C)$

Luego $k+1|S(A), \forall k/ 1\leq k\leq n\Rightarrow mcm(2;...;n+1)\leq S(A)$

Si $a_1, a_2, ..., a_{n+1}$ son los elementos de $A$, un ejemplo con $S(A)=mcm(2;...;n+1)=m$ es el siguiente.

$\forall i/ 1\leq i \leq n, a_i=\frac{m}{i}-\frac{m}{i+1}$
$a_{n+1}=\frac{m}{n+1}$

Para ver que $k$ divide $A$, basta que $B$ contenga a los elementos $a_1,..., a_k$.