En cierta ciudad en la época del Rey Jacobo, tenían todas las cosas de valor encerradas bajo llave en un cofre en la iglesia. El cofre tenía un cierto número de cerraduras, cada una con una única llave y todas distintas. El propósito de la ciudad era que cada tres personas tuviesen entre ellas suficientes llaves para abrir el cofre, pero que nunca dos personas solas pudiesen abrirlo ¿cuantas cerraduras se requieren y cuantas llaves?
Algunos hechos:
1) La solución depende del número de personas (N) que consideremos.
2) No hay dos personas con exactamente las mismas llaves. Ya que si en un grupo de tres hay dos que tienen el mismo conjunto de llaves, se podría prescindir de uno de ellos y así abrir el cofre entre dos personas.
3) Como entre dos personas no pueden abrir el cofre, se deduce que a cualquier pareja que se forme le faltará por lo menos 1 llave.
4) A dos parejas distintas no les puede faltar la misma llave, ya que si así lo fuera, se podrían tomar 3 personas de esas parejas y les faltaría por lo menos 1 llave.
5) Como con N personas se pueden formar N(N-1)/2 parejas, y a cada pareja le falta una llave distinta, se necesitan al menos N(N-1)/2 llaves.
6) Como cada persona puede formar N-1 parejas, y cada pareja que forma le falta una llave. se tiene que cada persona recibe N(N-1)/2-(N-1)=(N-1)(N-2)/2 llaves.
A continuación se muestra como se obtiene la solución si se ocupan 4 personas.
Como son 4 personas se necesitan 6 llaves, sean A,B,C,D,E,F las llaves y 1,2,3,4 las personas. Formamos todas las parejas posibles e imponemos que les falte una llave, así por ejemplo a la pareja (1,2) les faltará la llave A, a la (1,3) la llave B, y así sucesivamente, con esto se obtendrán las llaves que sí podrá tener cada uno, y una solución posible se muestra a continuación.
1) DEF
2) BCE
3) ACE
4) ABD
Se observa que 2 personas no podrán abrir el cofre pero 3 sí. Además, si esta solución estuviera correcta, sería la solución mínima.
Otra teoria:
Supongamos que el cofre tiene cinco cerraduras. Si cada ciudadano tuviera tres llaves distintas, podría existir alguna reunión de dos ciudadanos que juntaran las cinco llaves necesarias, aunque no todos los pares de ciudadanos podrían abrir el cofre. Pero la condición es que ningún par de personas pueda acceder al contenido. Para garantizar que solamente tres personas tengan la posibilidad de abrir el cofre, cada una debe tener dos llaves.
Ahora bien, ¿cuántos conjuntos distintos de dos llaves cada uno pueden formarse desde un conjunto de cinco llaves? La respuesta es diez. Numeremos las llaves del 1 al 5. Los conjuntos de dos llaves son:
{1, 2} – {1, 3} – {1, 4} – {1, 5} – {2, 3} – {2, 4} – {2, 5} – {3, 4} – {3, 5} – {4, 5}
También hay que preguntarse cuántos conjuntos distintos de tres personas se pueden formar a partir de diez. La respuesta es factorial de diez dividido por factorial de 10 – 3, dividido por factorial de 3; o sea, 120 conjuntos de tres personas. Si a cada persona se le da dos llaves, necesitaremos 20 llaves, cuatro de cada una. Pero solamente 30 de los 120 conjuntos consiguen las cinco llaves necesarias para abrir el cofre, noventa reuniones de tríos de esas diez personas no podrán acceder al contenido del mismo. Para simplificar las cosas, estableceremos una correspondencia biunívoca entre cada conjunto de dos llaves y una persona, de manera que identificaremos a cada persona con su conjunto de llaves. He aquí la lista de las treinta reuniones que abren el cofre:
01 - {1, 2} U {1, 3} U {4, 5}
02 - {1, 2} U {1, 4} U {3, 5}
03 - {1, 2} U {1, 5} U {3, 4}
04 - {1, 2} U {2, 3} U {4, 5}
05 - {1, 2} U {2, 4} U {3, 5}
06 - {1, 2} U {2, 5} U {3, 4}
07 - {1, 2} U {3, 4} U {3, 5}
08 - {1, 2} U {3, 4} U {4, 5}
09 - {1, 2} U {3, 5} U {4, 5}
10 - {1, 3} U {1, 4} U {2, 5}
11 - {1, 3} U {1, 5} U {2, 4}
12 - {1, 3} U {2, 3} U {4, 5}
13 - {1, 3} U {2, 4} U {2, 5}
14 - {1, 3} U {2, 4} U {3, 5}
15 - {1, 3} U {2, 4} U {4, 5}
16 - {1, 3} U {2, 5} U {3, 4}
17 - {1, 3} U {2, 5} U {4, 5}
18 - {1, 4} U {1, 5} U {2, 3}
19 - {1, 4} U {2, 3} U {2, 5}
20 - {1, 4} U {2, 3} U {3, 5}
21 - {1, 4} U {2, 3} U {4, 5}
22 - {1, 4} U {2, 4} U {3, 5}
23 - {1, 4} U {2, 5} U {3, 4}
24 - {1, 4} U {2, 5} U {3, 5}
25 - {1, 5} U {2, 3} U {2, 4}
26 - {1, 5} U {2, 3} U {3, 4}
27 - {1, 5} U {2, 3} U {4, 5}
28 - {1, 5} U {2, 4} U {3, 4}
29 - {1, 5} U {2, 4} U {3, 5}
30 - {1, 5} U {2, 5} U {3, 4}
Si reunimos diez personas en conjuntos de tres al azar y cada una de ellas tiene un juego de dos llaves, la probabilidad de abrir el cofre es 0,25.
Supongamos, ahora, que el cofre tiene 4 llaves. Si damos 2 llaves a cada persona, habrá alguna reunión de dos personas que pueda abrir el cofre. Si cada persona tiene una llave, tres no podrán cumplir lo pedido.
Si el cofre tiene tres cerraduras, hay tres llaves, tres personas y se le da una llave a cada una, podrá cumplirse con lo pedido. Pero no tiene mucho sentido hablar de una reunión de tres personas al azar, si solamente hay tres personas. Para cada caso analizado, el aumento de gente disminuye la posibilidad de que tres puedan abrir el cofre.
Parece, si no hay error u omisión, que existe una única solución trivial de un arca con tres cerraduras, tres llaves y tres personas depositarias de una llave cada una.
Wuau .... me cansé....
Profesora MFV
Suerte!!
2007-12-27 07:17:51
·
answer #5
·
answered by Fernanda 6
·
1⤊
0⤋