Uri debe pintar de rojo algunos números enteros desde $1$ hasta $2022$ inclusive, a su elección, de manera que ninguna de las diferencias entre dos números rojos es igual a un número primo. Determinar la máxima cantidad de números que puede pintar Uri de rojo.
Nota 1. La diferencia entre dos números distintos es la resta del mayor menos el menor Nota 2. 1 no es primo.
Redefinamos el problema y supongamos que la lista va de 0 a 2021 en lugar de 1 a 2022. También podemos suponer que el primer número pintado es el 0 sin perder generalidad. Indexemos la secuencia creciente de números pintados con $i=0,1,2,… ,I$ (o sea que tiene $I+1$ elementos) y veamos la solución
$x_i = 4i$
Notar que la distancia entre dos elementos consecutivos es siempre 4 y por lo tanto la distancia entre dos números pintados cualesquiera es múltiplo de 4 y por lo tanto no es primo. Esto implica que es una secuencia valida y puede tener hasta 506 elementos ya que
$x_{505}=2020<2021$
y
$x_{506}=2024>2021$
Veamos ahora que es la secuencia válida con la mayor cantidad de elementos.
Llamemos a la distancia entre el elemento $i$ y el $i-1$
$d_i≡x_i-x_ {i-1}$
Si existe una secuencia valida con una mayor cantidad de elementos entonces esta debería tener al menos una distancia menor que 4. Claramente esa distancia no puede ser 2 o 3 ya que estos son primos. Veamos que tampoco puede ser 1. O sea que en la secuencia con la mayor cantidad posible de elementos no puede haber números consecutivos.
Supongamos que hay una secuencia con $507$ elementos o más. O sea que $I>505$.
Supongamos que existe un $0<i<I$ tal que $d_i=1$. Por lo tanto es fácil chequear que $d_{i+1} ≥8$ ya que de otra forma la distancia entre los elementos $i+1$ e $i-1$ es un número primo.
También sabemos que
$∑d_i = x_I ≤ 2021$
Definamos a $z$ como la cantidad veces que hay un $i<I$ con $d_i=1$. Cada uno de estos unos $d_i=1$ está acompañado por un $d_{i+1}≥8$. Las otras distancias menos $d_I$ tienen que ser todas mayores o iguales a 4. Por lo tanto
$(1+8)z + 4(I-2z-1) + 1≤ ∑d_i = x_I ≤ 2021$
O sea
$I≤(2024-z)/4$
Si $z≥1$ entonces
$I≤505,75$
Y como $I$ es entero entonces $I≤505$
PD: Si se preguntar por el caso donde solo la última distancia es igual a 1 entonces solo tiene que reordenar la secuencia para que esa distancia sea la primera en lugar de la última.
En un grupo no puedo elegir mas de $1$ ya que la diferencia de cualesquiera $2$ numeros es un primo, menos para un $x$ y su consecuente.
Si seguimos esto, puedo agarrar a lo sumo $1$ de cada.
Si tomo $1,5,9,13,17,...1+4k, k\leq 505$, puedo tomar $506$ en total. Lo mismo para $2,6,...,2+4k$.
Si empiezo tomando el $3$ maximo tendria $505$, ya que el ultimo grupo de $2$ me restringe el rango de $k$.
Entonces la maxima cantidad de puntos rojos es $506$.
No se puede pintar numeros consecutivos:
Queremos que esta coloracion sea $\geq 507$. Entonces, como en un mismo grupo es rapido ver que tres numeros no es posible colorear, debe haber al menos un grupo con $2$ pintados consecutivos. En el grupo de $4$ inmediato a este, viendo casos chicos vemos que es imposible colorear alguno. Consecuentemente tampoco se puede colocar $2$.
Entonces, si tenemos un grupo con $2$ consecutivos, el siguiente grupo no puede tener ninguno. De esta forma tenemos a lo sumo $2$ por dos grupos, es decir, cada $8$, equivalente a la anterior coloracion.
Concluimos que el maximo es $506$.
Última edición por Lean el Jue 05 Oct, 2023 9:25 pm, editado 1 vez en total.