Sea $k\geq 1$ un entero. En un grupo de $2k+1$ personas algunas son sinceras (siempre dicen la verdad) y las restantes son impredecibles (a veces dicen la verdad y a veces mienten). Se sabe que las impredecibles son a lo sumo $k$. Alguien ajeno al grupo debe determinar quién es sincero y quién impredecible mediante una secuencia de pasos. En cada paso elige dos personas $A$ y $B$ del grupo y le pregunta a $A$ ¿es $B$ sincero?
Demostrar que al cabo de $3k$ pasos el forastero podrá clasificar con certeza a las $2k+1$ personas del grupo.
(Antes de formular cada pregunta se conocen las respuestas de las anteriores preguntas.)
Aclaración: Cada una de las $2k+1$ personas del grupo sabe cuáles son sinceras y cuáles impredecibles.
Editado porque tengo que corregir un error y emprolijar unas cosas (estaba tan desprolijo que tuve que leer mi propio mensaje 3 veces para entender que razonamiento había hecho). Disculpen.
Sean $p_1,p_2,\ldots ,p_{2k+1}$ las personas. Las acomodamos en ese orden en una fila especial $e$. Defino $p_x\rightarrow p_y$ la operación de preguntarle a $p_x$ sobre $p_y$, defino $p_x=T$ si $p_x$ es sincero y $p_x=F$ si $p_x$ es indeciso, $p_x\rightarrow p_y$ toma el valor que tiene $p_y$ según $p_x$. Un grupo está resuelto cuando todas las personas están clasificadas con certeza
Colocamos a $p_1$ en una nueva fila $t$. Hacemos $p_1\rightarrow p_2$, y mientras la respuesta sea $T$ colocamos a $p_2$ delante de $p_1$ en $t$ y hacemos $p_i\rightarrow p_{i+1}$.
$1)$
Si siempre tenemos $p_i\rightarrow p_{i+1}=T$, al cabo de $k$ pasos tenemos $p_{k+1}=T$ ya que $p_i\rightarrow p_{i+1}=T\wedge p_{i+1}=F\Rightarrow p_i=F$ (*) por lo que si $p_{k+1}$ fuera $F$ tendríamos $p_i=F\forall 1\leqslant i\leqslant k+1$ ABS!! pues hay a lo sumo $k$ indecisos.
Luego, como $p_{k+1}=T$, hacemos $p_{k+1}\rightarrow p_i\forall 1\leqslant i\leqslant 2k+1,i\neq k+1$, es decir $2k$ preguntas, y con eso identificamos a todas las personas, en total usamos $k+2k=3k$ preguntas.
$2)$
Veamos que a un grupo de $3$ personas lo podemos resolver en $3$ pasos
Sean $A,B,C$ las personas.
Hacemos $A\rightarrow B$
Caso $1$: Si $A\rightarrow B=T$ entonces $B=T$ por (*). Hacemos $B\rightarrow A$ y $B\rightarrow C$ y con eso identificamos a todos usando $3$ preguntas.
Caso $2$: Si $A\rightarrow B=F$ entonces hacemos $A\rightarrow C$ Subcaso $2.1$: Si $A\rightarrow C=F$ entonces $A=F$. Pues si $A=T$ resulta que hay dos indecisos, pero hay a lo sumo un indeciso ABS!! luego $A=F$ y como hay a lo sumo un indeciso tenemos $B=C=T$ Subcaso $2.2$: Si $A\rightarrow C=T$ entonces $C=T$ por (*). Hacemos $C\rightarrow A$ Subcaso $2.2.1$: Si $C\rightarrow A=F$ entonces $A=F$ y como no puede haber más indecisos, $B=T$ Subcaso $2.2.2$: Si $A\rightarrow C=T$ entonces $A=T\Rightarrow B=F$
Entonces identificamos a todos usando $3$ preguntas
Sea $n\geqslant 1$
Supongamos que podemos resolver un grupo de $2n+1$ personas en $3n$ pasos $\forall n\leqslant k$. Veamos que podemos resolver un grupo de $2(k+1)+1=2k+3$ personas en $3(k+1)=3k+3$ pasos.
Ponemos a $p_1$ en $t$ y hacemos $p_1\rightarrow p_2$
Si $p_1\rightarrow p_2=F$ ponemos a $p_2$ en una fila $f$
Si $p_1\rightarrow p_2=T$ ponemos a $p_2$ en $t$
En cada paso tomamos a la última persona que agregamos a $t$ y e preguntamos por la primer persona en $e$
Si la respuesta es $T$, agregamos esa persona a $t$
Si la respuesta es $F$, agregamos esa persona a $f$
Sean $C_t,C_f$ la cantidad de personas de $t$ y $f$, respectivamente. Sean $t_i,f_i$ las personas en la posición $i$ de $t$ y $f$, respectivamente.
Si en algún momento $C_t=C_f=x$, detenemos el proceso y nos quedamos con el grupo de las personas que están en $e$
Como originalmente $C_t=1>0=C_f$ y en cada paso $C_f$ aumenta en $0$ o $1$, tenemos $C_t\geqslant C_f$ en todo momento del proceso
Notemos entonces que o bien hicimos $t_i\rightarrow f_i$ o hicimos $t_m\rightarrow f_i$ con $m>i$, pero hicimos $t_{m-1}\rightarrow t_m\forall m$, luego, deshaciendo la secuencia de preguntas desde $f_i$ llegamos a $t_i$. Por lo tanto, $f_i=T\Rightarrow t_z=F\forall 1\leqslant z\leqslant i$ por (*). A su vez, $t_i=T\Rightarrow t_r=T\Rightarrow f_r=F\forall r\geqslant i$ (**)
Juntando estos dos resultados tenemos que hay al menos $x$ indecisos entre $t$ y $f$ cuando $C_t=C_f=x$, luego, hay a lo sumo $k+1-x$ indecisos en $e$, pero en total hay $2(k+1)+1-2x=2(k+1-x)+1$ personas en $e$. Luego, $e$ es un grupo con menos personas que cumple con las condiciones, entonces podemos resolverlo en $3k+3-3x$ pasos.
Usamos $2x-1$ preguntas para formar $t$ y $f$, ya que preguntamos exactamente una vez por cada persona salvo $p_1$, por el que no preguntamos.
En total usamos $3k+3-3x+2x-1=3k+3-x-1$ preguntas, por lo tanto, nos quedan $x+1$ preguntas. Veamos que nos alcanzan.
Sea $e_t$ un sincero de $e$
Hacemos $e_t\rightarrow t_x$
Si $e_t\rightarrow t_x=T$ entonces $f_x=F$ y hacemos $e_t\rightarrow t_{x-1}$. Repetimos esto mientras la respuesta sea $T$. Si esto ocurre siempre, usamos $x$ preguntas y con eso resolvemos el grupo.
Si al cabo de $s$ preguntas tenemos $e_t\rightarrow t_{x-s-1}=F$ entonces $t_i=F\forall 1\leqslant i\leqslant x-s-1$, y $f_i=F\wedge t_i=T\forall x-s-1<i\leqslant x$. Como sabemos sobre $s-1$ personas de $f$ preguntamos por las otras $x-(s-1)=x-s+1$ personas de $f$. En total usamos $x-s+1+s=x+1$ preguntas.
Si llegamos a $C_t=C_f=k+1$ entonces $e$ es un grupo de $1$ personas en el que a lo sumo $0$ son indecisos, luego, sabemos que la única persona de $e$ es sincera en $0$ pasos.
Si siempre se cumple que $C_t>C_f$, cuando llegamos a $C_t=k+2$ tenemos por (*) que $t_{k+2}$ es sincero. Usamos el método anterior para resolver $f$ y $t_i$ con $i\leqslant C_f$ en $C_f$ pasos, al grupo de las $C_t-C_f-1$ personas restantes en $t$ lo resolvemos en $C_t-C_f-1$ pasos. Como $C_t-1=k+1$ las personas sobrantes son exactamente $C_t-C_f-1$, y a este grupo lo resolvemos en $C_t-C_f-1$ pasos. En total usamos $C_f+C_t-C_f-1+C_t-C_f-1=2C_t-C_f-2$ pasos. Para armar $t$ y $f$ usamos $C_t+C_f-1$ pasos. En total usamos $3C_t-3=3k+3$ pasos.
