NOTA: me confundió que los mentirosos en el OP de la definición de ambos pueden decir la verdad y la mentira. Esta solución se supone que los mentirosos siempre mentira.
Asociar una verdad-teller con el valor booleano $0$ y un mentiroso con el valor booleano $1$. Deje $+$ ser la disyunción exclusiva (es decir,, $0+0=0$, $0+1=1$, $1+0=1$, y $1+1=0$). Para una persona $P$, vamos a $f(P)$ ser el booleana asociada a $P$. Por lo tanto, para dos personas $A$$B$, si le preguntas a $A$ si $B$ es un mentiroso, a continuación, $A$ se podría decir $B$ no es un mentiroso si $f(A)+f(B)=0$, e $A$ diría lo contrario si $f(A)+f(B)=1$.
Escoge a una persona $X$. Pregunte $X$ $54$ a otras personas. Usted sería capaz de encontrar que las personas entre estos $54$ son del mismo tipo como $X$ (es decir, los $Y$'s tal que $f(X)+f(Y)=0$, o, equivalentemente,$f(X)=f(Y)$). Si al menos $27$ de ellos son del mismo tipo como $X$, $X$ debe ser una verdad-teller (como sólo hay $27$ mentirosos, y el grupo de personas como $X$ contiene al menos $27+1$ de los miembros). Si no, entonces por lo menos $28$ de estos chicos son de diferente tipo de $X$ (es decir, los $Y$'s $f(X)+f(Y)=1$), lo que significa que son verdad-escrutadores.
Por lo tanto, la tarea se puede hacer con la mayoría de las $54$ cuestionamientos. Me dicen que este es el mínimo número posible de preguntas para que esta tarea siempre se lleva a cabo con éxito.
Supongamos que hay una manera de pedir a la gente a su alrededor con menos de $54$ preguntas. Ahora, considere la posibilidad de un gráfico de $G(V,E)$, donde el conjunto de vértices $V$ es el conjunto de todas las personas en la habitación y el conjunto de borde $E$ donde un borde se dibuja entre dos personas si y sólo si uno es interrogado sobre el otro. Tenemos $|E|\leq 53$. Tenga en cuenta que los cuestionamientos, sólo nos dice la información sobre cada componente de $G$, y sólo podemos completar la tarea si hay un componente conectado en la que hay, al menos, $28$ vértices del mismo tipo. Sin embargo, un mayor componente conectado de $G$ tiene más de $|E|+1\leq 54$ vértices, y por lo tanto, es posible reasignar las personas por lo que este componente conectado se tienen en la mayoría de $27$ personas de cada tipo. Saber nada acerca de otros componentes conectados no contribuir más información.
Más generalmente, si hay $m$ verdad-cajeros y $n$ mentirosos con $m \neq n$, entonces el número mínimo de los cuestionamientos que la tarea siempre puede llevarse a cabo es $2\min\{m,n\}$. Usted no tiene ninguna esperanza si $m=n$.
