Cuando hay honestos y mentirosos, una pregunta aislada puede engañar. Pero si sabes emparejar respuestas, puedes hacer que las mentiras se cancelen con las verdades.
El consejero de la mayoría
Enunciado
Un rey tiene 101 consejeros. Cada uno es de uno de estos dos tipos:
- honesto: siempre dice la verdad;
- mentiroso: siempre miente.
El rey puede elegir dos consejeros A y B y preguntar a A: «¿B es honesto?».
¿Cómo puede encontrar con certeza a un consejero que pertenezca al tipo mayoritario?
Ver solución
Solución
La pregunta da una comparación fiable.
Si A responde «sí», A y B son del mismo tipo. Si A es honesto, B es honesto; si A es mentiroso, la afirmación «B es honesto» es falsa, de modo que B también es mentiroso.
Si A responde «no», son de tipos distintos.
Con esa comparación, el rey aplica una cancelación de mayoría. Mantiene un candidato y un contador:
- Empieza con el primer consejero como candidato y contador 1.
- Compara cada nuevo consejero con el candidato.
- Si son del mismo tipo, suma 1 al contador.
- Si son de tipos distintos, resta 1.
- Si el contador llega a 0, toma al siguiente consejero como nuevo candidato y reinicia el contador en 1.
Cada resta cancela una pareja formada por un consejero de cada tipo. Como hay 101 consejeros, un tipo aparece más veces que el otro. Tras cancelar parejas opuestas, el candidato final tiene que pertenecer al tipo mayoritario.
El rey no necesita saber si ese tipo es el de los honestos o el de los mentirosos para cumplir la meta.
Respuesta: usa las respuestas como comparaciones de igualdad y aplica el algoritmo de cancelación de mayoría.