La caja fuerte (animale)

[Machinegun]

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.

[Machinegun]

Re: La caja fuerte (animale)

No sé si la respuesta que propongo sea la mejor. Tal vez haya algún error en mi razonamiento, porque me resultan demasiadas cerraduras y demasiadas llaves. Es decir, no sería practicable en la vida real, pero veamos el desarrollo.

Si fueran 4 personas y quisieran que sólo pudieran abrir la caja cuando haya mayoría más 1, se necesitarían 6 cerraduras, dos copias de cada llave y se le darían 3 llaves a cada persona. Este resultado se puede obtener al tanteo porque se trata de pocas personas. Así, podemos distribuir las llaves de la siguiente manera:

A: 4, 5, 6
B: 2, 3, 6
C: 1, 3, 5
D: 1, 2, 4

De tal manera que cualesquiera dos de ellos que se juntaran serían incapaces de abrir la caja, mientras que cualesquiera tres la podrían abrir en todos los casos. Para 4 personas es fácil, para 5 ya se empieza a complicar, a menos que tengamos un método. Ahora bien, ¿cómo podemos saber cuántas cerraduras necesitamos y cuántas llaves de cada una de ellas, si tenemos un grupo de 12 personas y queremos que ningún equipo de 6 personas pueda abrir la caja juntando sus llaves, y 7 personas puedan siempre? Vamos a necesitar 924 cerraduras porque hay 924 posibles equipos de 6 personas que se pueden formar de un grupo de 12 personas. Cada uno de estos equipos va a tener las llaves de todas las cerraduras excepto de una. Si los numeráramos tendríamos que al equipo 1 le faltaría la llave de la cerradura 1, al 2 la de la 2 y así sucesivamente. Para saber cuántas llaves de cada cerradura necesitamos, debemos evitar que pueda darse el caso de que lleguen 7 personas y falte la llave de alguna cerradura, es decir que si tuviéramos 5 llaves por cerradura podría darse el caso de que exactamente los 5 que no están tengan la 5 únicas llaves de una cerradura determinada; por lo tanto debemos hacer 6 llaves de cada cerradura. Tenemos 924 cerraduras con 6 llaves de cada una, es decir, 5544 llaves en total. ¿Cómo las distribuimos entre las 12 personas? Esta pregunta tiene dos respuestas: una muy sencilla (dividiendo 5544 entre 12) y la otra no tan sencilla: tenemos que darle a cada quien una llave por cada uno de los equipos de 6 personas a los que no pertenece. Ya sabemos que el total de equipos de 6 personas es 924; ahora, de ésos, ¿a cuántos no pertenece cada una de las 12 personas? La respuesta es 462 (las combinaciones de 11 personas tomadas de 6 en 6). ¿Por qué se necesita una llave por cada equipo al que no pertenezca cada una de las12 personas? Para asegurarnos que por cada equipo de 6 personas, cualquiera de las 6 restantes tiene la llave que le falta a ese equipo. Afortunadamente, la respuesta sencilla y la no tan sencilla coinciden: 462 llaves tendrá que cargar cada quien para que sea seguro que 7 cualesquiera personas abrirán la caja fuerte mientras que 6 cualesquiera no podrán, ni yendo a bailar a Chalma. Si alguien tiene una respuesta menos complicada, agradeceré que me la haga saber.

Saludos

[Trollindor]

Re: La caja fuerte (animale)

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.

Si no estoy olvidando algo fundamental, ese «al menos» le quita toda la chicha al problema

Veamos qué pasa si instalamos en la caja un número de cerraduras igual a la mitad del de señores más uno. Hagamos dos llaves de todas las cerraduras menos de dos y entreguemos una llave de todas ésas a cada señor: como se necesita un número de llaves igual a la mitad del número de señores más uno, se satisface la condición de que la apertura requiera al menos la presencia de la mitad de los señores más uno.

Ahora veamos qué pasa si intentamos una solución con un número menor de llaves. De cada cerradura debe haber al menos una llave en poder de al menos un señor. Eso implica que debe haber algún conjunto de, como mucho, un número de señores igual al de cerraduras, capaces de abrir la caja por sí solos, y, como ese número es menor que la mitad del de señores más uno, la condición del enunciado no se satisface. Luego es trivial que la solución, en los términos planteados —con el número mínimo posible de cerraduras— es un número de cerraduras igual a la mitad del de señores más uno, dos llaves de todas las cerraduras menos de dos y una llave de cada una de las otras dos, entregando cada una de todas esas llaves a un señor.

Ahora, si se exige que la caja se pueda abrir estando presente cualquier conjunto de la mitad de los señores más uno, y nunca con menos, ya es otra historia

A ver si se me ocurre algo...

[Machinegun]

Re: La caja fuerte (animale)

Ahora, si se exige que la caja se pueda abrir estando presente cualquier conjunto de la mitad de los señores más uno, y nunca con menos, ya es otra historia

Bien, ojalá que no se exija, porque eso de tener 924 cerraduras no es como que muy práctico. Pero si no se exige, entonces yo le pondría 7 cerraduras y sólo le entregaría una llave a cada uno de los 7 señores que se encargarán de abrir la caja. Si numeramos a los señores, le daría una llave a los que tengan los números, 1, 2, 3, 4, 5, 6 y 7, de tal manera que cada vez que se va a abrir la caja, siempre tuvieran que estar presentes al menos esos 7 señores. Lo señores 8, 9, 10, 11 y 12 podrían estar o no. En ese caso sólo necesitaría una llave por cerradura.

Saludos

[ser humano]

Re: La caja fuerte (animale)

No, no creo que lo exija, sino el enunciado seria contradictorio. Supongamos que pide que cualquier grupo de siete personas de los doce pueda abrir la caja que tiene $n$ cerraduras. Si es asi, tomamos un grupo cualquiera de siete y entre todos ellos tienen las $n$ llaves necesarias. Pero como el enunciado pediria un grupo cualquiera, entonces podriamos cambiar a un individuo del grupo que tomamos al principio (que llamare A) por otro que habia quedado en los 5 restantes (que llamare B). Este nuevo grupo de 7 personas, segun lo pedido en el enunciado, tambien deberia tener todas las llaves. Hay que notar que como seis personas no deben juntar todas las llaves necesarias, A debe tener una llave o mas que el resto no tiene. Esta llave (o llaves), para que el nuevo grupo tenga las llaves necesarias, tambien la debe tener B.
Un razonamiento analogo se puede aplicar con el resto de los seis integrantes del grupo inicial, notando que se deberia poder cambiar a cada uno de ellos por el mismo B.
De esta manera se puede notar que si cualquier grupo de 7 personas junta las llaves necesarias, B tiene todas las llaves. Esto contradice claramente al enunciado.
Espero haber sido claro, en todo caso me dicen

Saludos

[Machinegun]

Re: La caja fuerte (animale)

Hola, ser humano. No sé si los demás, pero yo no entiendo lo de la contradicción de la que hablas. Te propongo que veamos el caso de que en lugar de ser 12 sean 6 las personas totales (con 12 sería engorroso, pero la lógica es la misma). Si 6 personas desean que cualquier grupo de tres personas no pueda abrir la caja, pero cualquier grupo de 4 pueda siempre, entonces la caja tendría 20 cerraduras con tres copias de cada una. Las 60 llaves se distribuirían de la siguiente manera:

Así, cualquier grupo de 3 personas estaría imposibilitado de abrir la caja porque le faltaría 1 llave, la cual estaría en poder de cualquiera de las 3 personas restantes. Por lo tanto, cualquier grupo de 4 personas, juntaría siempre las llaves necesarias para abrir la caja. Si quieres puedes tratar de encontrar un grupo de tres (de los 20 posibles) que junte las 20 llaves o un grupo de 4 (de los 15 posibles) que no las junte y verás que no hay ninguna contradicción en el planteamiento.

Saludos cordiales

[ser humano]

Re: La caja fuerte (animale)

Hola nuevamente, volvere a exponer lo que planteaba de diferente manera.
Lamemos a los integrantes del grupo : A, B, C, D, E, F, G, H, I, J, K, L.
Si cualquier grupo de 7 integrantes de estos tiene que poder abrir la caja fuerte, entonces el grupo A B C D E F G lo puede hacer.
Pero como cualquier grupo lo puede hacer, entonces el grupo H B C D E F G tambien lo puede hacer.
Hay que notar que cada integrante del primer grupo ( A B C D E F G ) tiene llaves necesarias para abrir la caja que no posee el resto de integrantes del mismo gurpo, ya que si el resto las tendria (o la tendria, en el caso de ser unica), ese resto podria abrir la caja, cosa que no puede suceder porque son 6 y no 7.
En particular, A tiene llaves que no poseen ninguno de ellos: B C D E F G. Como ya se dijo, el grupo H B C D E F G tambien debe poder abrir la caja, por lo tanto, deben reunir todas las llaves. Esto implica que las llaves necesarias que tenia A, como no las tenian ni B, ni C, ni D, ni E, ni F, ni G, las tiene que tener H .
Pero el grupo A H C D E F , tambien debe poder abrir la caja, ya que son 7. Como deben tener todas las llaves necesarias, H debe tener todas las llaves necesarias que poseia B, pero que no poseia el resto.

Hasta aca podemos concluir que H tiene las llaves de A y de B. Procediendo de la misma manera con el resto de integrantes, se puede llegar a la conclusion de que H deberia tener todas las llaves necesarias para abrir la caja, lo que contradice las condiciones iniciales.

Espero que esta vez lo haya expuesto de forma mas entendible.

Saludos

[ser humano]

Re: La caja fuerte (animale)

Gracias por el ejemplo, me hiciste notar donde estaba el error de mi razonamiento. El problema en lo que yo decia estaba en que A (por ejemplo) compartia llaves con otro integrante del primer grupo, pero estas llaves no las posee H, por lo que el grupo con H tendria todas las llaves, pero el mismo H careceria de estas (por lo que este ya no podria abrir la caja solo).

Saludos

[carroza]

Re: La caja fuerte (animale)

Hola, Machinegun.

Gracias por un bonito problema, que me ha amenizado un largo viaje.

Tengo un contraejemplo, para el caso de 6 personas, tales que ningun grupo de 3 abre la cerradura, pero cualquier grupo de 4 lo abre. Lo hago con 12 llaves.

No estoy seguro que este sea el numero minimo.
Tengo un procedimiento general para determinar, en un grupo de n personas, cuantas llaves son necesarias para que n-1 personas cualesquiera si abran la caja y n-2 no la puedan abrir. Salen n(n-1)/2.

A partir de este caso, determino el caso de n=6, para que 5 personas abran y 4 no.
Salen 15 llaves. De aqui, quito 3 llaves redundantes, para que 4 abran y 3 no.

Imagino que un procedimiento similar puede aplicarse a las 12 personas.


Saludos

[Machinegun]

Re: La caja fuerte (animale)

Hola, carroza, gusto verte por aquí. No entiendo muy bien cómo logras con 12 llaves que 3 cualesquiera personas no abran la caja y 4 siempre la puedan abrir. Tal vez si me dijeras cómo distribuirías las 12 llaves entre los seis integrantes, quizá con una tablita. Gracias.

Saludos

[ser humano]

Re: La caja fuerte (animale)

Estoy intentando resolver el problema para una cantidad indeterminada de personas con teoria de conjuntos. Si llego a algo, lo expongo

[Machinegun]

Re: La caja fuerte (animale)

Hola, carroza, nuevamente. En mi torpeza no me fijé que ya habías puesto la tablita, pensé que era la mía y que sólo la estabas citando, por eso no entendía tu mensaje. Ahora que le echo un ojo, me doy cuenta de que no es contraejemplo, pues de los 15 grupos posibles de 4 miembros, 12 no podrían abrir la caja, es decir, sólo 3 lo lograrían: ABCD, ABEF y CDEF. No pueden ser sólo dos llaves por cerradura porque entonces si esas dos llaves están en poder de los dos que no se presentan, una cerradura se quedará sin abrir.

Saludos

[carroza]

Re: La caja fuerte (animale)

Hola, Machinegan.

Tienes toda la razón. Me he precipitado.

Mi solución para que, de 6 personas, 5 abran y cuatro no es:


A: 1, 2, 3, 4, 5
B: 1, 5, 6, 7, 8
C: 2, 5, 9, 10. 11
D: 3, 6, 9, 12, 13
E: 4, 7, 10, 12, 15
F: 5, 8, 11, 13, 15



Pensé que quitando las llaves 1, 9 y 15 lograba que los grupos de 4 personas abrieran, y los de 3 no, pero me equivoqué.


Es probable que tengas razón, y que la solución general para que m+1 personas abran la caja y m no, en un grupo de n personas, sea tener un numero de llaves y cerraduras igual al numero de grupos de m personas que pueden hacerse a partir de n, o sea,
n sobre m.

[Machinegun]

Re: La caja fuerte (animale)

Hola, Machinegan.

Tienes toda la razón. Me he precipitado.

Mi solución para que, de 6 personas, 5 abran y cuatro no es:


A: 1, 2, 3, 4, 5
B: 1, 5, 6, 7, 8
C: 2, 5, 9, 10. 11
D: 3, 6, 9, 12, 13
E: 4, 7, 10, 12, 15
F: 5, 8, 11, 13, 15



Pensé que quitando las llaves 1, 9 y 15 lograba que los grupos de 4 personas abrieran, y los de 3 no, pero me equivoqué.

Sólo encontré un error menor en tu distribución de llaves: tienes 4 copias de la cerradura 5 y ninguna de la 14, lo cual imposibilitaría que se abriera la caja ni siquiera estando los 6 integrantes, pero eso se arregla cambiando los 5 por 14 en los integrantes B y C.

Es probable que tengas razón, y que la solución general para que m+1 personas abran la caja y m no, en un grupo de n personas, sea tener un numero de llaves y cerraduras igual al numero de grupos de m personas que pueden hacerse a partir de n, o sea,
n sobre m.

En cuanto al número mínimo de cerraduras, estoy de acuerdo, pero el número mínimo de llaves por cerradura se obtiene de n – m, pues si hicieras una menos podría darse el caso de que n – m – 1 personas tuvieran las únicas copias de alguna cerradura, por lo que m + 1 personas no tendrían ninguna copia de esa cerradura y por lo tanto no podrían abrir la caja. Por ejemplo, si quisieras que de 6 socios se necesitaran cualesquiera 2 para abrir la caja, pero que ninguno pudiera abrirla solo, necesitarías 6 cerraduras y 5 copias por cada una. Si hicieras menos copias, por ejemplo 4, entonces los 2 socios que no tienen las 2 copias de alguna cerradura no podrían abrir la caja. Como en el ejemplo que pones de que sólo 5 puedan abrir la caja, en este también habría que darle 5 llaves a cada socio (cada uno podría abrir todas las cerraduras menos una).

Saludos

[carroza]

Re: La caja fuerte (animale)

Hola.

Gracias de nuevo, machinegun, por encontrar mi errata. Vamos a poner la solución bien:
Mi solución para que, de 6 personas, 5 abran y cuatro no, es:


A: 1, 2, 3, 4, 5
B: 1, 6, 7, 8, 9
C: 2, 6, 10, 11, 12
D: 3, 7, 10, 13, 14
E: 4, 8, 11, 13, 15
F: 5, 9, 12, 14, 15



Es también curioso el significado geométrico de estas soluciones.

Si tomas el caso de 4 personas, con 6 llaves, para

A: 4, 5, 6
B: 2, 3, 6
C: 1, 3, 5
D: 1, 2, 4

Las llaves (vértices) forman un octaedro, y cada personas tiene tres llaves, que forman 4 triángulos que cada uno comparten un vértice común con los otros.


En el caso de 6 personas, 20 llaves, las llaves (vértices) forman un dodecaedro, y a cada persona corresponden 10 llaves que forman dos pentágonos opuestos.