19 d’abril del 2020

Tauler infectat

Amb el nom de Tauler infectat apareix al llibre Matemàtica, ¿estas ahí? Episodio 100 aquest interessant problema. No serveix molt com a model de propagació d'epidèmies, però conserva l'aspecte "d'infecció per contacte". El problema és fàcil de plantejar. Imaginem que tenim un tauler de 8x8 en el que algunes caselles estan "infectades".


Casa casella comparteix costats amb quatre caselles més. Si tenim una casella sense infectar que està en contacte amb dues o més caselles infectades també s'infectaran. Així a la imatge següent podem veure quines seran les caselles que s'infectaran a la següent fase. En aquest cas, cada casella nova comparteix exactament dos costats amb infectades.


Aquest procés es va repetint fins que cap casella nova es pot infectar i l'epidèmia s'acaba. Al cas de l'exemple no s'infecten totes les caselles.
Però en aquest altra, amb una disposició i quantitat inicial de caselles infectades diferent, sí que s'acaba amb tot el tauler vermell.

Ja tenim la situació plantejada. Ara venen les preguntes. Per exemple:
  • quina és la quantitat mínima de caselles inicials infectades per poder infectar tot el tauler?
  • és indiferent com estan distribuïdes?
  • observant un disposició inicial, podem predir ràpidament si s'infectarà tot el tauler o no?
Com en molts altres problemes podem investigar-lo fent una reducció: començarem per un tauler de 2x2. Si descartem els casos extrems (una sola casella infectada i tot el tauler) i no tenim en compte simetries i girs tenim tres disposicions inicials.

Aquest cas ja ens dona algunes pistes. En un tauler de 2x2 hi ha un mínim de caselles inicials necessàries: dues. I la disposició sí que importa, perquè si ocupen un costat no hi ha cap infecció nova i sí que hi ha infeccions si ocupen una diagonal.

Ara, abans de continuar, et deixem investigar en taulers de 3x3 i 4x4 amb aquests dos applets fets amb scratch.

Pinta les caselles inicials i prem la tecla "espai" per iniciar

Pinta les caselles inicials i prem la tecla "espai" per iniciar


Continuem l'exploració del problema?

5 d’abril del 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?