Nacional 2022 - Nivel 2 - Problema 2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Nacional 2022 - Nivel 2 - Problema 2

Mensaje sin leer por Monazo »

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.
Soy una Estufa en Piloto
:shock:
alerodri1976
Mensajes: 18
Registrado: Jue 20 Feb, 2020 7:21 pm
Nivel: Ñandú

Re: Nacional 2022 - Nivel 2 - Problema 2

Mensaje sin leer por alerodri1976 »

Spoiler: mostrar
La máxima cantidad de números que puede pintar de rojo es 506.
Spoiler: mostrar
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.
Avatar de Usuario
Lean

OFO - Medalla de Bronce-OFO 2023 FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Plata-OFO 2024
Mensajes: 176
Registrado: Vie 20 Ene, 2023 10:38 am
Medallas: 3
Nivel: 3
Ubicación: Quilmes

Re: Nacional 2022 - Nivel 2 - Problema 2

Mensaje sin leer por Lean »

Spoiler: mostrar
Dividimos los numeros $1,2,3,4,5,6...,2022$ en grupos de $4$:

$(1,2,3,4),(5,6,7,8),...,(2017,2018,2019,2020),(2021,2022)$.

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.
"El mejor número es el 73".
alerodri1976
Mensajes: 18
Registrado: Jue 20 Feb, 2020 7:21 pm
Nivel: Ñandú

Re: Nacional 2022 - Nivel 2 - Problema 2

Mensaje sin leer por alerodri1976 »

Lean escribió: Sab 30 Sep, 2023 12:45 pm
Spoiler: mostrar
Dividimos los numeros $1,2,3,4,5,6...,2022$ en grupos de $4$:

$(1,2,3,4),(5,6,7,8),...,(2017,2018,2019,2020),(2021,2022)$.

En un grupo no puedo elegir mas de $1$ ya que la diferencia de cualesquiera $2$ numeros es un primo.
Entonces 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$.
1 no es primo por lo tanto si se pueden elegir dos números de un mismo grupo.
Responder