Nacional 2019 - Nivel 3 - Problema 6

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 2019 - Nivel 3 - Problema 6

Mensaje sin leer por Monazo »

Los números naturales desde $1$ hasta $300$ inclusive se ubican alrededor de una circunferencia. Decimos que un tal ordenamiento es alternado si cada número es menor que sus dos vecinos o es mayor que sus dos vecinos. A un par de números vecinos lo llamaremos par bueno si al quitar ese par de la circunferencia, los restantes números forman un ordenamiento alternado.
Determinar la menor cantidad posible de pares buenos que puede haber un ordenamiento alternado de los números del $1$ al $300$ inclusive.
Soy una Estufa en Piloto
:shock:
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 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 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Nacional 2019 - Nivel 3 - Problema 6

Mensaje sin leer por Joacoini »

Me hubiese gustado haber pasado a resolver este en vez de a rapear sumas.
Spoiler: mostrar

Veamos que cada número aparece en al menos un par bueno.

Supongamos que un número $c$ no pertenece a ningún par bueno. Si $a, b, c, d, e$ son $5$ números consecutivos.

Si $a<b, b>c, c<d, d>e$, como $(b;c)$ no es bueno tenemos que $a>d\Rightarrow b>a>d>e\Rightarrow (c;d)$ es bueno.

Si $a>b, b<c, c>d, d<e$, como $(b;c)$ no es bueno tenemos que $a<d\Rightarrow b<a<d<e\Rightarrow (c;d)$ es bueno.

Ahora veamos que hay al menos un número que aparece en dos pares buenos, para eso consideramos los $6$ números consecutivos $a, b, c, 1, d, e, f$.

Tenemos que $a>b, b<c, c>1, 1<d, d>e, e<f$ ya que el $1$ es el más chico y por la misma razón $1<a$ y $1<f$ por lo que los pares $(b;c)$ y $(d;e)$ son buenos pero por lo que dedujimos antes $1$ tiene que estar en al menos un par bueno, por lo que alguno entre $c$ y $d$ pertenece a dos pares buenos.

Tenemos que el mínimo de pares buenos que puede haber es $\frac{300+1}{2}$ pero como la cantidad de pares buenos es entera tienen que haber al menos $151$ pares buenos.

Un ejemplo con $151$ pares buenos es ubicar los $300$ números de forma consecutiva y cambiar de lugar los de la forma $2k$ con los de la forma $2k+1$ (el $1$ y el $300$ se quedan como estan).

Quedaría así $1, 3, 2, 5, 4, 7, 6, ..., 297, 296, 299, 298, 300$.

Para comprobar que anda veamos que cada número esta en exactamente un par bueno excepto por $3$ y $298$.

Los pares $(1;3), (3;2), (299;298), (298;300)$ son buenos y $(300;1), (2;5), (296;299)$ no lo son por lo que $3$ y $298$ están en dos pares buenos y $1, 2, 299, 300$ están en un solo par bueno.

Veamos que los de la forma $2k$ con $1<k<149$ están en exactamente un par bueno, los números cercanos están ubicados de la siguiente forma.

$2k-2, 2k+1, 2k, 2k+3, 2k+2$

$(2k+1;2k)$ es bueno pero $(2k;2k+3)$ no.

Veamos que los de la forma $2k+1$ con $1<k<149$ están en exactamente un par bueno, los números cercanos están ubicados de la siguiente forma.

$2k-1, 2k-2, 2k+1, 2k, 2k+3$

$(2k+1;2k)$ es bueno pero $(2k+1;2k-2)$ no.

Y ya estamos.
1  
NO HAY ANÁLISIS.
Responder