5 d’abril de 2020

Un joc de cares i creus amb sorpreses (El joc de Penney)

Hi ha problemes que, de vegades, te'ls trobes, no et criden l'atenció i els oblides. I passat un temps, que poden ser anys, te'l tornes a trobar i els trobes superinteressants. I quan comences a investigar... descobreixes que se t'havien passat per alt en un altre moment. Això és que m'ha passat llegint el llibre de Matt Parker "Pifias matemáticas". He trobat un problema que no recordava, però que després he descobert que ja havia vist, com a mínim, tres vegades: com no, a un títol de Martin Gardner, Viajes por el tiempo y otras perplejidades, al Cuaderno de Cultura Científica en un article de Miguel Ángel Morales (@Gaussianos ) o, fins i tot, a una Matiaventura de Clara Grima. Deixem les lamentacions i passem a mirar el joc que genera el problema. Es coneix com el Joc de Penney en honor al seu autor Walter Penney que el va publicar a l'any 1969.

Volem jugar a cara i creu contra una altra persona. Jugar a una sola tirada pot ser molt avorrit. Per tant jugarem apostant (punts, no cal que siguin diners) a una seqüència de tres tirades.  Tenim vuit ternes per triar que són igual de probables, cosa fa pensar que el joc és també equiprobable.


Un cop cada jugador ha triat la seva terna, que han de ser diferents, es comença a tirar la moneda fins que apareix la seqüència triada per un dels dos jugadors, que guanya el punt. A l'animació teniu un exemple de partida.


Potser hauràs observat a la partida d'exemple que, després de sortir dues creus seguides, l'opció CXC ja no podia guanyar. Si teníem dues creus i continuen sortint creus successivament (per exemple CCXXXXXX) guanyarà XXC en el moment que surti una cara, mentre que CXC ja no podrà sortir mai abans que XXC.

Si has entès el joc et recomanem que ara juguis contra l'ordinador. Per començar cada partida nova has de prémer la tecla espaiadora del teu teclat. A continuació tria la teva opció. Recomanem fer un mínim de deu partides.


T'ha anat bé el joc? O sembla que l'ordinador té alguna mena d'avantatge?


Bé. Si has practicat prou estona hauràs observat que l'ordinador té una certa tendència a guanyar. I és que passen dues coses:
  • La primera és que, encara que hi hagi vuit ternes diferents (CCC, CCX, CXC...) i, a priori sembla que totes tenen 1/8 de probabilitats per a sortir, resulta que això no és cert. Sí que ho és per a les tres primeres tirades, però a partir d'aquí, al ser seqüencials, les ternes es van superposant de forma que es va trencant l'equiprobabilitat.
A partir d'XXX, podria guanyar CCX contra XCC?
  • La segona qüestió és que si comparem de dos en dos les diferents ternes, a la majoria de casos, sempre hi ha una que té avantatge sobre l'altre. De fet, de les 28 possibles parelles de ternes només 10 són equiprobables.
Podem mirar un cas senzill. Quina terna pot guanyar fàcilment a CCC? Si apostem per XCC la terna CCC només pot guanyar si surt al principi, perquè, si no passa això, sempre hi haurà una creu abans de dues cares. És un cas molt extrem. La probabilitat de que CCC surti a les tres primeres tirades és d'1/8. Això fa que les probabilitats de XCC siguin de 7/8. Passaria el mateix entre XXX i CXX.

Graf que mostra que només hi ha un camí per arribar a CCC i és sortir de bon principi
L'observació anterior ens dona una estratègia general per triar sempre,si ho fem en segon lloc, una terna millor que el contrari. Només cal mirar les dues primeres tirades de la seva opció. Llavors anteposem una primera tirada diferent i afegim com a segona i tercera les seves dues primeres tries. Mirem exemples:
  • Si tria CXC nosaltres triem XCX
  • Si tria XXC nosaltres triem CXX
  • Si tria XCC nosaltres triem XXC
  • etc.
Bé... no és tan senzill com això. Per exemple, si la primera tria és XCC, quina opció de resposta és millor? CXC o XXC? Què poso al principi, abans de repetir? Ja us avancem que el càlcul de les probabilitats és una mica complicat i, fent espòiler, que és millor XXC (2/3 de probabilitats de guanyar) que CXC (que seria equiprobable).

Donat que calcular les probabilitats teòriques de l'enfrontament de cada parella de ternes no és fàcil, deixem l'explicació per a la part final de l'article, com un afegit (de fet, un llarg afegit). Però sí que ho podem fer experimentalment. Aquí teniu un applet que us permet fer les comparacions. Per a cada prova cal clicar la bandereta. En cada cas podràs triar les ternes i la quantitat de partides a experimentar.


Si us animeu podeu omplir una taula com la següent.



Voleu més sorpreses?

Nosaltres, per omplir la taula, hem fet l'experiment amb 5000 tirades cada vegada. Els resultats apareixen en forma de percentatge de partides guanyades.
Una anàlisi ràpida dels resultats ens mostra, per a cada primera tria, quina és la millor tria de resposta. A la taula estan marcades, de color verd, les que responen a les ternes d'encapçalament de la columna.
Això ho podem resumir en aquesta altra taula on es mostren la primera tria, la tria de resposta i les probabilitats teòriques per a cada cas que, com es pot observar, s'ajusten força a les experimentals. Ja explicarem després com es calculen les teòriques.
Hi ha un parell de regles mnemotècniques per recordar la 2a tria a partir de la 1a:
  • Mirar la moneda el mig, caviar-la i posar-la la primera. Posar a continuació les dues primeres. (Exemple: a CXX la del mig és un X i posarem una C; després posarem CX; quedarà XCX)
  • Posar com a 2a i 3a les dues primeres i posar al davant una opció que no faci capicua. (Exemple: a XCX posem XC i davant una X perquè CXC seria capicua; quedarà XXC

Una de les coses sorprenents és la no transitivitat del joc. Hi ha un cicle de quatre ternes en les que la 1a és més "forta" que la 2a, la 2a que la 3a, la 3a que la 4a i, trencant la transitivitat, la 4a és més forta que la 1a. El gràfic complet és el següent.


I a l'aula?

Tot el que hem vist fins ara és força treballable a l'aula. Si més no a l'ESO. Com sempre en probabilitat, és una bona activitat per posar contra les cordes la nostra intuïció probabilística. Si en aquest camp de la matemàtica aprenem a desconfiar de la nostres primeres idees, ja haurem aprés molt.

La proposta es pot simplificar a una seqüència de dues monedes, però no és tant interessant perquè dels sis aparellaments possibles només dos no són equiprobables.
  • XC guanya a CC (3/4 de probabilitats)
  • CX guanya a XX (3/4 de probabilitats)
Haureu vist que la proposta es basa en la probabilitat experimental. Això és per fer més "universal" educativament l'activitat. Calcular exactament les probabilitats teòriques de cada terna en un enfrontament no és directe. No ho aconsellaria a l'aula més que per a batxillerat. Però a 3r o 4t d'ESO pot ser interessant, en canvi, treballar els grafs que es mostraran a continuació i que serveixen per a representar els "camins" per arribar a cadascuna de les parelles de ternes que s'enfronten. Un d'quests grafs l'hem vist un abans sense que estigui comentat com es fa o com s'interpreta. A continuació sí que ho farem. Són necessaris per quantificar les probabilitats de cada cas i, si més no, ens permeten també una certa ponderació qualitativa d'aquestes probabilitats. Comentarem alguns casos.

Com es calculen les probabilitats de cada aparellament?

Aquesta part, si no la voleu llegir, és prescindible. Entre altres aspectes perquè és dens i perquè només s'apuntaran formes de calcular-les, sense explicacions detallades de tots els casos. La part interessant, per a mi, és el disseny dels grafs que permet calcular-les, ponderar si hi ha casos més fàcils de resoldre que altres i, com a mínim, fer anàlisis qualitatius,

L'algoritme més fàcil per calcular-les és el de Conway (qui si no?). Comparteixo el que diu Gardner: "No tic ni idea de per què funciona; senzillament, produeix el resultats correcte com per art d'encantament". Per això queda per al final. De moment mirem uns mètodes menys màgics però que, confesso, jo no acabo de saber aplicar en tots els casos. Si voleu ajudar em podeu fer correus o comentaris al web.

Observem primer com es fan un parell de diagrames d'arbre per aquest problema.


Als dos diagrames d'exemple s'observa l'aparició de bucles. Calcular les probabilitats pot implicar l'ús de matrius de transició (article de R.S. Nickerson) o anar resseguint cadenes amb més o menys dificultat i utilitzant progressions geomètriques (article al Blogdemaths). Recomano especialment aquest segon article encara que haig de reconèixer que no me'n surto amb tots els diagrames que he provat.

A mi m'agradaria començar per alguns casos senzills i anar augmentant la complexitat.

Mirem aquests dos diagrames. No són difícil d'avaluar qualitativament perquè són simètrics. La línia superior i la inferiors són idèntiques. En tots dos casos les probabilitats són d'1/2 per a cada línia

De fet, el cas CXC contra CXX no cal estudiar-lo amb el diagrama. Les dues primeres tirades són iguals (CX), per tant hi ha un 50 % de possibilitats de treure C  a la següent tirada i un altre 50 de treure X.

La següent proposta de càlcul de probabilitats està més basada en observar moments del camí i decidir la via de resolució. És una proposta d'Y. Nishiyama en un article del 2012. Posa tres exemples molt clars. El primer ja l'hem comentat.
  • CCC contra XCC

  • XCC contra CCX
    Aquí es fa un anàlisi previ. Podem observar que abans d'arribar a CCX hem de treure repetidament una successió més o menys llarga de cares (recordeu que si surt una X abans de CC hem perdut. La probabilitats de CCX a la primera serà 1/8, la de CCCX serà 1/16, la de CCCCX 1/32. Per tant el càlcul de la probabilitat total és la de la suma d'aquests casos. Tenim la suma d'una sèrie geomètrica de raó 1/2 i com a primer element 1/8.


  • CCX contra CXC
    En aquest cas utilitza un tercer truc. Aquí sí que ens anirà millor mirar el diagrama del joc.

Primera observació: arribant a CC segur que arribem a CCX més tard o més d'hora, i mai a CXC. Segona observació: no cal mirar des d'inici perquè la situació C és bona pels dos finals. Tercera observació: cal parar molta atenció a que des de CX de la línia inferior es pot tornar a l'inici. Ara anomenem x a la probabilitat d'arribar a CC. Des de C la probabilitat d'arribar a CC és la suma d'arribar directament (1/2 si surt cara) més la de tornar a l'inici, si surt creu, i tornar a començar. Per a tornar a l'inici des de C cal una creu i una cara (1/4 de probabilitat). Però com que comencem de nou i ens pot passar diverses vegades anar per aquest via, la probabilitat d'aquest tram serà 1/4 · x. Això ens permet plantejar i resoldre una equació per esbrinar aquesta x.
Bé... s'ha de mirar cas a cas quin dels tres mètodes aplicar i, com a mínim, a mi em passa que faig molts errors pel camí.

Hi ha un article de Juan M.R. Parrondo del Grup Alquerque que també és interessant. Explica el mètode directament per a diagrames que no són simètrics. Seguirem també el seu mateix exemple, XCC contra XXC. 


Tradueixo el text de l'article directament: "la seqüència XXC té una probabilitat 1/2 de guanyar,
mentre que l'XCC només té una probabilitat 1/4, ja que necessita dues cares seguides. Per tant, la
probabilitat que XXC guanyi és el doble de la de XCC, és a dir, jo guanya amb una probabilitat 2/3 i XCC amb una probabilitat 1/3."

Els casos i mètodes que he presentat més o menys els he anat seguint, però reconec que quan els intento aplicar a casos com el de la imatge no me'n surto gaire.

En aquest cas, però, podem fer una anàlisi qualitativa. Per exemple, podem valorar que les probabilitats de cada terna no estan lluny d'1/2, ja que hi ha força simetria entre la línia superior i la inferior. Però que CCX té un lleuger avantatge perquè un cop arribem a CC ja guanyarà segur: es poden anar repetint cares totes les vegades que passi, però a la primera creu ja s'hi arribarà a CCX, i sense opcions intermèdies per arribar a XCX. A més, el bucle a "...X" és anterior al de "...CC" i des d'XC s'arriba també a CC que hem vist que és "definitiu". Per tant, tot porta a pensar en què CCX és millor opció. Efectivament, si mirem els resultats experimentals veurem que és d'un 62,56% per a CCX per un 37,44% d'opcions per a XCX. Les teòriques ho confirmen ja que són de 5/8 i 3/8 (60 i 40 %) respectivament. Tal com havíem dit "prop de la meitat".

Per a calcular les probabilitats teòriques, el mètode general que és fàcil i no falla, encara que ben poc transparent, és el de John H, Conway. El podeu mirar explicat en la següent presentació. I si voleu podeu mirar la justificació a l'article de Nishiyama.



Aplicant de forma repetida aquest algoritme no és difícil omplir la taula completa per a comparar les probabilitats en els enfrontaments de cada parell de ternes.


Bé. Heu arribat al final? Un joc sorprenent, no?



Cap comentari:

Publica un comentari