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^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

8 Comentarios

  1. Estos problemas tan normales que llevan a un número importante de resultado me encantan, este es casi tan bueno como la aguja de buffon, jeje.

    Saludos.

    Publica una respuesta
  2. Pues yo estoy sorprendida de que sea tan alta.

    El nombre del problema Matching me ha llevado a pensar en las agencias que te buscan pareja. Si cada persona tiene un “alma gemela” y nos “repartimos” al azar, hay un 36.8% de que TODO el mundo acabe con la “pareja equivocada”!!
    La leche!, TODO EL MUNDO es mucha gente!!

    Please, que alguien me corrija si no he comprendido bien el problema (habrá sido el amor… :D)

    Publica una respuesta
  3. Algo razono yo mal, a ver qué es:

    La posibilidad de repartir mal el primer examen en un grupo de n alumnos es

    \frac{n-1}{n}

    o sea, todos los exámenes posibles (menos el bueno) dividido por el total de alumnos. Para el siguiente alumno tenemos un elemento menos en cada población, de modo que la probabilidad total es

    P(N_n = 0) = \frac{(n-1)!}{n!} = 1/n

    La probabilidad cuando son 2 alumnos es de 0.5 (dar mal el primero y el último ya está colocado) y se va haciendo menor según va creciendo la población (lo cual pensado dejando las matemáticas aparte tiene su lógica).

    Publica una respuesta
  4. Álvaro, si el primero no coge su sombrero es porque coge el de otro. Y por lo tanto, ese otro tendrá una probabilidad 1 de no coger su sombrero.

    Publica una respuesta
  5. YO esperaba que fuera menos ……….muy interesante ,saludos.

    Publica una respuesta
  6. Este problema fue el 1 de la competencia “El número de Oro” (Olimpíadas para profesores) propuesto por el excelentísimo Dr. Natalio Guersenzvaig.

    Publica una respuesta
  7. Esto me lo planteé hace muchos años con el típico reparto navideño del amigo invisible: ¿cual es la probabilidad de que nadie se tenga que regalar a sí mismo?. Me gusta este problema y la sencillez de su solución.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Tiempo finito y logarítmico » 1/e - [...] Si cada persona tiene un “alma gemela” y nos “repartimos” al azar, hay un 36.8% de que TODO el…
  2. Tiempo finito y logarítmico » Es la misma probabilidad - [...] Suena familiar: es exactamente la misma probabilidad de formar un desordenamiento en n elementos cuanto n tiende a infinito.…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *