Nacional 2022 - Nivel 1 - Problema 4

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 1 - Problema 4

Mensaje sin leer por Monazo »

En una reunión hay $22$ amigos, algunos son veraces, que siempre dicen la verdad, y los demás mentirosos, que siempre mienten. Cada uno piensa un número real (no necesariamente entero). Los $22$ amigos se ponen en fila y cada uno dice exactamente una frase. El primero dice "mi número es mayor que $1$"; el segundo dice "mi número es mayor que $2$"; el tercero dice "mi número es mayor que $3$"; y así siguiendo hasta que el último dice "mi número es mayor que $22$". A continuación, cambian arbitrariamente de lugar en la fila y ahora, en el nuevo orden, cada amigo dice exactamente una frase. El primero dice "mi número es menor que $1$"; el segundo dice "mi número es menor que $2$"; el tercero dice "mi número es menor que $3$"; y así siguiendo hasta que el último dice "mi número es menor que $22$". Determinar la máxima cantidad de veraces que puede haber entre los $22$ amigos.
Soy una Estufa en Piloto
:shock:
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 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: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2022 - Nivel 1 - Problema 4

Mensaje sin leer por Gianni De Rico »

La idea para la cota la contaron en la discusión de problemas, el ejemplo es de @Male Arias
Spoiler: mostrar
Miremos al último amigo, el que dice "mi número es mayor que $22$". Después del cambio, va a decir "mi número es menor que $n$", donde $n$ puede ser cualquier número entero entre $1$ y $22$, entonces no puede ser veraz, porque en ese caso se tendría que su número es mayor que $22$ y menor que un número $n$ menor o igual que $22$ (y por lo tanto menor que $22$). Entonces el último amigo es un mentiroso. Con esto obtenemos que siempre hay por lo menos un amigo mentiroso, es decir, que siempre hay a lo sumo $21$ amigos veraces.
Veamos ahora que puede haber $21$ amigos veraces. Digamos que el amigo $1$ pensó el número $1,5$, el amigo $2$ pensó el número $2,5$, el amigo $3$ pensó el número $3,5$, y así hasta el amigo $21$ que pensó el número $21,5$. Además, el amigo $22$ pensó el número $2$ (cualquier número mayor que $1$ y menor que $22$ nos va a servir para este ejemplo). Hacemos que el amigo $1$ vaya a la posición $2$, el amigo $2$ a la posición $3$, el amigo $3$ a la posición $4$, y así hasta el amigo $21$ que va a la posición $22$. Además, el amigo $22$ va a la posición $1$. Entonces el amigo $1$ (que pensó el $1,5$) dice "mi número es mayor que $1$" y "mi número es menor que $2$", así que siempre dice la verdad. El amigo $2$ (que pensó el $2,5$) dice "mi número es mayor que $2$" y "mi número es menor que $3$", así que siempre dice la verdad. Siguiendo así vemos que todos los amigos entre $1$ y $21$ dicen la verdad (el amigo $k$ piensa el número $k,5$ y dice "mi número es mayor que $k$ y menor que $k+1$"). Además, el amigo $22$ miente, porque pensó el $2$ pero dice "mi número es mayor que $22$" y "mi número es menor que $1$". Entonces en este ejemplo tenemos $21$ amigos veraces.
Como dimos la cota y el ejemplo, concluimos que la máxima cantidad de veraces que puede haber entre los $22$ amigos es $21$, y ganamos.
1  
♪♫ do re mi función lineal ♪♫
Responder