SOMBREROS

(Un problema de probabilidades)

Éste es un clásico problema de probabilidad planteado así. En el guardarropa de un centro de congresos se recogen los sombreros de los congresistas, éstos pierden sus fichas de identificación por lo que, al término de la sesión, recogen los sombreros al azar. ¿Cual es la probabilidad de que ninguno reciba su propio sombrero? ¿Cómo evoluciona esta probabilidad cuando el número de congresistas aumenta?

Pocos intuyen que esta probabilidad es prácticamente independiente del número de congresistas con sombrero. Curiosamente está relacionada con el número e.

Para atacar el problema con éxito, consideremos previamente todas las permutaciones de n elementos: a₁, a₂, a₃, ... a_n, (cuyo número es n!) y llamaremos a una de ellas permutación base. Dada cualquier otra permutación de los mismos n elementos, llamaremos fijos a aquellos que coincidan en posición con los de la base. Por último llamaremos completas a aquellas permutaciones que no contengan ningún elemento fijo.

En el problema de los sombreros, una completa corresponderá a un caso en que nadie recibe su propio sombrero. Quedaría resuelto si averiguamos cual es el número de completas dada una permutación base de n elementos o sombreros.

Sea C_n el número total de completas correspondientes a una permutación base de n elementos. Es fácil ver que C₁= 0, C₂ = 1, C₃ = 2...

Demostremos ahora la importante igualdad: C_n = (n-1) C_n-1 + (n-1) C_n-2 (1)

El primer sumando de la igualdad (1) es el número de completas de n elementos, que pueden obtenerse, partiendo de cada una de las completas de n-1 elementos, por el proceso de sustituir uno de sus n-1 elementos, a_i, por el nuevo elemento a_n, colocando el a_i como último elemento de la nueva permutación de n elementos.

Partamos ahora de una cualquiera de las completas de orden n; si intercambiamos de posición el elemento a_n y el último, podrá ocurrir que éste, en la nueva permutación obtenida, se convierta en fijo, lo que quiere decir que la completa de que partíamos no fue originada por el proceso descrito en el párrafo anterior sino por otro consistente en, partiendo de una permutación de orden n-1, con un solo elemento fijo, sustituir éste por a_n y colocar el fijo al final.

Es fácil ver que el número de permutaciones de orden n-1 con un solo elemento fijo es precisamente (n-1) C_{n-2 ,} que corresponde al segundo sumando de la fórmula (1), con lo que esta queda justificada.

Llamemos P_n a la probabilidad de que una permutación de orden n sea completa con respecto a la base.

P_n = C_n/n! ; P₁ = 0; P₂ = ½

De (1), dividiendo por n! obtenemos: ;

n(P_n – P_n-1) = -(P_n-1 – P_n-2) (2)

Haciendo en (2) P_n – P_n-1 = V_n , tendremos que nV_n = -V_n-1

Se ve que V_{n =} 1/n!, con signo + si n es par y – si n es impar.

Finalmente se llega para la probabilidad buscada, a la expresión:

que tiende al valor 1/e = 0,3678... cuando n tiende a infinito. Ya para 7 sombreros el valor de la probabilidad se estabiliza según vemos en el siguiente cuadro, demostrando su relativa independencia del número de sombreros.

Sombreros	P
2	0,5000
3	0,3333
4	0,3750
5	0,3666
6	0,3680
7	0,36785
8	0,36788
9	0,367891
10	0,367894
40	0,367879

Aristogeronte

Madrid. Agosto 04