Problema 3 del segundo nivel de la Olimpiada de Mayo 2023
Se dirige a una edad de: 13-14 años

En el pizarrón están escritos los 49 números 2, 3, 4, . . . , 49, 50.

Una operación permitida consiste en elegir dos números distintos a y b del pizarrón tales que a sea múltiplo de b y borrar exactamente uno de los dos.

María hace una secuencia de operaciones permitidas hasta que observa que ya no es posible hacer ninguna más.

Determinar la mínima cantidad de números que pueden quedar en el pizarrón en ese momento.

Solución:

Inicialmente, podemos pensar que quedarán los números primos, pero algunos números primos podemos eliminarlos, si tienen un múltiplo común con otro número primo.

Por ejemplo, podemos eliminar con el 2 todos los números pares, excepto el 6, seleccionar el 2 y el 6 para eliminar el 2 y después eliminar el 6 con el 3. De esta forma, eliminaremos todos los números pares, incluyendo el propio 2.

Sin embargo, hay números primos en el conjunto inicial que no dividen a ningún otro número, y que por lo tanto no podrán ser eliminados. Concretamente, el 29, el 31, el 37, el 41, el 43 y el 47 no se podrían eliminar de ninguna forma.

Todos los demás números es posible eliminarlos de alguna forma, pero habrá uno que deberá quedarse sin ser eliminado. Por ejemplo, podemos eliminar 23 con 46, y después 46 con el 2.

Sucesivamente, podremos eliminar todos los primos en orden decreciente, hasta llegar a eliminar a todos sus múltiplos. Por ejemplo, cuando no queden múltiplos de primos entre 11 y 29, eliminamos todos los múltiplos de 11 usando el propio 11, excepto el 22. Con el 22, eliminamos el 11, y con el 2, eliminamos el 22.

De esa forma, eliminaremos todos los números entre 2 y 28, de forma que sólo quedará uno (podemos elegir cuál es el número que queda, pero no podremos evitar que quede uno, pues no divide ni es dividido por ninguno de los otros que quedan).

Por tanto la cantidad mínima de números que quedan es 7.