Encontrar a una persona especial entre cien parece exigir muchas comprobaciones. Pero una buena pregunta no solo da información: también elimina candidatos.
La celebridad invisible
Enunciado
En una fiesta hay 100 personas y se sabe que existe una celebridad con esta propiedad:
- todo el mundo conoce a la celebridad;
- la celebridad no conoce a nadie.
Puedes hacer preguntas del tipo «A, ¿conoces a B?».
¿Cómo puedes identificar a la celebridad usando solo 99 preguntas?
Ver solución
Solución
Sí, puedes encontrar un candidato con 99 preguntas.
Empieza con dos personas, A y B.
Pregunta:
“A, ¿conoces a B?”
Si A responde que sí, entonces A no puede ser la celebridad, porque la celebridad no conoce a nadie. En ese caso, conservas a B como posible celebridad.
Si A responde que no, entonces B no puede ser la celebridad, porque todo el mundo debería conocer a la celebridad. En ese caso, conservas a A como posible celebridad.
En una sola pregunta has descartado a una persona.
Ahora enfrentas al candidato que queda contra una tercera persona. Otra pregunta descarta a uno de los dos.
Repites el proceso con las 100 personas.
Después de 99 preguntas queda un único candidato posible.
Como el enunciado garantiza que la celebridad existe, ese candidato tiene que ser la celebridad.
Respuesta: sí. Basta con 99 preguntas, descartando una persona en cada pregunta.