OFO 2023 Problema 7

[Uli Pereira]

Un entero positivo $n$ es multiversal si todo entero positivo menor o igual a $n$ puede ser escrito como la suma de divisores de $n$, distintos entre sí.
Por ejemplo, los divisores de $6$ son $1$, $2$, $3$ y $6$. Y como$$1\,=\,{\bf 1}, ~~ 2\,=\,{\bf 2}, ~~ 3\,=\,{\bf 3}, ~~ 4\,=\,{\bf 1}\,+\,{\bf 3}, ~~ 5\,=\,{\bf 2}\,+\,{\bf 3}, ~~ 6\,=\,{\bf 6},$$entonces $6$ es multiversal.
Demostrar que el producto de dos números multiversales también es multiversal.

[Uli Pereira]

Aquí publicaremos la solución oficial.

[FabriATK]

Solución:

Spoiler: mostrar

Supongamos que tenemos dos enteros positivos $a, b$ que son multiversales con $a \geq b$
Como $b$ es multiversal, podemos formar todos los enteros positivos menores o iguales a $b$ usando sólo divisores de $b$.

Es decir, para todo $1 \leq i \leq b$
$i = d_{b1} + d_{b2}+...+ d_{bm}$ siendo $d_{b1}, d_{b2},..., d_{bm}$ divisores positivos de $b$, distintos entre sí.

Está claro que, para todo $d_{bx}$ divisor de $b$, el número $a\times d_{bx}$ será un divisor de $ab$, pero no de $a$ ni de $b$ (a excepción de que $d_{bx} = 1$, y en ese caso $a\times d_{bx}$ sería $a$).

En resumen, si $i = d_{b1} + d_{b2}+...+ d_{bm} \Rightarrow a\times i = a( d_{b1} + d_{b2}+...+ d_{bm}) = ad_{b1} + ad_{b2}+...+ ad_{bm}$ siendo $ad_{b1}, ad_{b2},..., ad_{bm}$ divisores de $ab$ que no son divisores de $a$, excepto tal vez el mismo $a$.

Cuestión que entonces podemos formar todos los $ai$ con $1 \leq i \leq b$ sin usar divisores de $a$ menores que $a$.

Como $a$ es multiversal, podemos formar todos los enteros $k$ con $1 \leq k < a$ usando sólo divisores de $a$ menores a $a$.
Luego, para todo $1 \leq k < a$:
$k = d_{a1} + d_{a2}+...+ d_{al}$ siendo $d_{a1}, d_{a2},..., d_{al}$ divisores positivos de $a$, distintos entre sí.

Es decir que para todo número de la forma $ai + k$ con $1 \leq i \leq b$ y $1 \leq k <a$ se cumple que:
$ai + k = ad_{b1} + ad_{b2}+...+ ad_{bm} + d_{a1} + d_{a2}+...+ d_{al}$ siendo $ad_{b1}, ad_{b2},..., ad_{bm} y d_{a1}, d_{a2},..., d_{al}$ divisores positivos de $ab$ distintos entre sí.
y ya dijimos que todos los $ai$ también se pueden formar.
Y claramente $1, 2, ..., a$ se pueden formar usando divisores de $a$.
Así que se pueden formar todos los enteros menores o iguales a $ab$ usando sólo divisores de $ab$.
De donde $ab$ es multiversal.