XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 2

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

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 2

Mensaje sin leer por Sandy »

En una isla con $2018$ habitantes cada persona es un caballero, un mentiroso o un conformista. Todo el mundo sabe lo que es cada habitante de la isla. Un día todos los habitantes de la isla formaron una fila y, por turnos, siguiendo el orden de la fila, cada persona respondió (por sí o por no) la pregunta "¿Entre los habitantes de esta isla, hay más caballeros que mentirosos?". Todos escuchan todas las respuestas anteriores a la suya. Los caballeros dicen siempre la verdad, los mentirosos siempre mienten y cada conformista responde lo que han dicho la mayoría de los que están antes que él en la fila. En caso de que antes de él haya igual número de respuestas "Sí" y "No", el conformista elige una de ellas al azar. Al terminar de responder los $2018$ de la fila hubo exactamente $1009$ respuestas "Sí". Determinar la mayor cantidad posible de conformistas que puede haber entre los habitantes de la isla.
Fallo inapelable.
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-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 - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 2

Mensaje sin leer por BrunZo »

Solución:
Spoiler: mostrar
Por comodiad, diremos que "sí" es $1$ y "no" es $-1$. Además, llamaremos $f(n)$ a la suma de las respuestas hasta el $n$-ésimo habitante.
Entonces, $f(n)>0$ sí y sólo sí, hasta ese momento, hubo más respuestas "sí" que "no", y viceversa. Luego, vamos a dividir la fila en grupos, de modo que cada vez que $f(n)=0$, se termina el grupo. Y usando que $f(0)=f(2018)=0$, sabemos que esta partición abarca a todos los habitantes.

Parte 1. Sea $A=(a;b)$ uno de estos grupos, entonces $\forall n\in A, n\neq b$, $f(n)>0$ ó $\forall n\in A, n\neq b$, $f(n)<0$.
Spoiler: mostrar
Supongamos que existen $x, y\in A$ tal que $f(x)<0<f(y)$. Entonces, $\exists z$ con $x<z<y$ y $f(z)=0$. Absurdo.
De este modo, decimos, en cada caso, que el grupo es positivo o negativo. Más aun, todos los conformistas de un grupo positivo deberán decir "sí" y viceversa.

Parte 2. En el grupo $A$, hay la misma cantidad de "síes" que "noes".
Spoiler: mostrar
Sabemos que $f(a-1)=f(b)=0$. Además, por la definición de $f$, habiendo $s$ "síes" y $n$ noes, tenemos $f(b)=f(a-1)+s-n$, luego $s=n$.
Entonces, si hay $|A|$ habitantes en este grupo, la cantidad de "síes"/"noes" es $\frac{|A|}{2}$, de modo que no puede haber más de $\frac{|A|}{2}$ conformistas en $A$.
Entonces, tomando la cantidad de habitantes en todos los grupos $|A_i|$; y la cantidad de conformistas $c_i$ en cada grupo. Tenemos,
$$\sum c_i\leq\sum \frac{|A_i|}{2}\leq\frac{\sum |A_i|}{2}=1009$$
Luego el máximo es $1009$.

El ejemplo podría ser Co, M, Co, M, Co, M,..., Co, M; de modo que los $1009$ conformistas dicen "no" (al azar) y los otros $1009$ mentirosos dicen "sí" (puesto que no hay más caballeros que mentirosos).
Avatar de Usuario
fran :)

FOFO 12 años - Mención-FOFO 12 años OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Copa-FOFO 13 años
Mensajes: 20
Registrado: Mié 22 Jun, 2022 6:04 pm
Medallas: 3
Nivel: 3
Ubicación: Buenos Aires

Re: XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 2

Mensaje sin leer por fran :) »

mi solución :)
Spoiler: mostrar
Con 1009 conformistas y 1009 caballeros se puede: va primero un conformista, y luego se van alternando caballeros y conformistas. Todos los conformistas responden "no" ya que tienen un empate entre respuestas afirmativas y negativas al frente suyo, y todos los caballeros responden "sí" porque hay más caballeros que mentirosos

Llamemos $S$ a la cantidad de respuestas afirmativas ("Sí") y $N$ a la cantidad de respuestas negativas ("No"). Ahora consideremos como varía la cantidad $|S - N|$ a medida que los habitantes van respondiendo.

Si el habitante que responde es conformista, $|S - N|$ necesariamente aumentará por 1, mientras que si no lo es, puede aumentar o disminuir por 1.

Como $S = 1009$ y $S + N = 2018$, entonces $|S - N| = 0$ al final del torneo. Si hay más de 1009 conformistas que van a aumentar $|S - N|$, entonces necesitamos más de 1009 no-conformistas para que $|S - N|$ vuelva a bajar a 0 para el final del día. Pero esto es imposible porque hay 2018 habitantes. Entonces, el máximo de conformistas es 1009.
$$\phantom{[muajajacaracteresinfinitos=}\begin{matrix}(λx.F\;a)&→&x=a;F\\(\{x_0\;x_1\}\;a)&→&\{a_0\;a_1\}=a;\{(x_0\;a_0)\;(x_1\;a_1)\}\\\{a_0\;a_1\}=\{b_0\;b_1\}&→&a_0=b_0;a_1=b_1\\\{a_0\;a_1\}=λx.F&→&x=\{x_0\;x_1\};\{f_0\;f_1\}=F;a_0=λx_0.f_0;a_1=λx_1.f_1\end{matrix}\phantom{]}$$
Responder