Quizzino della domenica: la scacchiera infetta

Avete una scacchiera 12×12, inizialmente con tutte le caselle bianche. Il vostro arcinemico infetta un certo numero di caselle, colorandole di nero. Una casella nera rimane tale: ogni giorno tutte le caselle bianche che toccano per almeno due lati (gli angoli non valgono) caselle nere vengono infettate e si anneriscono anch’esse.

Chiaramente un’unica casella infetta non farà nulla e resterà da sola, come anche succede se si colora di nero un quadrato 11×11. Una colorazione alternata come quella di una scacchiera normale porta invece in un singolo passo all’infezione di tutta la tastiera. Siete in grado di trovare una configurazione col minor numero di caselle inizialmente annerite che infettino tutta la tastiera? Se non sapete dimostrarlo, qual è il numero minore di caselle nere che vi servono?

[una configurazione iniziale]

(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p172.html; la risposta verrà postata lì il prossimo mercoledì. Problema tratto dal libro di Béla Bollobás The Art of Mathematics: Coffee Time in Memphis)

3 comments

  1. Che dici del libro di Bollobas, vale la pena di prenderlo?
    Dopo che hai pubblicato questo problema ho letto un po’ di lui e mi sembra un personaggio davvero interessante.

    • Non lo so, nel senso che io il libro non l’ho letto (il problemino era apparso due anni fa su Wordplay del NYT, io sono sempre in ritardo…). Penso però che dovrebbe valerne la pena, anche se non lo consiglierei a chi di matematica non ne sa.

  2. a occhio e croce direi che riempire i 12 quadratini di una delle diagonali è sicuramente sufficiente, e se non sbaglio dovrebbe pure essere una configurazione minima. non è nemmeno necessario che la diagonale sia intera (si può spezzare in più parti) ma sempre 12 quadratini devono esserci.