PROBLEMAS DE COMBINATORIA RESUELTOS.
Hay algunos con repetición...esos no van...pero si tienen ganas...pueden leerlos!!
Permutación
1) Se tienen 3 libros: uno de aritmética (A), uno de biología(B) y otro de cálculo(C), y se quiere ver de cuántas maneras se pueden ordenar en un estante.
En principio se puede elegir cualquiera de los 3 para colocar en primer lugar:
| 1a | 2a | 3a |
A
| ||
| B | ||
| C |
Se ve entonces que hasta ahora hay 3.2 maneras distintas de ordenar los libros. Pero una vez dispuestos las 2 primeros queda unívocamente determinado cuál debe ser el tercero.
O sea que el número total de maneras posibles de ordenar los 3 libros se puede calcular como: 3.2.1 = 6
Variación
2) Se tienen 7 libros y solo 3 espacios en una biblioteca, y se quiere calcular de cuántas maneras se pueden colocar 3 libros elegidos; entre los siete dados, suponiendo que no existan razones para preferir alguno.
En un principio se puede elegir cualquiera de los 7 libros para ubicarlo en
Primer lugar Después quedan 6 libros posibles para colocar en el segundo lugar y por último solo 5 libros para el tercer lugar.
Por lo tanto las distintas maneras en que se pueden llenar los 3 huecos de la
biblioteca es: 7.6.5 = 210
PERMUTACIONES CON REPETICIÓNSi se tienen n libros y tres lugares es: n.(n - 1).(n - 2)En general para n libros y k lugares resulta:n. (n-1). (n-2). ..... .[n- (k-1)]Con la fórmula: Vn,k = n!/(n-k)! ® V7,3=7!/(7-3)!=7.6.5.4!/4!=7.6.5
3) ¿Cuántas permutaciones pueden formarse con las letras de la palabra BONDAD?Hay 6!/2!Si se escribe en lugar de BONDAD: BONDAD’Todas las letras son distintas, luego hay 6! permutaciones, pero cada par de
permutaciones:
- - - D - D’
- - - D’- D
Coinciden, por lo tanto se tiene que dividir por 2 el número total de permutaciones
4) ¿De cuántas maneras se pueden ordenar las letras de la palabra AMASAS?
Si a la letras que se repiten se les coloca un subíndice se tiene
A 1M A 2 S 1 A 3 S2 y el número de permutaciones posibles es P6 = 6!
Que ocurre si sólo se cambian de posición las letras A?
A 1M A 2 S 1 A 3 S2 A 2M A 3 S 1 A 2 S2
A 1M A 3 S 1 A 2 S2 A 3M A 1S 1 A 2 S2
A 2M A 1 S 1 A 3 S2 A 3M A 2 S 1 A 1 S2
Se obtienen tantas maneras distintas de ordenar como permutaciones de 3
elementos (las 3 "A"), cuyo número es P3 = 3!
De manera similar si sólo se modifica la posición de la letra "S" se obtienenP2 = 2! maneras de ordenar diferentes.
Pero en cualquiera de los dos casos, siempre se sigue leyendo la misma palabra, es decir, que si se borran los subíndices, no se distingue diferencia alguna.
Se puede encontrar el número de permutaciones –P6 distinguibles o no – haciendo el producto de las distinguibles – que se indican 6 P 2,3 – por las no distinguibles P2 y P3 .
P6 = 6 P2,3 . P2. P3
De esta manera se puede encontrar el número de permutaciones distinguibles:
P6 / P2. P3
Combinación
5) Un hospital cuenta con 21 cirujanos con los cuales hay que formar ternas para realizar guardias. ¿Cuántas ternas se podrán formar?
Se trata de formar todas las ternas posibles, sin repetir elementos en cada una, y sin importar el orden de los elementos.
Si quisiéramos formar todas las ternas posibles, sin repetición de elementos en cada una, para elegir el primer elemento hay 21 posibilidades, para el segundo quedan 20 posibilidades, y para el tercero 19 posibilidades, por lo tanto el número de ternas posibles está dado por: 21* 20*19 = 7980
Pero en este caso cada terna aparece repetida en distinto orden, por ejemplo tendremos: ABC, ACB, BAC, CAB y CBA. Son seis ternas con los mismos elementos, que está dado por el factorial de 3.
Por lo tanto el total de ternas obtenido 7980, hay que dividirlo por 6
7980/6 = 1330
Se pueden organizar las guardias de 1330 maneras diferentes
Este es un problema de combinación. Si llamamos m al número de elementos del conjunto y n al número que integrará cada uno de los conjuntos que debemos formar, de modo que ls elementos de cada uno sean diferentes y no importa el orden, se tiene la fórmula:
Cm,n = m!/ (n!. (m-n)!)
Combinaciones con repetición
6)¿De cuántas maneras pueden entrar cuatro alumnos en tres aulas, si no se hace distinción de personas?
Si tomamos, por ejemplo que entran dos personas en el aula 1, una en el aula 2 y otra en el aula 3
Que escribimos: 1123
Pero también se puede dar la siguiente situación
Es decir 3121
Otra situación
O sea 3211
Al no haber distinción estas distribuciones de cuatro alumnos en tres aulas son la misma.
Otra distribución distinta es, por ejemplo 1113, que significa: tres alumnos entraron en el aula 1 y el cuarto en el aula 3.
De modo que las distribuciones posibles de 4 personas en tres aulas, son
C’3,4 = C3+4-1,4 = C6,4 = 6 . 5. 4. 3/(4. 3. 2. 1) = 15
7. Una comida gratis
Diez jóvenes decidieron celebrar la terminación de sus estudios en la escuela secundaria con un almuerzo en un restaurante. Una vez reunidos, se entabló entre ellos una discusión sobre el orden en que habían de sentarse a la mesa. Unos propusieron que la colocación fuera por orden alfabético; otros, con arreglo a la edad; otros, por los resultados de los exámenes; otros, por la estatura, etc. La discusión se prolongaba, la sopa se enfrió y nadie se sentaba a la mesa. Los reconcilió el camarero, dirigiéndoles las siguientes palabras:
- Jóvenes amigos, dejen de discutir. Siéntense a la mesa en cualquier orden y escúchenme
Todos se sentaron sin seguir un orden determinado. El camarero continuó:
- Que uno cualquiera anote el orden en que están sentados ahora. Mañana vienen a comer y se sientan en otro orden. Pasado mañana vienen de nuevo a comer y se sientan en orden distinto, y así sucesivamente hasta que hayan probado todas las combinaciones posibles. Cuando llegue el día en que ustedes tengan que sentarse de nuevo en la misma forma que ahora, les prometo solemnemente, que en lo sucesivo les convidaré a comer gratis diariamente, sirviéndoles los platos más exquisitos y escogidos.
La proposición agradó a todos y fue aceptada. Acordaron reunirse cada día en aquel restaurante y probar todos los modos distintos, posibles, de colocación alrededor de la mesa, con objeto de disfrutar cuanto antes de las comidas gratuitas.
Sin embargo no lograron llegar hasta ese día. Y no porque el camarero no cumpliera su palabra sino porque el número total de combinaciones diferentes alrededor de la mesa es extraordinariamente grande. Estas son exactamente 3.628.800. Es fácil calcular, que este número de días son casi 10.000 años.
Posiblemente a ustedes les parecerá increíble que 10 personas puedan colocarse en un número tan elevado de posiciones diferentes. Comprobemos el cálculo.
Ante todo, hay que aprender a determinar el número de combinaciones distintas, posibles. Para mayor sencillez empecemos calculando un número pequeño de objetos, por ejemplo, tres. Llamémosles A, B y C.
Deseamos saber de cuantos modos diferentes pueden disponerse, cambiando mutuamente su posición. Hagamos el siguiente razonamiento. Si se separa de momento el objeto C, los dos restantes, A y B, pueden colocarse solamente en dos formas.
Ahora agreguemos el objeto C a cada una de las parejas obtenidas. Podemos realizar esta operación tres veces:
- colocar C detrás de la pareja,
- colocar C delante de la pareja,
- colocar C entre los dos objetos de la pareja.
Es evidente que no son posibles otras posiciones distintas para el objeto C, a excepción de las tres mencionadas. Como tenemos dos parejas, AB y BA, el número total de formas posibles de colocación de los tres objetos será: 2 x 3 = 6.
Hagamos el cálculo para cuatro objetos.
Tenemos cuatro objetos A, B, C y D, y separemos de momento uno de ellos, por ejemplo, el objeto D. Efectuemos con los otros tres todos los cambios posibles de posición. Ya sabemos que para tres, el número de cambios posibles es 6. ¿En cuántas formas diferentes podemos disponer el cuarto objeto en cada una de las 6 posiciones que resultan con tres objetos? Evidentemente, serán cuatro. Podemos:
- colocar D detrás del trío,
- colocar D delante del trío,
- colocar D entre el 1º y de 2º objetos,
- colocar D entre el 2º y 3º.
Obtenemos en total: 6 x 4 = 24 posiciones, pero teniendo en cuenta que 6 = 2 x 3 y que 2 = 1 x 2, entonces podemos calcular el número de cambios posibles de posición haciendo la siguiente multiplicación: 1 x 2 x 3 x 4 = 24.
Razonando de idéntica manera, cuando haya 5 objetos, hallaremos que el número de formas distintas de colocación será igual a: 1 x 2 x 3 x 4 x 5 = 120.
Para 6 objetos será: 1 x 2 x 3 x 4 x 5 x 6 = 720 y así sucesivamente.
Volvamos de nuevo al caso antes citado de los 10 comensales. Sabremos el número de posiciones que pueden adoptar las 10 personas alrededor de la mesa, si nos tomamos el trabajo de calcular el producto siguiente: 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10.
Resultará el número indicado anteriormente: 3.628.800.
El cálculo sería más complicado, si de los 10 comensales, 5 fueran muchachas y desearan sentarse a la mesa alternando con los muchachos. A pesar de que el número posible de combinaciones se reduciría en este caso considerablemente, el cálculo sería más complejo.
Supongamos que se sienta a la mesa, indiferentemente del sitio que elija, uno de los jóvenes. Los otros cuatro pueden sentarse, dejando vacías para las muchachas las sillas intermedias, adoptando 1 x 2 x 3 x 4 = 24 formas diferentes. Como en total hay 10 sillas, el primer joven puede ocupar 10 sitios distintos. Esto significa que el número total de combinaciones posibles para los muchachos es de 10 x 24 = 240.
¿En cuántas formas diferentes pueden sentarse en las sillas vacías, situadas entre los jóvenes las 5 muchachas? Evidentemente serán 1 x 2 x 3 x 4 x 5 = 120. Combinando cada una de las 240 posiciones de los muchachos, con cada una de las 120 que pueden adoptar las muchachas, obtendremos el número total de combinaciones posibles, o sea, 240 x 120 = 28.800
Este número, como vemos, es muchas veces inferior al que hemos citado antes y se necesitaría un total de 79 años. Los jóvenes clientes del restaurante, que vivieran hasta la edad de cien años, podrían asistir a una comida, servida gratis, si no por el propio camarero, al menos por uno de sus descendientes.
Sabiendo calcular el número de permutaciones posibles, podemos determinar el número de combinaciones realizables con las cifras del "juego del 15". Con otras palabras, podemos calcular el número total de ejercicios que es posible efectuar con ese juego. Se comprende fácilmente, que el cálculo se reduce a hallar el número de combinaciones posibles a base de 15 objetos. Sabemos, según hemos visto, que para ello es preciso multiplicar sucesivamente: 1 x 2 x 3 x 4 x … x 14 x 15.
Como resultado se obtiene: 1.307.674.365.000, o sea, más de un billón.
La mitad de ese enorme número de ejercicios son insolubles, o sea que en este juego, más de 600.000 millones de combinaciones no tienen solución. Por ello se comprende, en parte, la fiebre de apasionamiento por el "juego del 15", que embargó a las gentes, que no sospechaban la existencia de ese inmenso número de casos insolubles.
Si fuera posible colocar cada segundo las cifras en una nueva posición, para realizar todas las combinaciones posibles, habría que trabajar incesantemente día y noche más de 40.000 años.
Como fin de nuestra charla sobre el número de combinaciones posibles, resolvamos el siguiente problema relacionado con la vida escolar.
Hay en clase 25 alumnos. ¿En cuántas formas diferentes pueden sentarse en los pupitres?
Para los que han asimilado lo expuesto anteriormente, la solución es muy sencilla: basta multiplicar sucesivamente los 25 números siguientes: 1 x 2 x 3 x 4 x 5 x 6 x … x 23 x 24 x 25.
En matemáticas existen diversos métodos de simplificación de los cálculos, pero para facilitar operaciones como la que acabamos de mencionar, no los hay. El único procedimiento para efectuar exactamente esta operación consiste en multiplicar con paciencia todos esos números. Sólo puede reducirse algo de tiempo requerido para efectuar esa multiplicación, eligiendo una agrupación acertada de los mismos. El resultado que se obtiene es un número enorme compuesto de 26 cifras, cuya magnitud es incapaz de representársela nuestra imaginación.
He aquí el número: 15.511.210.043.330.985.984.000.000
