Páginas

lunes, 26 de febrero de 2018

1521. Cada oveja con su pareja. RESOLUCIÓN

    Mire, profe. Sea  f  una permutación al azar de  N  elementos. ¿Cuál es la probabilidad de que no haya ningún punto fijo?

    La cuestión de Pepe Chapuzas había que matizarla. Una permutación de  N  elementos se puede considerar como una biyección  F : {1, 2, 3, ... , N}  {1, 2, 3, ... , N}  y un punto fijo  K  de esa biyección cumpliría que  F(K) = K . Le pedí a Pepe que formulara de otra manera la pregunta...

    Profe, mire. Si en el juego de cada oveja con su pareja, emparejamos los elementos al azar... ¿Cuál sería la probabilidad de que no se produzcan emparejamientos horizontales?



    ¿Está más claro ahora lo que hay que calcular?

SOLUCIÓN

    Nina Guindilla lo tenía claro... 

    Mire, profe. 
    Lo contrario de que no haya ningún punto fijo es que haya alguno, esto es, al menos uno... Así, lo que hay que calcular es  
P ( A )  =  1  –  P ( A∪ A∪ A∪ ... ∪ A)

donde cada  A representa el suceso que se cumple cuando  i  es un punto fijo... Estos sucesos son compatibles por lo tanto, si consideramos
                  
S1 = ∑ P ( Ai )             (1 ≤ ≤ N)
S2 = ∑ P ( A∩ A)         (1 ≤ ≤ N)
S3 = ∑ P ( A∩ A∩ A)    (1 ≤ ≤ N)
...
por el principio de inclusión-exclusión (o del hacha)...

P ( A )  =  1 – S1 + S2 – S3 + ... + (–1)· SN

    (Ese primer 1 se puede considerar  S0 = P(E)  donde E es el suceso seguro, que es el elemento neutro de la intersección...)
    Pues ya solo faltaría calcular cada suma  Sm ... Como todos los sumandos de  Sm  valen lo mismo: el número de permutaciones de  (N–m)  elementos (casos favorables) dividido entre el número de permutaciones de  N  elementos (casos posibles), esto es,  (N–m)!/N! ; y como el número de sumandos es el número de combinaciones de N elementos tomados de  m  en  m , esto es,  N!/m!/(N–m)! , tenemos que...

Sm =  (N–m)!/N! · N!/m!/(N–m)! = 1/m!
y por tanto
P ( A ) = 1 – 1 + 1/2 – 1/6 + ... + (–1)N/N!

    ¡Controlado! 
    Comprueba el valor de  P(A)  para los primeros valores de  N .
    ¿Cuánto valdrá  P(A)  cuando  N∞ ?

RESOLUCIÓN

    Yoyó Peluso partió de la serie de Taylor de la función  f(x) = ex  centrada en  x = 0 .


ex ∑ xm/m!        (m ≥ 0)

    Mire, profe.
limN P(A) = ∑ (–1)m/m! = e–1 = 1/e = 0,367879441...

    Finalmente comprobó el valor de  P(A)  para  N = 0, 1, 2 y 3 .

    Mire, profe... 
    Si  N = 0  no hay elementos ni emparejamientos horizontales,  A  es un suceso seguro y P(A) = 1 como confirma la fórmula...
    Si  N = 1  solo hay una pareja y el único emparejamiento es horizontal. A es un suceso imposible y  P(A) = 0  lo que concuerda con la formula:  1–1 = 0 .
    Si  N = 2  hay un caso favorable de dos posibles.  P(A) = 1/2  y según la fórmula  1–1+1/2 = 1/2 .
    Si  N = 3  P(A) = 2/6 = 1/3  como se ve en el dibujo, y  1–1+1/2–1/6 = 2/6 = 1/3 .

No hay comentarios:

Publicar un comentario