Problema 1.Un grupo de 14 profesores dun claustro escolar organiza unha comida para celebrar a finalización da avaliación. Para armar festa alguén propuxera facer un amigo invible: cada un levaría un pequeno agasallo que se sortearía durante a celebración. Alguén comenta: "é ben seguro que algún vai levar o regalo que el mesmo comprou". Velaquí un problema matemático: cal é a probabilidade de que haxa algúen a quen lle toque o seu propio agasallo?Sabía que coñecía o problema, só que tiña outro enunciado, aínda que cunha redacción referida a unha realidade doutra época:
Problema 2. O encargado do gardarroupa dun establecemento esqueceuse de etiquetar os sombreiros dos clientes e decide devolvelos ao chou. Cal é a probabilidade de que polo menos unha persoa reciba o seu sombreiro?Ou incluso este outro, que fai referencia a cando aínda se escribían cartas:
Problema 3. Un encargado debe enviar n cartas a n direccións diferentes. Como é pouco responsable co seu traballo, introduce as cartas nos sobres ao azar. Achar a probabilidade de que introducira algunha carta no sobre correspondente.A seguinte, e última versión, recibiu o nome do xogo do recontre
Problema 4. Dúas persoas, A e B, cunha baralla completa cada unha, sacan a un tempo cada súa carta. Se extraen a mesma carta gana A. Se repiten a operación ata esgotar todas as cartas e nunca coinciden, ganará B. Pídese a probabilidade de que gane cada un dos xogadores.Esta última versión foi proposta por Pierre Rémond de Montmort (1678-1719) nun ensaio publicado no 1708. Na segunda edición desta obra (1713) resolve algúns casos simples pero queda sen dar unha solución xeral. Un dos que se enfrontaría á cuestión sería Leonhard Euler no seu Calcul de la probabilité dans le jeu de rencontre (1743). De seguido vou debullar esta resolución porque é un exemplo maxistral de como abordar un problema. En primeiro lugar profundiza sobre el, estuda varios casos ata familiarizarse con el. Cando non pode seguir traballando caso a caso busca unha propiedade que lle permita domesticalo e preparar así o asalto final. Vou seguir os pasos de Euler aínda que o farei usando unha notación distinta. Se o fago así non é por capricho, senón que despois de ler a súa resolución, vin que a entendía mellor facendo uso deste anacronismo. Polo demais, no esencial, reproducirei con toda fidelidade o seu razoamento.
A versión sobre a que traballa Euler é a dun xogo de cartas na que dúas persoas A e B, con cada seu mazo completo de cartas, van sacándoas de unha en unha. Se nalgún momento sacan os dous a mesma carta gañará A. Se, pola contra, ningún par de cartas é coincidente, gañará B. Trátase de calcular a probabilidade de que gañe cada un deles.
No canto de cartas imos falar de números e no canto de considerar únicamente o caso das 52 cartas dunha baralla francesa, trataremos o problema xeral de n cartas.
En primeiro lugar, sen perda de xeneralidade, podemos supoñer que un dos xogadores (consideremos que sexa o xogador A) ten ordenadas todas as súas cartas en orde crecente: 1, 2, 3,....,n. Agora o problema consistirá en contabilizar o número de permutacións nas que ningún elemento coincida con esta dada. Este tipo de reconto é hoxe coñecido como desarranxo.
Fago aquí unha paréntese terminolóxica. Escollín o termo desarranxo por varias razóns. En primeiro lugar xa temos en galego outro termo para referirnos a outro reconto combinatorio: arranxo
(os arranxos de n elementos tomados de m en m consisten en todos os subconxuntos ordenados de m elementos que podemos formar nun conxunto de n elementos, con m ≤ n). En segundo lugar, a denominación en inglés é derangement, en francés dérangement e en portugués, desaranjo. En español só achei que para referirse á contabilización dos desarranxos, que se fai mediante a función subfactorial. Nesta lingua hai quen usa o termo desarreglo.
Volvamos á análise de Euler. Consideremos os primeiros casos.
Se n=1, gaña A
Se n =2, hai dúas posibilidades de extracción: (1,2) gañando A, e (2,1) gañando B.
Se n = 3 Euler fai a seguinte táboa con todas as posibilidades:
 |
| Táboa para n=3 |
Se denominamos $${ A }_{ n }^{ k }=no\quad xogo\quad con\quad n\quad cartas\quad A\quad gaña\quad coa\quad carta\quad k$$
$${ A }_{ n }=no\quad xogo\quad con\quad n\quad cartas\quad A\quad gaña\quad (con \quad algunha \quad carta)$$
Podemos contabilizar o número de veces que gaña A e en que extracción. A gañará na primeira extracción nos casos 1 e 2 (ver táboa anterior), gañará na segunda extracción no caso 5 e na terceira extracción no caso 3.
$$P\left( { A }_{ 3 }^{ 1 } \right) =\frac { 2 }{ 6 } \quad\quad P\left( { A }_{ 3 }^{ 2 } \right) =\frac { 1 }{ 6 } \quad\quad P\left( { A }_{ 3 }^{ 3 } \right) =\frac { 1 }{ 6 } $$
$$P\left( { A }_{ 3 } \right) =\frac { 4 }{ 6 } $$
Para n=4:
 |
| Táboa para n=4 |
A gaña na segunda extracción nos casos 17, 18, 21 e 22.
A gaña na terceira extracción nos casos 10, 12 e 21
A gaña na cuarta extracción nos casos 8 e 15
$$P\left( { A }_{ 4 }^{ 1 } \right) =\frac { 6 }{ 24 } \quad\quad P\left( { A }_{ 4 }^{ 2 } \right) =\frac { 4 }{ 24 } \quad\quad P\left( { A }_{ 4 }^{ 3 } \right) =\frac { 3 }{24 } \quad\quad P\left( { A }_{ 4 }^{ 4 } \right) =\frac { 2 }{24 }$$
$$P\left( { A }_{ 4 } \right) =\frac { 15 }{ 24 } $$
Para n = 5 teremos un total de 5! = 120 permutacións. Moi difícil de abarcar. Pasemos a profundizar nos casos estudados e intentemos xeneralizar o que xa coñecemos. Por exemplo, con 4 cartas temos 4! ordenacións distintas. Delas danse 6 coincidencias na primeira extracción. Se non rematara o xogo coa primeira coincidencia tamén teriamos 6 coincidencias en cada unha das outras extraccións. Por exemplo na segunda vémola na táboa nos casos 1, 2, 17, 18, 21 e 22. Está claro que en xeral, para n cartas haberá (n-1)! coincidencias en calquera das extraccións . Isto permitiríanos a seguinte notación:
${ a }_{ n }^{ k }=nº\quad de\quad éxitos\quad de\quad A\quad na\quad k-ésima\quad extracción\quad con\quad n\quad cartas$
${ a }_{ n }^{ 1
}=(n-1)!$
Deamos un paso máis. Sabemos que na segunda extracción A gaña menos que (n-1)! veces pois hai que restarlle algunha das veces que gañou coa primeira. No caso das 4 cartas, das 6 coincidencias temos que restar dúas: as correspondentes aos casos 1 e 2.
E que pasaría na terceira extracción? Aquí é onde agroma a xenialidade de Euler que desbloquea as dificultades e abre unha vía para abordar o problema. Euler propón eliminar as cartas coincidentes nesa extracción nos dous mazos e pasa a contabilizar o resultado despois desta simplificación. Sabemos que hai 6 coincidencias na terceira fila (as correspondentes ás columnas 1, 6, 10, 12, 20 e 21). Eliminemos precisamente o 3 destes casos e quédanos:
Que son precisamente os 6 casos para n=3. Pero o problema de determinar en cantos casos gaña A na terceira extracción xa o resolvimos máis arriba. Sabemos que das 6 coincidencias da terceira fila debemos restar 2 da primeira e unha da segunda. Quédannos 3 vitorias para A.
En xeral, con n cartas, para determinar o número de éxitos de A na k-ésima extracción, debemos suprimir as cartas nas que se produce esa k-ésima coincidencia polo que nos quedan n-1 cartas e un total de (n-1)! casos dos que debemos restar aqueles nos que houbo unha coincidencia das k-1 primeiras extraccións. Todo isto podemos expresalo con fórmulas; farémolo para o caso de termos n+1 cartas.
${ a }_{ n+1 }^{ 1 }=n!$
Deamos un paso máis. Sabemos que na segunda extracción A gaña menos que (n-1)! veces pois hai que restarlle algunha das veces que gañou coa primeira. No caso das 4 cartas, das 6 coincidencias temos que restar dúas: as correspondentes aos casos 1 e 2.
E que pasaría na terceira extracción? Aquí é onde agroma a xenialidade de Euler que desbloquea as dificultades e abre unha vía para abordar o problema. Euler propón eliminar as cartas coincidentes nesa extracción nos dous mazos e pasa a contabilizar o resultado despois desta simplificación. Sabemos que hai 6 coincidencias na terceira fila (as correspondentes ás columnas 1, 6, 10, 12, 20 e 21). Eliminemos precisamente o 3 destes casos e quédanos:
 |
| táboa para n=3 (non é erro, compara coa de máis arriba) |
En xeral, con n cartas, para determinar o número de éxitos de A na k-ésima extracción, debemos suprimir as cartas nas que se produce esa k-ésima coincidencia polo que nos quedan n-1 cartas e un total de (n-1)! casos dos que debemos restar aqueles nos que houbo unha coincidencia das k-1 primeiras extraccións. Todo isto podemos expresalo con fórmulas; farémolo para o caso de termos n+1 cartas.
${ a }_{ n+1 }^{ 1 }=n!$
$ { a }_{ n+1 }^{ 2 }=n!-{ a }_{ n }^{ 1 }$
Temos que sumar todos os valores anteriores. Como en cada fila nos aparecen os números combinatorios, unha boa estratexia é colocar os sumandos a semellanza do triángulo de Pascal e despois pasar a sumar as diagonais, tal e como se indica na imaxe:
Euler non fai referencia a Blaise Pascal (16232-1662), posiblemente porque recoñecía de sobra a propiedade que se debe aplicar para sumar cada unha destas diagonais. Aparecera como "terceira consecuencia" nun libro do matemático francés no que explicita 19 resultados sobre o famoso triángulo que leva o seu nome. A obra, O triángulo aritmético, publicárase póstumamente no 1665 aínda que xa estaba impresa no 1654 pois Pascal xa a divulgara entre as amistades. Esa terceira consecuencia é a que agora vén a denominarse en inglés como hockey-stick identity.
Facendo uso desta identidade sumaremos a k-ésima diagonal do anterior triángulo:
$\sum _{ i=k }^{ n-1 }{ { (-1) }^{ k } } \left( \begin{matrix} k \\ i \end{matrix} \right) \frac { 1 }{ n\left( n-1 \right) .....\left( n-k \right) } ={ \left( -1 \right) }^{ k }\frac { 1 }{ n\left( n-1 \right) .....\left( n-k \right) } \sum _{ i=k }^{ n-1 }{ \left( \begin{matrix} k \\ i \end{matrix} \right) } =$
${ a }_{ n+1 }^{ 3 }=n!-{ a }_{ n }^{ 1 }-{ a }_{ n }^{ 2 }={ a }_{ n+1 }^{ 2 }-{ a }_{ n }^{ 2 }$ ....
$ { a }_{ n+1 }^{ k+1 }=n!-{ a }_{ n }^{ 1 }-{ a }_{ n }^{ 2 }-....-{ a }_{ n }^{ k }={ a }_{ n+1 }^{ k }-{ a }_{ n }^{ k }$
Con estes resultados no peto podemos poñernos a calcular os valores dos primeiros casos:
${ Para\quad n=1:\quad a }_{ 1 }^{ 1 }=1$
Con estes resultados no peto podemos poñernos a calcular os valores dos primeiros casos:
${ Para\quad n=1:\quad a }_{ 1 }^{ 1 }=1$
${ Para\quad n=2:\quad a }_{ 2 }^{ 1 }=1!=1 \quad { a }_{ 2 }^{ 2 }={ a }_{ 2 }^{ 1 }-{ a }_{ 1 }^{ 1 }=1-1=0$
$ { Para\quad n=3:\quad a }_{ 3 }^{ 1 }=2!=2 \quad { a }_{ 3 }^{ 2 }={ a }_{ 3 }^{ 1 }-{ a }_{ 2 }^{ 1 }=2-1=1 \quad { a }_{ 3 }^{ 3 }={ a }_{ 3 }^{ 2 }-{ a }_{ 2 }^{ 2 }=1-0=1$
$Para\quad n=4:\quad { a }_{ 4 }^{ 1 }=3!=6 \quad { a }_{ 4 }^{ 2 }={ a }_{ 4 }^{ 1 }-{ a }_{ 3 }^{ 1 }=6-2=4 \quad{ a }_{ 4 }^{ 3 }={ a }_{ 4 }^{ 2 }-{ a }_{ 3 }^{ 2 }=4-1=3$
$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad { a }_{ 4 }^{ 4 }={ a }_{ 4 }^{ 3 }-{ a }_{ 3 }^{ 3 }=3-1=2$
Euler, incansable, continúa e ofrece todos estes valores:
Chegou o momento de calcular as probabilidades. Agora contamos co coñecemento suficiente para abordar o ataque final ao problema.
$P\left( { A }_{ n }^{ k } \right) =\frac { { a }_{ n }^{ k } }{ n! } \quad \quad \quad P\left( { A }_{ n-1 }^{ k } \right) =\frac { { a }_{ n }^{ k } }{ \left( n-1 \right) ! } $
 |
| nº de éxitos de A en cada extracción |
$P\left( { A }_{ n }^{ k } \right) =\frac { { a }_{ n }^{ k } }{ n! } \quad \quad \quad P\left( { A }_{ n-1 }^{ k } \right) =\frac { { a }_{ n }^{ k } }{ \left( n-1 \right) ! } $
$P\left( { A }_{ n }^{ k+1 } \right) =\frac { { a }_{ n }^{ k+1 } }{ n! } =\frac { { a }_{ n }^{ k }-{ a }_{ n-1 }^{ k } }{ n! } =\frac { { a }_{ n }^{ k } }{ n! } -\frac { { a }_{ n-1 }^{ k } }{ \left( n-1 \right) !\cdot n } =P\left( { A }_{ n }^{ k } \right) -\frac { P\left( { A }_{ n-1 }^{ k } \right) }{ n } \quad \quad \quad [1]$
Agora podemos calcular as probabilidades de que, con n cartas, A gane na k-ésima extracción:
$P\left( { A }_{ n }^{ 1 } \right) =\frac { { a }_{ n }^{ 1 } }{ n! } =\frac { \left( n-1 \right) ! }{ n! } =\quad \frac { 1 }{ n } \quad \quad$
Agora podemos calcular as probabilidades de que, con n cartas, A gane na k-ésima extracción:
$P\left( { A }_{ n }^{ 1 } \right) =\frac { { a }_{ n }^{ 1 } }{ n! } =\frac { \left( n-1 \right) ! }{ n! } =\quad \frac { 1 }{ n } \quad \quad$
$ P\left( { A }_{ n }^{ 2 } \right) =P\left( { A }_{ n }^{ 1 } \right) -\frac { P\left( { A }_{ n-1 }^{ 1 } \right) }{ n } =\frac { 1 }{ n } -\frac { 1 }{ n\left( n-1 \right) } $
$ P\left( { A }_{ n }^{ 3 } \right) =P\left( { A }_{ n }^{ 2 } \right) -\frac { P\left( { A }_{ n-1 }^{ 2 } \right) }{ n } =\frac { 1 }{ n } -\frac { 1 }{ n\left( n-1 \right) } -\frac { 1 }{ n } \left( \frac { 1 }{ n-1 } -\frac { 1 }{ \left( n-1 \right) \left( n-2 \right) } \right) =$
$ =\frac { 1 }{ n } -\frac { 2 }{ n\left( n-1 \right) } +\frac { 1 }{ n\left( n-1 \right) \left( n-2 \right) } $
$ P\left( { A }_{ n }^{ 4 } \right) =P\left( { A }_{ n }^{ 3 } \right) -\frac { P\left( { A }_{ n-1 }^{ 3 } \right) }{ n } =$
$=\frac { 1 }{ n } -\frac { 2 }{ n\left( n-1 \right) } +\frac { 1 }{ n\left( n-1 \right) \left( n-2 \right) } -\frac { 1 }{ n } \left( \frac { 1 }{ n-1 } -\frac { 2 }{ \left( n-1 \right) \left( n-2 \right) } +\frac { 1 }{ \left( n-1 \right) \left( n-2 \right) \left( n-3 \right) } \right) =$
$ =\frac { 1 }{ n } -\frac { 3 }{ n\left( n-1 \right) } +\frac { 3 }{ n\left( n-1 \right) \left( n-2 \right) } -\frac { 1 }{ n\left( n-1 \right) \left( n-2 \right) \left( n-3 \right) } $
$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $
$ \quad \quad \quad \quad \quad \quad \quad \quad \quad .....$
$ P\left( { A }_{ n }^{ k+1 } \right) =\left( \begin{matrix} k \\ 0 \end{matrix} \right) \frac { 1 }{ n } -\left( \begin{matrix} k \\1 \end{matrix} \right) \frac { 1 }{ n\left( n-1 \right) } +\left( \begin{matrix} k \\ 2 \end{matrix} \right) \frac { 1 }{ n\left( n-1 \right) \left( n-2 \right) } -.......+{ \left( -1 \right) }^{ k }\left( \begin{matrix} k \\ k \end{matrix} \right) \frac { 1 }{ n\left( n-1 \right) ...\left( n-k \right) } \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $
$.....$
$ P\left( { A }_{ n }^{ n } \right) =\left( \begin{matrix} n-1 \\ 0 \end{matrix} \right) \frac { 1 }{ n } -\left( \begin{matrix} n-1 \\ 1 \end{matrix} \right) \frac { 1 }{ n\left( n-1 \right) } +\left( \begin{matrix} n-1 \\ 2 \end{matrix} \right) \frac { 1 }{ n\left( n-1 \right) \left( n-2 \right) } -......+{ \left( -1 \right) }^{ n }\left( \begin{matrix} n-1 \\ n-1 \end{matrix} \right) \frac { 1 }{ n! } $
Temos que sumar todos os valores anteriores. Como en cada fila nos aparecen os números combinatorios, unha boa estratexia é colocar os sumandos a semellanza do triángulo de Pascal e despois pasar a sumar as diagonais, tal e como se indica na imaxe:
Facendo uso desta identidade sumaremos a k-ésima diagonal do anterior triángulo:
$\sum _{ i=k }^{ n-1 }{ { (-1) }^{ k } } \left( \begin{matrix} k \\ i \end{matrix} \right) \frac { 1 }{ n\left( n-1 \right) .....\left( n-k \right) } ={ \left( -1 \right) }^{ k }\frac { 1 }{ n\left( n-1 \right) .....\left( n-k \right) } \sum _{ i=k }^{ n-1 }{ \left( \begin{matrix} k \\ i \end{matrix} \right) } =$
$ ={ \left( -1 \right) }^{ k }\frac { 1 }{ n\left( n-1 \right) ....\left( n-k \right) } \left( \begin{matrix} n \\ k+1 \end{matrix} \right) ={ \left( -1 \right) }^{ k }\frac { 1 }{ \left( k+1 \right) ! } $
Finalmente poderemos obter o resultado de todas estas sumas, o que nos dá a probabilidade desexada, de que A gane nunha partida con n cartas:
$$P\left( { A }_{ n } \right) =1-\frac { 1 }{ 2! } +\frac { 1 }{ 3! } -\frac { 1 }{ 4! } +\frac { 1 }{ 5! } -....+{ { \left( -1 \right) } }^{ n-1 }\frac { 1 }{ n! } $$
Nun último toque fantástico Euler propón pensar que pasaría se o número de cartas fose infinito.
$$P\left( { A }_{ \infty } \right) =1-\frac { 1 }{ 2! } +\frac { 1 }{ 3! } -\frac { 1 }{ 4! } +\frac { 1 }{ 5! } -....=1-\frac { 1 }{ e } =0,632120558$$
Finalmente poderemos obter o resultado de todas estas sumas, o que nos dá a probabilidade desexada, de que A gane nunha partida con n cartas:
$$P\left( { A }_{ n } \right) =1-\frac { 1 }{ 2! } +\frac { 1 }{ 3! } -\frac { 1 }{ 4! } +\frac { 1 }{ 5! } -....+{ { \left( -1 \right) } }^{ n-1 }\frac { 1 }{ n! } $$
Nun último toque fantástico Euler propón pensar que pasaría se o número de cartas fose infinito.
$$P\left( { A }_{ \infty } \right) =1-\frac { 1 }{ 2! } +\frac { 1 }{ 3! } -\frac { 1 }{ 4! } +\frac { 1 }{ 5! } -....=1-\frac { 1 }{ e } =0,632120558$$
$$P({ B }_{ \infty })=\frac { 1 }{ e } =0,367879441$$
Leonhard Euler calcula as probabilidades para A e B ata n=15 e conclúe que cando o número de cartas supera as 12, as cifras decimais dadas anteriormente xa non varían. Lembremos que o noso problema orixinal falaba de 14 profesores polo que a resposta está suficientemente calculada.
Para disfrutar de Euler:
The Euler Archive
Euler. El maestro de todos los matemáticos, Dunham, William, Editorial Nivola (2000)
Leonhard Euler calcula as probabilidades para A e B ata n=15 e conclúe que cando o número de cartas supera as 12, as cifras decimais dadas anteriormente xa non varían. Lembremos que o noso problema orixinal falaba de 14 profesores polo que a resposta está suficientemente calculada.
Para disfrutar de Euler:
The Euler Archive
Euler. El maestro de todos los matemáticos, Dunham, William, Editorial Nivola (2000)
Ningún comentario:
Publicar un comentario