Host: No mostrado/ Not shown
IP: No mostrado/ Not shown
Sistema: Windows XP
Señores, cerraduras y llaves. (solución)
Publicidad
Hola.
Creo tener la solución del problema siguiente:
12 señores tienen acceso a documentos de una caja fuerte. Calcular el número mínimo de cerraduras que ha de tener la caja, el número de llaves que han de hacer de cada cerradura y cómo se han de distribuir éstas para que puedan abrir la caja sólo cuando estén reunidos al menos la mitad más uno.
Tenemos a los señores A,B,C,D,E,F,G,H,I,J,K,L Llamaré X4 a una llave que abre la cerradura número 4.
Lo primero que hago es una lista de todas las maneras posibles que hay de dividir a los 12 señores en 2 grupos de 6.
ABCDEF-GHIJKL ABCDEG-FHIJKL ... ...
¿Cuántas filas tendrá ésta lista? Pues tantas como maneras de elegir 6 elementos de un conjunto de 12. Esto son las combinaciones de 12 elementos tomados de 6 en 6. El resultado es 924. Pero realmente nos tenemos que quedar sólo con la mitad, ya que cada combinación aparece realmente 2 veces ( la combinación ABCDEF-GHIJKL y la GHIJKL-ABCDEF son en realidad la misma). Así que me quedo con el número 462.
Ahora vayamos repasando la lista de 462 filas y asignando llaves. En la primera fila daremos llaves X1 a los señores ABCDEF y llaves X2 a los señores GHIJKL. En la segunda fila daremos llaves X3 a los señores ABCDEG y llaves X4 a los señores FHIJKL. Si seguimos éste proceso así, acabaremos repartiendo 6 llaves X1, 6 llaves X2,... y así hasta repartir 6 llaves X924.
Necesitamos 924 cerraduras, 6 llaves para cada cerradura. Total 5544 llaves.
Éste reparto funciona porque cualquier grupo de 6 señores aparece alguna vez en la lista. Cuando se hace el reparto a éstos señores se les da una llave, pero hay una que no se les da (se les entrega a cada señor del grupo complementario). Cualquier señor que se agregue a éstos 6, tendrá la llave que falta.
Falta explicar por qué esa llave es la única que les falta. Si les faltara también otra llave (la XY), es que todos ellos han aparecido en una combinación en la que se otorgaba la llave XY al grupo complementario. Pero un mismo grupo de señores solo aparecen una vez en el listado que hemos hecho.
No sé, salen muchas cerraduras y muchas llaves, pero no se me ocurre nada mejor.
Gran problema.
Respuestas (2)
» Señores, cerraduras y llaves. (solución) « - albert - 2/04/2008 12:27
2/04/2008 12:27
Señores, cerraduras y llaves. (solución)
