miércoles, 4 de abril de 2007

Mago busca puerta

Enunciado

Primera solución (tanteo)

Fíjate que 2 no pueden abrir, pero 3, los juntemos como los juntemos, sí pueden abrir la puerta.

Tres cerraduras

Es evidente que más de 3 cerraduras sí necesitará, ya que con sólo 3, no tendría para repartir a los cuatro, por tanto uno no tendría llave, y si ése y 2 más pueden abrir, los otros dos pueden abrir solos.

Cuatro cerraduras

Al menos necesita 4, veamos que con 4 no puede cumplir las condiciones.

No puede haber ninguno con 3 llaves, pues en cuanto lo juntases con uno más que tuviese la restante, abriría.

Uno de ellos tendría que tener 2 (si no, tres no podrían abrir la puerta, al faltarles una llave). Llamémosle A. Los otros tres (B, C y D) deben poder abrir la puerta, luego tienen 4 llaves, por eso hay otro (supongamos que B) que tiene 2 llaves. A y B deben tener una llave en común, porque en caso contrario, abrirían la puerta entre los 2. Tampoco pueden tener repetidas las dos llaves, porque en ese caso, ellos dos y otro abrirían la puerta, y si se fuese uno de los dos, tendrían las mismas llaves. Luego entre los dos tienen tres llaves. La cuarta la tienen los otros dos, puesto que cualquiera de ellos con A y B deben de poder abrir. Claro, que si juntas C y D con A, pueden abrir, luego C o D tienen la llave que le falta a A y tiene B, y también la que les falta a ambos, por lo que entre ése y A tendrían las cuatro llaves.

Cinco cerraduras

Con cinco cerraduras el proceso es aún más complejo, pero lo cierto es que tampoco se puede hacer. Veamos.

Ninguno puede tener tres llaves. Si uno (llamémosle A) tuviese tres, y uno tuviese las dos restantes, podrían abrir la puerta entre dos. Luego los otros tres sólo podrían tener una de las dos que le faltan a A. Pero como son 3, dos de ellos la tienen repetida (supongamos que son B y C). Cuando juntemos a A, B y C tienen que tener todas las llaves, lo cual es absurdo.

Es decir, que como mucho tendrían que tener dos llaves. Además, es sencillo entender que al menos hay dos que tienen dos llaves, porque en caso contrario no podrían juntar 5.

Tomemos dos de los que tienen dos llaves (A y B). No pueden tenerlas iguales, ya que al juntar un tercero, no dispondrían de 5 llaves.

Si dos de ellos tienen una llave igual, entre ambos tienen 3 llaves, luego al añadir cualquiera de los otros dos (C o D) han de juntar 5 llaves, por lo que las dos llaves que tuviesen habrían de ser las dos que le faltan, y por tanto C y D tendrían el par de llaves igual, lo que hemos visto que no puede ser.

Si no tienen ninguna repetida, entre los dos tienen 4 llaves. Los otros dos tienen la llave que falta, pues entre 3 deberían abrir la puerta. Claro, que si juntamos A con los otros dos, también abrimos, por lo que entre C y D tienen las llaves que tiene B, repartidas, porque no pueden tener 3. Y si tomamos B, C y D, también tienen entre C y D las que tiene A, por la misma razón. No puede ser, pues siguen teniendo el límite de dos llaves.

Seis cerraduras

Nos acercamos a la respuesta.

Supongamos que ninguno tiene tres llaves. Evidentemente, todos tienen que tener dos, pues al juntar tres debemos poder abrir 6 cerraduras. Evidentemente, A y B tienen cuatro llaves y C tiene las dos restantes, pero si juntamos A, B y D, obtenemos que C y D tienen las mismas, y, claro, B, C y D no pueden abrir la puerta.

Está claro que al menos alguno tiene tres llaves. ¿Podría alguno tener cuatro llaves? Si A tiene cuatro llaves, ninguno de los otros puede tener las dos restantes, de forma que, por ejemplo, B tiene una y C otra. Pero si juntamos A, B y D, D debe tener la misma que tenía C antes, y si junto A, C y D, alguno debe tener la que tenía B, siendo que en cuanto la tuviera, se podría juntar con A y abrir la puerta.

Bueno, el caso es que, si el sistema funciona, el que más llaves tiene, dispone de 3. Supongamos que sea A y llamemos a las llaves Amarilla, Roja y Verde. Entre A, B y C abren la puerta, así que uno entre B y C debe tener dos llaves de las restantes y el otro al menos una. Supongamos que B tiene la Azul y la Negra, y que C tiene la Blanca. Juntando a A, B y D concluimos que D también tiene la Blanca. Claro, que si juntamos a A, C y D, sabemos que entre C y D tienen la Azul y la Negra, pero no pueden tenerlas a la vez. Pongamos que C tiene la Azul y D la Negra. Sólo nos queda juntar a B, C y D, y les faltrían las tres llaves que tiene A (Amarilla, Roja y Verde), sin acumular más de una cada uno (recuerda que ya tienen dos, y no pueden llegar a cuatro). Como son tres, pueden tener una cada uno.

Luego el reparto podría funcionar así: A, Amarilla, Roja y Verde, B, Amarilla, Azul y Negra, C, Roja, Blanca y Azul, y D, Verde, Blanca y Negra.

Comprobemos que las cuatro diferentes combinaciones de tres trolls (A, B, C), (A, B, D), (A, C, D) y (B, C, D) disponen de las seis llaves (tres de ellas, repetidas).

Por otra parte, respecto a los pares de trolls, a (A, B) le falta la llave Blanca, a (A, C) le falta la llave Negra, a (A, D) le falta la llave Azul, a (B, C) le falta la llave Verde, a (B, D) le falta la llave Roja, y a (C, D) le falta la Amarilla. Por cierto, son seis las parejas, y seis las cerraduras. Tal vez razonando por aquí hubiese salido antes, aunque habría que demostrar que es imposible hacerlo con menos cerraduras.

Por tanto, con seis cerraduras y dos copias de cada llave, puede cumplir sus deseos el mago, y guardar en su cámara lo que le quede después de pagar al cerrajero, y a nosotros por esta deducción.

Otra solución (más breve)

Como hemos visto, se pueden hacer exactamente seis pares de trolls con los cuatro disponibles, que serían (A, B), (A, C), (A, D), (B, C), (B, D) y (C, D). A todos ellos les debe faltar al menos una llave. Esa llave, la tienen que tener todos los que no pertenezcan al par, pues al unirse, podrían abrir la puerta. A dos pares distintos (en los que hay al menos un troll diferente) no puede faltarles la misma llave, ya que el de un par que no pertenezca al otro debe tener todas las llaves que le falten al otro par. Economizando al máximo, podemos escoger una llave por cada par, que debe llevar cada troll que no pertenezca al par (es decir, habría que hacer dos copias). Supongamos que a (A, B) le asociamos la llave 1, a (A, C) le asociamos la llave 2, a (A, D) le asociamos la llave 3, a (B, C) le asociamos la llave 4, a (B, D) le asociamos la llave 5 y a (C, D) le asociamos la llave 6.

De esta forma, A tendría las llaves (4, 5, 6), B tendría las llaves (2, 3, 6), C tendría las llaves (1, 3, 5) y D tendría las llaves (1, 2, 4). Es sencillo comprobar que esto equivale al reparto hecho en la solución anterior, y por tanto es una solución válida y es la que menos cerraduras (y llaves) usa.