sábado, 28 de febrero de 2009

El mentiroso

Hugo miente siempre en martes, jueves y sábados y el resto de los días de la semana dice siempre la verdad. Si un día en particular mantenemos la siguiente conversación:

Yuyo: ¿Que día es hoy?
Hugo: Sábado
Yuyo: ¿Que día será mañana?
Hugo: Miércoles

¿En que día de la semana semana tuvimos esta conversación?

Mississippi (Respuesta)

Antes de leer esta solución, te recomiendo que leas nuestros artículos "Permutaciones", "Combinaciones" y "Permutaciones con elementos repetidos".

Dividamos el problema. Primero olvidémonos de las "S". Obtenemos una colección de letras con una "m", dos "p" y cuatro "i". Como sabes, el número de reordenamientos, donde identificamos letras iguales, de la colección anterior esta dado por D*1!*2!*4!=(1+2+4)! Por lo que D=105. Ahora, ya que tenemos un reordenamiento dado, tenemos que colocar las "S" entre las letras restantes, pero como no pueden estar juntas, sólo podemos colocar, a lo mas, una entre cada par de las otras letras. Por el momento no nos importa como están reordenadas las demás letras, sólo los espacio entre ellas. Entonces, las palabras que formemos serán de la forma

  • 0X0X0X0X0X0X0X0

Donde cada X marca un lugar donde esta algunas de las otras letras, y cada 0 indica un posible lugar donde estará una "S". Entonces basta tomar 4 de 8 posibles lugares, es decir, el numero de combinaciones de 8 en 4. Como sabes, este número esta dado por C(8,4)=8!/(4!4!)=70.

Entonces por cada reordenamiento del las letras (sin incluir las S), tendremos 70 posibilidades para acomodar las "S". De ahí que el numero de reordenamientos de la palabra MISSISSIPPI, donde dos "S" no aparecen juntas es 105*70=7350.

Permutaciones con elementos repetidos

En nuestro artículo anterior, hemos supuesto que todos los elementos son diferentes. Supongamos que queremos encontrar todos los reordenamientos de tres pelotas verdes y dos azules. Aquí tenemos cinco elementos {a1,a2,v1,v2,v3}, donde a1 es la primera pelota azul y a2, la segunda; de igual manera con las "v". Así que podríamos pensar que el número de reordenamientos es 5!

Sin embargo, debes tomar en cuenta que al momento de reordenar, para nosotros nos dará lo mismo el reordenamiento a1-v2-v3-a2-v1 que el reordenamiento a2-v1-v2-a1-v3 ¡De cualquier forma veremos (en este orden) una pelota azul, dos verdes, una azul y una verde!

El secreto esta en que no importa que orden tomemos las pelotas verdes, ni las pelotas azules. Digamos que el numero de reordenamientos donde identificamos pelotas del mismo color es D. Sabemos que el numero de reordenamientos (permutaciones) de las pelotas, sin identificarlas por color es 5!. Ahora por cada reordenamiento de las pelotas donde identificamos las pelotas por color, tenemos 2! reordenamientos de pelotas azules y 3! de verdes, tomandolas sin identificarlas por colores. Entonces, llegamos a la fórmula

  • D*2!*3!=5!

De donde D=10. Una extraña coincidencia con nuestro ejemplo de combinaciones ¿No crees? No tanto. En el problema anterior identificamos a los dos niños que seleccionamos y a los tres que dejamos fuera. Así, los dos niños que escogemos se vuelven "del mismo color" y los tres restantes "del otro color".

En general si tenemos k tipos diferentes de objetos, cada uno con n_i elementos, i=1,2,...,k, es fácil ver que el numero de reordenamientos D donde identificamos elementos del mismo tipo esta dado por:

  • D*(n_1)!*(n_2)!*...*(n_k)!=(n_1+n_2+...+n_3)!

Para darte un ejemplo, toma 5 monedas de 50 ctvs, tres de a peso y 4 de cinco. ¿Cuántas maneras tienes de reordenarlas? Aquí tenemos 3 tipos diferentes de objetos. El primero tipo tiene 5 elementos, así que n_1=5; el segundo tiene 3, así que n_2=3; y por ultimo, el tercer tipo tiene 4 objetos, así que n_3=4. El total de objetos esta dado por n_1+n_2+...+n_3=5+3+4=12. Así que el numero de reordenamientos D, donde identificamos monedas del mismo tipo esta dado por

  • D*5!*3!*4!=12!

De donde D=27, 720 ¡Son demasiados! Y los calculamos en pocos segundos, increíble, ¿no?.

Como ejercicio, toma dos monedas de peso y tres de dos, y trata de encontrar los 10 posibles reordenamientos, identificando monedas del mismo tipo.

Combinaciones

Imagina que tienes cinco pelotas de diferentes colores y quieres tomar dos de ellas: ¿de cuentas formas puedes hacerlo?

Lo primero que podríamos hacer es ordenarlas de alguna forma. Escojamos a los dos primero y olvidémonos del resto. ¡Ya está! ¿O no?...

¡No! En realidad tenemos que tomar en cuanta dos hechos:

  • No importa en que orden tomemos a las dos primeras pelotas. Da lo mismo, por ejemplo, tomar una roja primero y una amarilla después, o una amarilla primero y una roja después. Recuerda que dos elementos diferentes se pueden reordenar de 2!

  • No importa en que orden tomemos las últimas tres. Como sabes, el número de reordenamiento de 3 elementos diferentes es 3!

Entonces, si denotamos por "C" las combinaciones que podemos formar de dos elementos diferentes, a partir de un conjunto de cinco objetos diferentes, tenemos que C(2!)(3!)=5! Entonces C=10. Es decir, el numero de combinaciones que podemos tomar es 10. ¿Cuántas podemos tomar de tres elementos a partir del mismo conjunto que teníamos al principio? La respuesta es ¡10! Esto porque podemos aplicar el mismo razonamiento, solamente que tomando a los tres últimos.

En general, en un conjunto de n elementos diferentes, tenemos n! formas de reordenarlos. Si queremos tomar una combinacion de r de estos (recuerda que r debe estar entre cero y n), los formamos en una fila y escogemos los primeros r. Sin embargo, el orden de los primero r elementos no nos va a importar (como en el ejemplo, queremos los primeros dos, no importa si el orden es amarillo-rojo o rojo-amarillo) Tampoco nos va a importar el orden de los últimos (n-r) elementos. Así que para el número de combinaciones de r elementos diferentes en un conjunto de n elementos diferentes (lo cual denotaremos por C(n,r)), tendremos que

  • C(n,r)*r!*(n-r)!=n!

Piensa en el primer ejemplo, con n=5 y r=2. Te darás cuenta que aunque la fórmula parece muy extraña, no lo es tanto. Despejando, obtenemos una fórmula muy conocida en tus clases de probabilidad:

  • C(n,r)= n! / (r! * (n-r)!)

que como hemos dicho, es el número de combinaciones (donde el orden no importa), de r elementos diferentes a partir de un conjunto de n elementos diferentes o, de manera más corta, las combinaciones de n en r.

Para verificar esta formula, te invito a que encuentras todas combinaciones de 5 en 2 y verifiques que, en efecto, son 10.

Permutaciones

Imagina que tienes 3 niños, y quieres ponerlos en una fila: ¿de cuántas maneras puedes hacerlo?

Para la primera posición tienes 3 posibilidades. Una vez que haz escogido uno, para la segunda posición tienes 2 posibilidades y para la última tienes solamente una (pues ya haz escogido dos niños de tres). Esto es lo mismo que tomar las números {1,2,3} y reordenarlos. Sus posibles reordenamientos son:

  • 1-2-3
  • 1-3-2
  • 2-1-3
  • 2-3-1
  • 3-1-2
  • 3-2-1

Si notas, el número de reordenamientos es 3x2x1. Te invito a hacer el ejercicio con cuatro niños (o cuatro números) y te darás cuenta que el número de reordenamientos es 4x3x2x1. Para cinco, será 5x4x3x2x1 y así sucesivamente. Esta manera de multiplicar números es muy importante y recibe un nombre: factorial.

Para un numero entero "n", su factorial se denota "n!" (se lee n factorial) y se define de la siguiente forma:

  • 0!=1
  • n!=(n)(n-1)!
Por ejemplo,
  • 1!=1(1-1)!=1(0!)=1(1)=1
  • 2!=2(2-1)!=2(1!)=2(1)=2
  • 3!=3(3-1)!=3(2!)=3(2)=6
  • 4!=4(4-1)!=4(3!)=4(6)=24.

La idea detrás de esta definición (que llamamos recursiva) es que al final obtendremos que n!=n(n-1)(n-2)...(3)(2)(1), es decir multiplicaremos "n" por todos los números anteriores, hasta llegar a 1. Si notas, tenemos que un grupo de "n" niños, lo podemos reordenar de n! formas diferentes. Este concepto, lo denotamos por permutaciones de un conjunto.

martes, 24 de febrero de 2009

Simetrías

sábado, 21 de febrero de 2009

Mississippi

¿Cuantas maneras existen de reordenar la palabra MISSISSIPPI, sin que dos "S" aparezcan de manera consecutiva?

Por ejemplo: MISPISISISP Y IPPISSISIISM son reordenamientos de MISSISSIPPI, pues ambos se forman con las letras que tiene MISSISSIPPI. Pero MISPISISISP es un reordenamiento válido, pues las cuatro "S" estan separadas al menos por una letra, mientras que en IPPISSISIISM no.

Espero su respuesta a este primer Desafio Matemático para No Matemáticos.

Desafio Matemático para No Matemáticos

Hola a todos,

A partir de hoy estaremos publicando pequeños problemas de Matemáticas que pueden resultar un verdadero reto para aquellos que no estén familiarizados con este arte. El propósito es mostrar que las Matemáticas no tienen que ser aburridas ni mecánicas y, que cualquier persona puede hacer Matemáticas interesantes, sin tener que ser necesariamente matemático. Los desafíos surfearan por la red a manera de cadenas, donde se adjuntará un archivo, cuya contraseña es el reto al desafío y donde podrán ingresar sus datos para que todos sepan que son buenazos para quebrarse el coco. Después de algunos días, publicaremos las respuestas así como un posible camino para obtenerlas (recuerden que en Matemáticas existen muchos caminos para llegar a una solución).

Suerte y espero que esta nueva propuesta les resulte divertida.