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

Sandy

OFO - Medalla de Bronce
Mensajes: 27
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 2

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

Mensaje sin leer por Sandy » Mar 13 Nov, 2018 9:40 pm

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.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata
Mensajes: 51
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 3
Nivel: 1

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

Mensaje sin leer por BrunZo » Mar 12 Feb, 2019 5:49 pm

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).

Responder