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.

Enllaç al programa

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

Enllaç al programa

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

Continuem l'exploració del problema?

Primeres descobertes

Tant el el cas de 3x3 com el de 4x4 haureu descobert que els mínim de caselles inicials són 3 i 4 respectivament. Però també que no totes les disposicions inicials valen per infectar tot el tauler.

Exemples que NO ho infecten tot

Exemples que SÍ ho infecten tot

Què tenen en comú les disposicions que omplen el tauler? Que cap de les caselles inicials comparteix costat amb cap altra. És condició suficient? No. El tercer exemple de les que no ho omplen tot, no té cap casella amb costats compartits.

Aquestes observacions les podem fer també en taulers de 4x4. Mostrem en verd alguns casos de quatre caselles inicials que no ho infecten tot (i la zona que infecten) i en vermell els que ho infecten tot.

Amb les observacions afegides de l'experimentació en quadrats de 4x4 podem començar a fer conjectures més generals (i afegirem una que no hem comentat abans)

• Per un quadrat de costat n la quantitat mínima de caselles infectades és n.
• Les caselles inicials no poden compartir costats. Com a molt és poden tocar per un vèrtex.
• Les caselles inicials han de "cobrir" tota l'amplada i l'alçada. És a dir, han de tocar els quatre costats del tauler.
• Una distribució d'aquesta mena no garanteix que s'infecti tot el tauler.

Entre totes les distribucions es toquen els quatre costats del tauler

Podem pensar que si fem una distribució amb un sol quadrat infectat a cada columna i a cada fila tindrem el problema resolt. Però no és cert. Als exemples anteriors ja ha aparegut una distribució que acompleix aquestes condicions i no infecta ni una sola casella i una altra que no les acompleix i infecta tot el tauler.

Una qüestió de perímetre

Al llibre de Paenza l'autor fa una observació molt interessant per a justificar que el mínim de caselles inicials infectades en un tauler de n x n és, justament, n. Observem l'evolució d'un parell de casos. En els que ens hem de fixar és en l'evolució del "perímetre d'infecció", és a dir, quin perímetre total tenen les caselles infectades. Té sentit perquè afecta al contagi. I anirem mirant com evoluciona aquest perímetre total en cada estadi de la infecció.

• Cas 1: el perímetre d'infecció inicial no varia.

Cas 2: el perímetre d'infecció inicial disminueix.

No hi ha "cas 3". No trobarem cap cas en què el perímetre augmenti. Això ens dona la justificació de perquè el mínim de caselles inicials infectades són tantes com el costat del quadrat i perquè no han de compartir costats. Si, en el cas de 4x4, el perímetre final és de 16 unitats, la disposició inicial també ha de tenir un perímetre de 16: quatre caselles infectades amb els quatre costats "nets", que no el comparteixin amb una altra casella infectada,

Podem saber a priori si una distribució infectarà tot el tauler?

La resposta és que immediatament no. Sabem quin és el mínim de caselles infectades inicials per a un tauler quadrat i que no han de compartir costats. Però també sabem que totes dues condicions són "necessàries però no suficients". El que sí podem ferm per veure si s'infectarà tot, són observacions zonals i de connexions entre zones.

És evident que el primer que hem de comprovar són les condicions inicial que ja coneixem:

• Si el costat del tauler és n hi ha d'haver n caselles inicials infectades.
• No poden compartir costats.
• Han de tocar-se els quatre costats exteriors del tauler.

Però hi ha una altra condició prèvia: mirar si hi ha alguna primera infecció o no.

Ara ja podem començar l'estudi zonal. Si abans heu experimentat haureu vist que les zones finals (o algunes de la fase intermèdia) sempre tenen forma rectangular, i que el rectangle es pot predir segons la disposició de les caselles inicials.

Dels casos anteriors, tres acaben com estan. Però al 4 veiem una casella de connexió entre les dues zones. Està marcada amb un punt. Aquesta casella, que serà la propera infectada, és la que farà que tot el tauler acabi infectat.

Per tant, per saber si un tauler quedarà totalment infectat hem de fer aquest estudi de zones i, a base de progressives connexions entre elles, esbrinar si el tauler s'infectarà totalment o no. Veiem un parell d'exemples en un tauler de 8x8.

• Exemple 1

• Exemple 2

A l'esquema hem fet les passes de forma progressiva però, amb una mica de pràctica, es poden veure més ràpidament les zones connectades i les que no ho estan.

I a l'aula?

• Encara que no serveix molt com a model d'expansió d'epidèmies com a mínim l'aspecte de la reducció de contacte hi apareix. Això el pot fer interessant de treballar.
• El plantejament de l'activitat no és complicat. Segons l'etapa en la que ho fem podem esperar que l'alumnat vagi més lluny o no en les seves observacions. Amb els més petits es pot plantejar ja inicialment amb taulers més reduïts. Per exemple de 6x6.
• Es poden donar taulers amb distribucions inicials donades i demanar, sense fer tota la "infecció" pas a pas, que justifiquin si s'infectarà tot o no.
• Podem estudiar altres tipus de taulers: rectangulars, amb caselles triangulars o hexagonals...