La setmana passada vam plantejar un enigma de probabilitat a les xarxes socials. Es tracta d'una simplificació que vam fer al problema conegut com el problema de Newton-Pepys.

En primer lloc, moltes gràcies als meus companys robòtics del blog Robologs, que em van donar a conèixer el problema. Robologs és un blog que sens dubte recomano a tots els amants dels enigmes i la informàtica.

Novament, m'agradaria remarcar que aquest no és el problema de Newton-Pepys, sinó que es tracta d'una simplificació que vam fer amb la finalitat de fer-lo més didàctic. El problema diu:

1. Què és més probable?

a) Tirar 2 monedes i obtenir com a mínim una cara.
b) Tirar 4 monedes i obtenir com a mínim dues cares.
c) Tirar 6 monedes i obtenir com a mínim tres cares.

2. Quines són les respectives probabilitats?

3. Quina és la probabilitat de tirar "2n" monedes i obtenir com a mínim "n" cares?

A contínuació, proposarem una solució al problema. Si vols pensar-lo, no segueixis llegint.

Resolució

De l'enunciat del problema cal remarcar el "com a mínim", perquè sense aquestes tres paraules el problema seria radicalment diferent.

Sigui $2x$ el nombre de monedes, $x$ el nombre mínim de cares que hem d'obtenir i $P(x)$ la probabilitat d'aconseguir aquest mínim de cares, és fàcil veure que $P(1) = 0.75$, ja que tres dels quatre possibles llançaments tenen èxit:

Imatge via Robologs

En aquest cas és fàcil veure-ho "a ull", però per la resta de casos recorrerem a la combinatòria. Per aquells que no hi estigueu familiaritzats, aquest recurs us pot ser útil.

Què passa per $P(2)$?

Fixem-nos que, en aquest cas, el nombre de possibilitats serà $VR(2,4) = 2^4 = 16$, ja que:

- Importa l'ordre: La possibilitats "C C X X" i "X C X C" són diferents, encara que a efectes pràctics el resultat sigui el mateix.

- Es pot repetir: És trivial, ja que podem treure més d'una cara o més d'una creu.

Vist des d'un altre punt de vista: Hem d'assignar cara o creu a 4 monedes. Cada moneda té 2 possibilitats. Per tant, el nombre total de possibilitats serà $2·2·2·2 = 2^4 = 16$.

Ara bé, en quantes d'aquestes possibilitats hi ha 2 o més cares?

Per calcular això, el que fem és trobar el nombre de possiblitats amb 2, 3 i 4 cares i sumar-ho tot.

Podem trobar el nombre de maneres d'obtenir dues cares triant 2 de les 4 monedes. En aquest cas:

- No importa l'ordre: És el mateix triar la 1a moneda en primer lloc i la 2a en segon que triar la 2a en primer lloc i la 1a en segon.

- No es pot repetir: Trivial, no pots triar una moneda més d'un cop.

Per tant, aquest càlcul el podem fer com $C(4,2)= {4 \choose 2} = {4! \over2!·2!}=6$.

El nombre de possibilitats amb 3 i 4 cares es calcularan de la mateixa manera.

$C(4,2)+C(4,3)+C(4,4)$
$={4 \choose 2}+{4 \choose 3}+{4 \choose 4}$
$=6+4+1=11$ possibilitats.

Per tant, $P(2) = {11\over16} = 0.6875$

Trobarem $P(3)$ de la mateixa manera que $P(2)$.

Nombre total de possibilitats: $VR(2,6) = 2^6 = 64$

Número de possibilitats amb 3 o més cares:
$C(6,3)+C(6,4)+C(6,5)+C(6,6)$
$=2^6-C(6,0)-C(6,1)-C(6,2)=64-1-6-15=42$

Per tant, $P(3)={42\over64}={21\over32}= 0.65625$

Com a conclusió, s'ha observat que el més probable és tirar dues monedes i que surti com a mínim una cara. A mesura que augmentem el nombre de monedes, observem una certa tendència a la baixa.

Passem ara a la generalització del problema. Hem de trobar una funció que determini, en funció de n, la probabilitat de treure n o més cares en tirar 2n monedes.

Heu sentit mai a parlar dels autòmats cel·lulars? D'entrada sembla un concepte una mica estrany...Estem parlant de biologia? Doncs en realitat no, són matemàtiques!

Un autòmat cel·lular és un model matemàtic que consisteix en una sèrie de regles que regeixen el comportament d'un nombre finit de cel·les elementals col·locades inicialment en una xarxa regular. Segons les regles que haguem dictat inicialment, el nostre sistema de cel·les evoluciona d'una manera o una altra.

Posem-ne un exemple senzill:

Tenim un autòmat cel·lular format per vuit cel·les disposades en una mateixa fila. Cada una de les cel·les només pot tenir dos estats, 0 o 1 (el zero és blanc i l'1 és negre).

Inicialment les cel·les tenen l'estat que nosaltres els otorguem, però a l'instant següent aquest estat canviarà depenent del seu entorn, és a dir, depenent del seu estat i de l'estat en que es troben les dues cel·les veïnes (la de la dreta i la de l'esquerra) en l'instant anterior. El patró que segueixen aquests canvis no és aleatori, sinó que ve regit per les regles que imposem.

En la situació que acabem de plantejar poden haver-hi 8 possibles entorns diferents:

Si no coneixem cap llenguatge informàtic amb el que poguem programar un autòmat cel·lular, la manera més fàcil (que no ràpida) és inventar-nos unes regles i anar dibuixant l'estructura en un full quadriculat. Després podem provar de canviar les regles i veure com apareix un dibuix completament diferent!

Un exemple més complex i curiós d'autòmat cel·lular és l'anomenat "Joc de la vida", creat pel matemàtic britànic John Conway al 1970.

Aquest autòmat consisteix en una graella quadrada on cada cel·la pot estar morta o viva, i està envoltada de 8 cel·les veïnes. L'evolució del conjunt ve donada per quatre senzilles normes:

1. Una cel·la viva amb menys de dos veïns vius mor per aïllament.
2. Una cel·la viva amb dos o tres veïns viu continua viva.
3. Una cel·la viva amb més de tres veïns vius mor per sobrepoblació.
4.  Una cel·la morta amb exactament tres veïns vius torna a la vida.

A partir d'aquestes normes i d'una configuració inicial, es poden crear patrons de comportament ben diferents. Depenent de com col·loquem les cel·les vives a l'inici, la població fins i tot pot arribar a extingir-se!

Exemple de patró de Joc de la vida, d'evolució oscil·lant.

Per saber-ne més:
o
- Modern cellular Automata
- Virtual Complexity Lab at Monash University-Cellular Automata (en aquest enllaç trobareu diferents simulacions d'autòmats cel·lulars que podreu modificar)

Com podem calcular les xifres del número PI?

Existeixen diversos mètodes i algorismes matemàtics per calcular les xifres de pi i un dels més curiosos és el mètode de Montecarlo (en honor al Casino de Montecarlo, la capital del joc d'atzar). Vegem-ho:

En Joan és un jugador mediocre que està jugant a dards en un casino. No és un jugador excepcionalment bo, ja que després d'analitzar els seus llançaments hem arribat a la conclusió que la probabilitat que el dard vagi en el punt mig de la diana és la mateixa que vagi en qualsevol altre punt del metre quadrat de la figura:

En resum, en Joan és un jugador que realitza les tirades a l'atzar.

Sigui $n$ el número de llançaments intentats, $m$ el número de llançaments encertats (qualsevol punt de la diana compta per igual), $D$ l'àrea de la diana i $Q$ l'àrea del quadrat. Fixem-nos que, si $n$ és elevat, es complirà la relació següent:

$$\lim_{n\rightarrow\infty}\frac{m}{n}=\frac{D}{Q}$$

Per tant:

$$\lim_{n\rightarrow\infty}\frac{m}{n}=\frac{\frac{\pi}{4}}{1}=\frac{\pi}{4}$$

$$\pi=\lim_{n\rightarrow\infty}\frac{4\times{m}}{n}$$