Rioplatense 2017 - N1 P1

[ésta]

Samantha debe escribir en la pizarra algunos números enteros positivos distintos.
Después de haberlos escrito, diremos que un número $k$ ha sido capturado por Samantha si hay en la pizarra dos números distintos cuyo máximo común divisor es $k$.
¿Cuál es la menor cantidad de números que puede escribir Samantha para que los catorce números $1, 2, 3, \ldots, 14$ sean capturados?
Mostrar un ejemplo con esa cantidad de números y explicar por qué si escribe menos números no puede lograrlo.

[Joacoini]

Spoiler: mostrar

Ejemplo con $7$.
$12=2^2\cdot 3$
$42=2\cdot 3\cdot 7$
$55=5\cdot 11$
$70=2\cdot 5\cdot 7$
$360=2^3\cdot 3^2\cdot 5$
$819=3^2\cdot 7\cdot 13$
$1144=2^3\cdot 11\cdot 13$

Veamos que con menos no se puede.

La única forma de capturar un par es usando dos números pares, si tenemos $4$ o menos pares podemos capturar como mucho $\frac{4\cdot 3}{2}=6$ pero como tenemos que capturar $7$ pares entonces requerimos que en el pizarrón halla $5$ o más pares.
Si hay $2$ impares entonces estamos y si no hay impares no podemos capturar, veamos que pasa con un impar.

Si hay un solo impar la única forma de capturar impares es unsandolo a este y la máxima cantidad de números que puede capturar es uno por cada par pero como hay que capturar $7$ impares entonces se requieren $7$ pares por lo que descartamos este caso y ya estamos.