Problema 1 de la Fase Local de la Olimpiada Española de Matemáticas 2023 (viernes mañana)
Se dirige a una edad de: 16-17 años

Sea n un entero positivo.

Cada uno de los números 1, 2, 3, …, 2023 se pinta de un color a escoger entre n distintos.

Una vez coloreados, se observa que cualquier par (a, b) con a < b y de manera que a | b (a divide a b), satisface que a y b son de distinto color.

Encuentra el menor valor de n para el cual esta situación es posible.

Solución:

La idea clave es que debemos construir cadenas de números en la que cada número sea divisible por todos los de la izquierda de esa cadena, y estudiar cuál es más larga. Esta situación se puede ensayar escribiendo los 10 números del 1 al 10, tratando de colorearlos según las reglas, y viendo que necesitamos al menos 4 colores.

Es evidente que 1 debe ser de un color diferente a todos los demás, pues 1 divide a cualquier número. Sin embargo, todos los números primos pueden ser del mismo color, ya que ninguno divide al otro.

Una idea muy básica es que si descomponemos un número en factores primos, y presenta una cierta cantidad de números primos en su descomposición (posiblemente varios de ellos repetidos), le pintemos de color que esté marcado con la cantidad de primos de su descomposición + 1.

Así, por ejemplo, si ponemos un color 1, sólo aparecerá en el 1.

El color 2 aparecerá únicamente en los primos, cuyo único divisor inferior a ellos mismos es el 1.

Los números con 2 factores, como el caso del 4, el 6, el 9, se pintan del color 3.

Si seguimos este procedimiento necesitaremos un número n de 11 colores, el último de los cuales servirá para pintar el 2¹⁰ y el 2⁹·3, que están en la lista. No hay números con más factores, ya que el primero que tiene 11 factores es 2¹¹, que vale 2048, por ser 2 el menor número primo.

Es evidente que una tal distribución de colores cumple el enunciado, ya que si a < b y a | b, los primos de la descomposición de a son algunos de la descomposición de b, no todos, por ser menor y divisible, por lo que están pintados de diferente color.

Para ver que es el menor valor posible de n, basta constatar que la cadena 1 < 2 < 4 < 8 < 16 < 32 < 64 < 128 < 256 < 512 < 1024 hay 11 números, y no puede haber 2 con el mismo color según el enunciado, así que debe ser 11, ya que hay una distribución con 11 y no puede darse con menos.

Otro método de coloreado que puede probarse fácilmente que es válido (y usa 11 colores) es pintar del mismo color todos los números entre una potencia de 2 (incluida) hasta la siguiente. Es decir, 1 de un color, 2 y 3 de otro, del 4 al 7 de otro, y así sucesivamente. Así, nunca un número y su doble o los números siguientes son del mismo color.

con este coloreado, si dos números diferentes a y b tienen la relación de a < b y a|b, entonces 2a <= b, cosa que impide que sean del mismo color.