Melina escribió en el pizarrón cuatro números enteros positivos distintos y, a continuación, calculó el máximo común divisor de cada pareja formada por dos es esos cuatro números. Obtuvo así seis resultados distintos: $1$, $2$, $3$, $4$, $5$ y $N$, con $N>5$. Determinar el menor valor posible de $N$.
Nota: Dado dos números enteros $a$ y $b$, el máximo común divisor de $a$ y $b$ es el mayor entero positivo $d$ tal que $d$ divide a $a$ y $d$ divide a $b$.
Lema: Si en la lista de $MCD$ aparecen al menos dos números que son divisibles por $d$ entonces hay al menos tres.
Demostración: Recordemos que $d |mcd(a,b)$ sí y solo sí $d|a$ y $d|b$. Ahora si hay al menos dos $MCD$ que son divisibles por $d$ hay al menos tres números del pizarrón que son divisibles por $d$, por lo que hay al menos $\binom{3}{2} = 3$ $MCD$ que lo son.
Vamos con el problema. Notemos que $N$ es par porque aparecen el $2$ y el $4$ y tiene que haber un tercero. Además, $N$ no es divisible por $d = 3, 4, 5$ ya que si lo fuera, aparecerían al menos dos números divisibles por $d$ pero no tres, lo que contradice el lema.
El primer $N>5$ que verifica todo esto es $N = 14$ donde un ejemplo que funciona son los números $20, 15, 28, 42$. Finalmente concluimos que el menor es $N = 14$.
Sean $A$, $B$, $C$ y $D$ los $4$ números:
Notemos que en la lista de resultados de los $mcd$ están el $4$ y el $2$. Esto significa que hay dos números en los cuales aparecen dos factores $2$ y un tercero en el cual aparece un único $2$:
$A = 2 * 2$
$B = 2 * 2$
$C = 2$
Notar ahora que en $D$ no puede aparecer ningún factor $2$. De lo contrario, todos los resultados de los $mcd$ serían números pares.
Tenemos "ubicados" dos de los seis $mcd$: El $4$ y el $2$. Ahora nos quedaría ver donde se ubican $1$, $3$, $5$ y $N$.
Si hay un $mcd(x, y) = 3$; $3$ va a tener que estar en $D$. $mcd(A, B, C) = 2$, por lo que si agregamos factores $3$ a dos de esos números nunca obtendremos un $mcd(x, y) = 3$, que es lo que estamos buscando.
Utilizamos el mismo argumento para el $5$, nos queda:
$A = 2 * 2$
$B = 2 * 2$
$C = 2$
$D = 5 * 3$
Como sabemos que $D$ no posee ningún factor $2$, este tendrá como resultado en los $mcd$ que participe al $1$, $3$ y $5$. Esto lo podemos ver en que los demás números tienen en común al menos un $2$, por lo que el único que nos queda para los resultados impares es $D$.
Ahora intentemos ubicar a todos los $mcd$: vamos a decir que el $2$ por conveniencia es el $mcd$ entre $A$ y $C$. Podríamos hacerlo también entre $B$ y $C$, pero como por ahora son el mismo número, no importa. Tenemos lo siguiente:
$mcd(A, B) = 4$
$mcd(A, C) = 2$
$mcd(B, C) = 2$
El $mcd$ entre $B$ y $C$ debe ser mayor a $2$, pues ya hemos ubicado el $2$ como el $mcd$ entre $A$ y $C$. Sabemos también que ni $C$ ni $B$ pueden incluir mutuamente ni al $3$ ni al $5$, si lo hiciesen, habrían dos resultados de los $mcd$ de $D$ con el mismo factor (no puede ser porque antes vimos que los $mcd$ que incluyen a $D$ son $1$, $3$, y $5$; coprimos dos a dos). Teniendo en cuenta esto, el menor primo mayor que $3$ y $5$ que nos queda agregar a $B$ y a $C$ es $7$:
Veamos que hay $2$ $mcd$ pares, luego siempre hay otro mas, con esto justifico que $N$ es par, veamos que para que N sea mayor que $5$ debe tener al $3$, al $5$, al $7$, o algun otro primo mayor. Veamos que si tiene al $3$, $N=6$. Luego hay $3$ números que tienen al $3$ en su descomposición. Entonces hay $3$ que tienen un $3$ y entonces hay $3$ mcd que son divisibles por $3$, Absurdo! El mismo absurdo se repite de manera análoga para $N=10$ ya que nos dice que habrá $3$ múltiplos de $5$. Luego el mínimo $N$ se da para $N=14$ donde un ejemplo son los números:
$20,28,42,15$