Label Cloud

jueves, 26 de noviembre de 2009

Combinatoria

.



por Adrián Paenza





Suponga que usted tiene un reproductor de CD que viene con un botón que permite “programar” el orden en el que va a escuchar las canciones. Es decir, en lugar de reproducirlas tal como vienen grabadas originalmente, las reproduce en el orden que usted elige, hasta agotarlas todas. Por ejemplo, supongamos que usted inserta un CD con 10 canciones. Usted podría seleccionar:

3-7-10-1-9-5-8-6-4-2

o

10-9-8-7-6-5-4-3-2-1,

por poner sólo dos casos.

Ahora, planteo un problema: si a usted le gusta mucho su CD y decidiera programar un “ordenamiento” diferente por día, hasta agotar todos los posibles “órdenes”, ¿cuántos días tardaría en recorrerlos todos? Es decir, ¿cuántos días tendrán que pasar hasta que a usted no le quede más remedio que repetir alguno anterior?
Antes de escribir la solución, lo invito a que pensemos algo juntos. Si usted tuviera los números 1, 2 y 3, ¿de cuántas formas los puede ordenar? Piense una manera de “contar” sin necesidad de escribir todas las formas. Es que si hay que hacer una lista, yo la hago. Es ésta:

123, 132, 213, 231, 312, 321 (*)

O sea, uno descubre que son seis formas. Pero esto es muy fácil, porque son pocos números. Si usted tuviera diez números o veinte (por poner un ejemplo), se haría mucho más tedioso escribir todos los casos y lo más probable es que uno termine equivocándose porque son muchas las posibilidades a considerar. No. La idea es buscar alguna forma que permita contar sin tener que hacer una lista.
Por ejemplo, aprovechando los datos que acabo de escribir en (*) pensemos juntos cómo hacer si hubiera cuatro números en lugar de tres.
El número 4 lo podríamos poner delante de los seis elementos de la lista (*). Tendríamos entonces esta nueva lista

4123, 4132, 4213, 4231, 4312 y 4321

Lo único que hice fue agregar el número 4 al principio de cada integrante de la lista (*). Vuelvo a tener 6 formas. Esto no agota todas las posibilidades. Lo que tenemos que hacer ahora es intercalar al número 4 en el segundo lugar de cada integrante de la lista (*). En ese caso, queda:

1423, 1432, 2413, 2431, 3412 y 3421.

O sea, otras seis formas. Creo que usted ya se da cuenta de lo que hay que seguir haciendo (si no, piénselo sola/o hasta advertir cómo seguir). Ahora, intercalemos el número 4 en la tercera posición de la lista (*). Se tiene entonces la siguiente lista:

1243, 1342, 2143, 2341, 3142 y 3241.

Y por último, ubicamos al número 4 al final de todos los miembros de la lista (*):

1234, 1324, 2134, 2314, 3124 y 3214.

Y se terminó. Es decir, hemos agotado todas las posibilidades. Al número 4 lo ubicamos en todos los lugares y, como vimos, se trató de reproducir la lista original (*) cuatro veces. Y, como había en total seis elementos en la lista (*), al multiplicarlo por cuatro tenemos 24 posibilidades.

4123, 4132, 4213, 4231, 4312 y 4321
1423, 1432, 2413, 2431, 3412 y 3421 (**)
1243, 1342, 2143, 2341, 3142 y 3241
1234, 1324, 2134, 2314, 3124 y 3214

Si ahora apareciera un quinto número, lo que habría que hacer es intercalar el número 5 en todas las posiciones de la lista (**), por lo que obtendríamos 5 veces la lista de 24 que ya teníamos. O sea, 24 x 5 = 120 maneras.

Si ahora uno tiene en cuenta que con 3 números había 3 x 2 = 6 formas,

con 4 números, hay 4 x 3 x 2 = 24 formas,

con 5 números, hay 5 x 4 x 3 x 2 = 120 formas, etc., uno puede inferir que con 10 números habrá:

10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 = 3.628.800 formas.

Visto de esta manera, ¿le ayuda esto a resolver el problema original? Es decir, ¿el problema del “reproductor de CD”?

Uno puede pensar que cada canción en el CD tiene un número (que es el número con el que fue grabada y figura en la “solapa”) y por lo tanto se trataba de buscar “todos los posibles órdenes” de reproducir las canciones.

Lo que acabamos de ver es que, con el mismo “modelo”, las distintas formas de escuchar las canciones son en total: 3.628.800. Eso significa que tardará 3.628.800 días hasta volver a escucharlas de nuevo en el mismo orden. Lo que implica (dividiendo este número por 365 para calcular cuántos años tienen que pasar) que uno tendrá que esperar más de ¡9941 años! hasta volver al orden inicial.

Más allá de las cuentas, lo interesante es el “modelo” que sirve para “contar” todos los posibles casos sin tener que hacer una lista. Haber pensado este problema permite resolver muchísimos otros de características parecidas.

Un par de observaciones finales:

a) La rama de la matemática que se dedica a “contar” (sin tener que “listar”) se llama “combinatoria”. Los problemas de combinatoria son preciosos y no necesariamente muy sencillos. Hay gente que tiene facilidad para “imaginar” formas para “contar” que son verdaderamente ingeniosas.
b) Tomar un número cualquiera, digamos el 4, y hacer el siguiente cálculo:

4 x 3 x 2 x 1 = 24 , se escribe 4! , y se lee “4 factorial” o “el factorial de 4”.

Hacer 5! = 5 x 4 x 3 x 2 x 1 = 120

De hecho, el resultado del problema planteado (o sea, de las posibles formas de escuchar las 10 canciones) es entonces “10!” , o sea, el factorial de diez.
A manera de ejemplo que sugiere cuán “grande” se hace el “factorial de un número” aun para números pequeños, fíjese en esta lista:

2! = 2 (factorial de 2 es igual a 2)

4! = 24 = 4 x 3 x 2 (factorial de 4, es igual a 24)

5! = 120 = 5 x 4 x 3 x 2 (factorial de 5, es igual a 120)

7! = 5040 = 7 x 6 x 5 x 4 x 3 x 2 (factorial de 7, es igual a 5040)

10! = 3.628.800 = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2

15! = 1.307.674.368.000

Una reflexión sobre este último número “15!”. Fíjese que si uno tuviera 15 libros en el estante de una biblioteca y se preguntara ¿de cuántas formas los puedo ordenar? (una pregunta “inocente” si se quiere), tiene como respuesta “más de un billón de posibilidades”.

Y por último, si uno calcula

20! = 2.432.902.008.176.640.000
descubre que ésta sería la respuesta a preguntarse de cuántas maneras pueden terminar ubicados los 20 equipos de fútbol que participan en el torneo de la AFA: más de ¡2 trillones! Y aún así ganó Estudiantes.



Diario Página12 2/1/2009




.

0 comentarios: