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