Llaves

abril 20, 2007

Hay n cajas, cada una con un candado cada uno de los cuales tiene una llave. Sabemos que alguien puso una llave en cada caja y las cerro todas (con candado). ¿Cual es la probabilidad de que rompiendo los primeros k candados logremos abrir todas las cajas?

Notacion:

Lo primero que hacemos es dar una forma de notar la distribucion de las llaves. Veamos en un ejemplo, supongamos que las cajas 1,2,3,4,5,6,7 tienen las llaves 4,5,2,7,6,3,1 respectivamente (la llave r es la de la caja r). Entonces:

La caja 1 tiene la llave de la caja 4 que a su vez tiene la llave de la caja 7 que a su vez tiene la llave de la caja 1. La caja 2 tiene la llave de la caja 5 que a su vez tiene la llave de la caja 6 que tiene la llave de la caja 3 que tiene la llave de la caja 2. Vamos a notar la distribucion como (147)(2563).

Otro ejemplo, si las cajas 1,2,3,4,5,6,7 tiene las llaves 4,5,7,1,2,3,6. Entonces notamos (14)(25)(376).

A (147),(2563),(14),(25),(376) vamos a llamarlos ciclos. Nuestra notacion todavia no es del todo buena porque si borramos los parentesis de (147)(2563) no tenemos forma de saber cuales eran los ciclos (por ejemplo si tenemos 1472563, no sabemos si viene de (147)(2563) o de (1472)(563)).

Vamos a hacer lo siguiente:

1) Por ejemplo (4726)=(7264)=(2647)=(6472), elegimos entonces escribir siempre los ciclos con su elemento mas chico adelante de todo, por ejemplo el anterior lo notamos como (2647) porque el 2 es el numerito mas chico en el ciclo.

2) Ahora tenemos que elegir en que orden poner los ciclos (pues por ejemplo (147)(2563)=(2563)(147)). Lo que hacemos es ordenar los ciclos de forma que sus primeros elementos vayan de mayor a menor. Es decir que en el ejemplo anterior deberiamos elegir (2563)(147), ya que 2>1.

Veamos un ejemplo, si las cajas 1,2,3,4,5,6,7,8,9 tienen las llaves 3,9,5,8,1,7,2,4,6 entonces los ciclos son (135)(2967)(48) que se nota como (48)(2967)(135).

Ahora nuestra notacion es mejor porque podemos borrar los parentesis, es decir que podriamos escribir directamente 482967135. ¿Como hacer para saber cuales eran los ciclos? facil… el ultimo ciclo debe empezar en 1 entonces debe ser (135), queda 482967. Entre los seis numeros que quedan el mas chico es el 2 entonces el ultimo ciclo debe empezar en 2, debe ser (2967). Entonces queda 48, entre los numeros que quedan el mas chico es el 4 entonces el ciclo mas a la derecha que queda debe ser (48), como no quedan mas numeros terminamos y queda (48)(2967)(135).

Otro ejemplo 754829136. El ultimo ciclo debe empezar en 1 entonces debe ser (136). Queda 754829, entre los numeros que quedan el mas chico es el 2 entonces el ciclo mas a la derecha debe comenzar en 2, entonces debe ser (29), queda 7548. Entre los numeros que quedan el mas chico es el 4 entonces el ciclo mas a la derecha debe ser (48) queda 75. Entre los que quedan el mas chico es el 5 entonces el ciclo siguiente sera (5), queda solo el 7 que forma otro ciclo (7). Entonces 754829136 venia de (7)(5)(48)(29)(136), es decir que las cajas 1,2,3,4,5,6,7,8,9 tenian las llaves 3,9,6,8,5,1,7,4,2 respectivamente.

Vamos a llamar a la notacion anterior el codigo de la distribucion, o sea si las cajas 1,2,3,4,5,6,7,8,9 tenian las llaves 3,9,6,8,5,1,7,4,2 respectivamente entonces el codigo de esa distribucion es 754829136. Lo que vimos es que dos distribuciones distintas tienen codigos distintos y es facil ver que cada permutacion de 1,2,...,n es el codigo de alguna distribucion. Lo que hemos hecho es entonces poner en biyeccion las posibles distribuciones de las llaves con las permutaciones de 1,2,....,n. ¿Que tiene todo esto que ver con el problema?

Solucion:

Es facil ver que si rompemos algunas cajas, vamos a poder abrir todas las cajas si y solo si rompemos al menos una caja en cada ciclo (pues con cada llave logramos abrir solamente las de su ciclo), entonces rompiendo las primeras k cajas vamos a poder abrir todas si y solo si todos los ciclos tienen al menos un numero entre 1 y k. Pero esto quiere decir que el menor numero de cada ciclo debe estar entre 1 y k o lo que es lo mismo, el mayor numero entre los numeros mas chicos de cada ciclo debe estar entre 1 y k. Pero este numero no es otro que el primer numero del codigo de la distribucion porque en cada ciclo escribimos el mas chico primero y ordenamos los ciclos de forma que los “primeros” vayan de mayor a menor. Por ejemplo a la distribucion con codigo 754829136 que es (7)(5)(48)(29)(136) no la vamos a poder abrir si rompemos las primeras 4 cajas (solo abriremos los ultimos tres ciclos). En ese caso precisamos romper las primeras 7 cajas (porque 7 es el primer numero del codigo).

En conclusion vamos a poder abrir todas las cajas si y solo si el primer numero del codigo de la distribucion esta entre 1 y k, entonces la probabilidad es k/n.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: