Parece un problema de cerrajería, pero en realidad es un problema de exclusión. No hay que pensar primero en quién debe poder abrir la caja, sino en quién debe quedar bloqueado.
La caja que solo abren tres
Enunciado
Cinco personas quieren guardar un secreto en una caja.
Pueden poner tantos candados como quieran en la caja y repartir copias de llaves como quieran.
Quieren que se cumplan estas dos condiciones:
cualquier grupo de 3 personas puede abrir la caja;
ningún grupo de 2 personas puede abrirla.
¿Cuál es el menor número de candados que necesitan?
Ver solución
Solución
La respuesta es:
La idea es poner un candado por cada pareja de personas.
Como hay 5 personas, el número de parejas es:
Para cada pareja, hacemos esto:
ponemos un candado especial contra esa pareja; damos la llave de ese candado a las otras tres personas.
Por ejemplo, si las personas son A, B, C, D y E, ponemos un candado que A y B no pueden abrir, pero cuyas llaves tienen C, D y E.
Así se hace con cada una de las 10 parejas.
Ahora comprobamos que funciona.
Si van solo dos personas, por ejemplo A y B, habrá un candado pensado justo contra esa pareja. Ninguno de los dos tiene la llave, así que no pueden abrir la caja.
Pero si van tres personas cualesquiera, siempre podrán abrir todos los candados.
¿Por qué?
Cada candado solo excluye a una pareja concreta. Un grupo de tres personas no puede estar contenido dentro de una pareja de dos. Por tanto, para cada candado, dentro del grupo de tres habrá al menos una persona que sí tenga la llave.
Así que cualquier trío puede abrir.
Además, no se puede hacer con menos de 10 candados.
Cada una de las 10 parejas debe quedar bloqueada por algún candado. Y un mismo candado no puede bloquear a dos parejas distintas, porque entonces habría al menos tres personas sin llave de ese candado, y ese trío no podría abrir la caja.
Por tanto, hacen falta al menos 10.
Respuesta: el mínimo es 10 candados.