noticias y última hora

The matching problem o cómo no formar ninguna pareja

Imaginemos que nos encontramos alguna de esta situaciones y nos planteamos la pregunta que viene en cada una de ellas:

  • Un profesor manda un trabajo para casa a un grupo de alumnos. Ellos entregan los mismos al profesor y cuando éste los va a devolver corregidos lo hace aleatoriamente. ¿Cuál es la probabilidad de que ninguno de los alumnos reciba su propio trabajo?
  • En una fiesta hay un cierto número de hombres ataviados con sombrero. Dejan los mismos en una sala y al término de la celebración cogen su sombrero de forma aleatoria. ¿Cuál es la probabilidad de que ninguno de los hombres lleve su propio sombrero?
  • Vamos a enviar felicitaciones de Navidad a nuestros familiares. Rellenamos las tarjetas por un lado y los sobres por otro y luego metemos las tarjetas en los sobres aleatoriamente. ¿Cuál es lo probabilidad de que ninguna de las tarjetas acabe en el sobre que le corresponde?

Todos estos ejemplos son casos en los que podemos aplicar el, al parecer, llamado The Matching Problem, aunque también he visto que lo llaman Montmort’s matching problem en honor a Pierre Raymond de Montmort, matemático francés nacido en 1678.

Bueno, vamos al tema. Para empezar, creo que se ve bastante claro que todos los casos son equivalentes. Entonces, ¿cuál diríais que es la probabilidad que se nos pide? Lo primero que uno podría pensar es: depende del número de alumnos, hombres y familiares que haya en cada caso. Es decir, que lo normal sería pensar que esa probabilidad depende del número de individuos que tenga la población. Pues no es así. La probabilidad es siempre la misma. Bueno, no exactamente. En realidad la probabilidad se acerca a un número concreto conforme el número de individuos se acerca a infinito. Curioso, ¿no?

Y ahora la pregunta es: ¿cuál es esa probabilidad? Pues bueno, teniendo en cuenta que si llamamos N_n a la variable aleatoria que nos indica el número de emparejamientos válidos de entre n se puede llegar a que su función de probabilidad es la siguiente:

\displaystyle{P(N_n=k)=\cfrac{1}{k!} \cdot \sum_{j=0}^{n-k} \cfrac{(-1)^j}{j!}} con k=0,1, \ldots ,n

la probabilidad de que no se haya formado ninguna pareja válida nos la da la probabilidad de que N_n sea igual a {0}. Es decir:

\displaystyle{P(N_n=0)=\sum_{j=0}^{n} \cfrac{(-1)^j}{j!}}

¿Os suena esta suma? Seguro que a muchos sí. Hacemos límite cuando n \to \infty y obtenemos lo que queremos:

\displaystyle{P(N_n=0)=\sum_{j=0}^{n} \cfrac{(-1)^j}{j!} \xrightarrow{n \to \infty} \cfrac{1}{e}}

Es decir, que la probabilidad de que no se forme ninguna pareja válida se acerca a \cfrac{1}{e} tanto más como grande sea n. Al parecer con n=5 ya nos queda una buena aproximación. Lo sorprendente es que cuanto más grande sea n mejor es la aproximación a \cfrac{1}{e}. Y digo yo: ¿cuánto vale ese número? Pues algo así como 0.367879441. Es decir, que en una situación de este tipo no se forma ninguna pareja válida aproximadamente el 36,8% de las veces. Y ese tanto por ciento se va acercando cada vez más a \cfrac{1}{e} \cdot 100 conforme aumenta el valor de n.

Realmente curioso el asunto. ¿Esperabais que la probabilidad fuera más alta o más baja?

Fuentes:

Autor: ^DiAmOnD^ | Publicado el 30 de October de 2007
Comments Off
Categorías: Curiosidades, Estadística, Otras constantes

Probabilidad de escoger dos números coprimos

Hace ya más de un año os comentaba en esta entrada (la tercera de Gaussianos) cuál era la probabilidad de que al escoger al azar dos números naturales (mayores que 1) éstos fueran coprimos (primos relativos). Esta probabilidad es \cfrac{6}{\pi^2}, pero no daba la demostración de este hecho. Este post va a servir para ello.

Teorema: La probabilidad de que al escoger al azar dos números naturales x,y \ge 2 sean coprimos (primos relativos) es \cfrac{6}{\pi^2}

Demostración

Supongamos que escogemos al azar dos números naturales x,y \ge 2 y menores que una cierta cota. Para que sean coprimos no deben tener ningún factor primo común.

Al escoger un número mayor o igual que 2, la probabilidad de que contenga al 2 como factor es \frac{1}{2}. Al escoger dos números, la probabilidad de que los dos contengan al 2 como factor es (\frac{1}{2})^2. Por tanto, la probabilidad de que no lo contengan a la vez los dos números es:

p_2=1- (\frac{1}{2})^2

Para el 3, la probabilidad de que un número lo contenga como factor es \frac{1}{3}. Por analogía, la probabilidad de que no lo contengan los dos números a la vez será:

p_3=1- (\frac{1}{3})^2

Al ser estos hechos sucesos independientes la probabilidad de la intersección es el producto de las probabilidades. Aplicando este hecho obtenemos que la probabilidad de que dos números escogidos al azar sean coprimos es el producto de estos p_i. Esto es:

P=(1-(\frac{1}{2})^2)(1-(\frac{1}{3})^2) \cdots (1-(\frac{1}{n})^2)

Tomamos n hasta la raíz cuadrada de la cota superior.

Haciendo n\to\infty obtenemos la probabilidad buscada.

Para calcularla utilizaremos la fórmula de la suma de una progresión geométrica. Esta fórmula es:

\displaystyle\sum_{n=0}^\infty {a^n}=1+a+a^2+ \cdots a^k+ \cdots =\cfrac{1}{1-a}

Por ejemplo, para el primer término tomamos a=(\frac{1}{2})^2 y damos la vuelta a la fórmula anterior:

1-\left (\cfrac{1}{2} \right )^2= \cfrac{1}{1+\left (\cfrac{1}{2} \right )^2+\left (\cfrac{1}{2} \right )^4+ \cdots +\left (\cfrac{1}{2} \right )^{2k}}

Haciendo lo mismo con todos los números primos nos queda lo siguiente:

P= \cfrac{1}{1+(\frac{1}{2})^2+(\frac{1}{2})^4+ \cdots +(\frac{1}{2})^{2k}} \cdot \cfrac{1}{1+(\frac{1}{3})^2+(\frac{1}{3})^4+ \cdots +(\frac{1}{3})^{2k}} \cdots

Ya estamos cerca.

Miremos ahora qué pasaría si multiplicáramos todas las fracciones y desarrolláramos todos los productos. El resultado sería una fracción cuyo numerador es 1 y cuyo denominador es una suma de fracciones. ¿Qué tienen de particular esas fracciones? Pues muy sencillo: todas ellas tienen numerador 1 y denominador un cuadrado perfecto. De hecho hay más: haciendo k,n\to\infty tenemos que en el denominador aparece la suma de los inversos de los cuadrados perfectos de todos los números naturales. Es decir, que esa probabilidad tiende a una fracción cuyo numerador es 1 y cuyo denominador es la suma de los inversos de los cuadrados perfectos de todos los números naturales. ¿Os suena esa suma? ¡Exacto!: El problema de Basilea. El valor de esta suma es bien conocido:

\displaystyle 1+\frac{1}{2^2}+\frac{1}{3^2}+ \cdots +\frac{1}{k^2}+ \cdots=\sum_{n=1}^\infty {\cfrac{1}{n^2}}=\cfrac{\pi^2}{6}

Por tanto tenemos:

P=\cfrac{1}{\displaystyle\sum_{n=1}^\infty {\cfrac{1}{n^2}}}=\cfrac{1}{\frac{\pi^2}{6}}=\cfrac{6}{\pi^2}

Esto es:

La probabilidad de que al elegir dos números naturales mayores o iguales que 2 sean primos relativos es
P=\cfrac{6}{\pi^2}

q.e.d.

Fuente: MENSA

Autor: ^DiAmOnD^ | Publicado el 20 de August de 2007
Comments Off
Categorías: Demostraciones, Estadística, Números primos, Pi

El TVI y el dado de tres caras

Hace un tiempo Papá Oso, de Sospechosos Habituales, nos mandó una consulta sobre un post suyo de su blog El Hombre de los Dados. El artículo en cuestión relacionaba el teorema de los valores intermedios y los dados, intentando a partir de él construir un dado de 3 caras, es decir, una figura de 3 caras que cumpliera que las 3 caras tienen la misma probabilidad de salir al tirarla tipo dado. Este post va a servir para presentaros el artículo de Papá Oso y para que veáis la respuesta que yo le di.

(Leer el resto del post)

Autor: ^DiAmOnD^ | Publicado el 28 de June de 2007
Comments Off
Categorías: Cálculo, Estadística, Teoremas

¿Cuántos vídeos caben en Youtube? La respuesta está en la combinatoria

Curiosa pregunta la que titula este artículo y probablemente para mucha gente también sea curioso que la respuesta a la misma se pueda encontrar en las Matemáticas. Pues es así. Vamos con la teoría correspondiente y dejemos la pregunta para el final:

Combinatoria

La combinatoria es una rama de las Matemáticas que básicamente se encarga de estudiar cuántos grupos pueden formarse con un cierto número de objetos atendiendo a determinados criterios. Como esta definición puede no ser demasiado clara vamos a poner un par de ejemplos:

  • ¿Cuántos números de 5 cifras pueden formarse con los números del 1 al 9?
  • ¿Cuántas manos posibles de mus pueden darse? (Cada mano de mus consta de 4 cartas)

La combinatoria se encarga de determinar esos números.

(Leer el resto del post)

Autor: ^DiAmOnD^ | Publicado el 26 de March de 2007
69 Comentarios
Categorías: Aprenda como, Estadística

La leyenda de Dantzig

Imaginad la siguiente situación:

Un día llegáis a clase algo tarde. Os sentáis y al mirar a la pizarra veis un par de ecuaciones escritas en ella. Como es normal suponéis que es trabajo mandado por el profesor y las apuntáis para trabajar en ellas al acabar las clases. Llegáis a casa y os ponéis con la tarea. Notáis que la dificultad de los ejercicios propuesto es algo mayor de lo habitual, pero eso no os echa para atrás y después de unos días conseguís terminar el trabajo. Al día siguiente de acabarlo se lo entregáis al profesor.

Días después recibís una llamada del mismo en la que os dice: ¿te das cuenta de lo que has hecho con tu trabajo?. Respondéis: vaya, realicé mal la tarea, ¿verdad?. Y vuestro profesor os dice: nada de eso. Has resuelto dos ecuaciones de las que todavía no se conocía la solución.

Es una historia de leyenda, algo soñado por, probablemente, todos los estudiantes de alguna carrera de ciencias. ¿Quién no ha deseado alguna vez resolver un problema que no tenía solución hasta ese momento?. Grandes genios como Andrew Wiles con el último teorema de Fermat o Grigori Perelman con la conjetura de Poincaré lo consiguieron. Pero la historia que os he planteado tiene un matiz que la hace distinta a estos dos casos: vosotros ni siquiera sabíais de antemano que esas ecuaciones no tenían solución. Matiz que le da más importancia si cabe al asunto.

Pues esta historia que tiene toda la pinta de leyenda ocurrió en realidad. Comencemos a poner nombres y apellidos a los protagonistas:

George Bernard Dantzig fue un matemático ruso considerado como el padre de la programación lineal. Entre sus trabajos podemos destacar el desarrollo del método simplex para resolución de problemas de esta rama de las Matemáticas.

Un día Dantzig llegó tarde a una clase del profesor Jerzy Neyman (quien haya tenido contacto con test de hipótesis de Estadística en la Universidad probablemente lo conozca por el lema de Neyman-Pearson). Al sentarse vio dos problemas escritos en la pizarra y consideró que eran trabajo para casa. Según las propias palabras de Dantzig “le parecieron ser un poco más difíciles de lo normal”, pero de todas formas días después consiguió las soluciones completas de los mismos. Seis semanas después Dantzig recibió la inesperada visita de su profesor Neyman, el cual le comunicó su hallazgo: había resuelto dos problemas estadísticos que hasta ese momento carecían de solución. Además le informó de que había preparado la resolución de uno de los problemas para su publicación en una revista matemática. Años despues Abraham Wald fue informado de que las conclusiones a las que había llegado en un trabajo que iba a publicar eran las mismas a las que había llegado Dantzig al resolver el otro problema. Por esta razón Wald incluyó a Dantzig como coautor de ese trabajo.

Durante mucho tiempo esta historia tuvo la categoría de leyenda urbana. Al parecer la razón por la cual se creía falsa fue la aparición de una exageración de la misma en un libro sobre pensamiento positivo. Por suerte Dantzig vivió lo suficiente (falleció en 2005) como para poder aclarar que la historia era verdadera.

Como podéis ver ningún problema es imposible. Solamente hay que creerse capaz. A Dantzig le ayudó no saber que esos problemas permanecían sin solución, y probablemente no los hubiera resuelto de haber conocido ese hecho. En todo caso historias como estas nos hacen ver lo que acabo de decir: si nos creemos capaces de resolver una situación tendremos más posibilidades de conseguirlo.

Y para terminar una curiosidad. No conozco a nadie que haya resuelto un problema en las condiciones de Dantzig, pero sí sé que en mi Facultad se demostró algún que otro resultado que hasta ese momento no tenía demostración (una pena no saber qué teoremas fueron ni quiénes lo consiguieron). ¿Conoceís vosotros a alguien que haya conseguido resolver algo parecido?. Contadnos.

Fuentes:

Autor: ^DiAmOnD^ | Publicado el 7 de November de 2006
Comments Off
Categorías: Curiosidades, Estadística, Historia, Matemáticos

Un juego

Os voy a proponer un juego matemático, es un poco chorra y seguramente lo sepáis todos, pero por lo menos nos divertiremos un rato. El juego es el siguiente:

Estáis en un concurso, tipo Allá tú, hay 3 cajas: dos de ellas contienen premios malos (1€ y10€), y la otra un buen premio (600.000€). Así que el presentador os hace elegir una caja, vosotros lo hacéis como buenos concursantes, y acto seguido el presentador os muestra el contenido de una de las cajas que no habíais elegido, dentro de dicha caja estaba el premio de 1€, y ahora os pregunta:

¿Quieres cambiar tu caja?

¿Qué haríais?

Contestad sin miedo, solo tenéis que decir sí o no, no pongáis ninguna explicación, porque fastidiaríais el juego a los demás.

(Leer el resto del post)

Autor: Fran | Publicado el 2 de August de 2006
Comments Off
Categorías: Estadística, Juegos

Siguiente