Epidemie
Anche stavolta parlo di un problema tratto da Numberplay. Il matematico ungherese naturalizzato britannico Béla Bollobás racconta:
Un’epidemia si sta propagando in una scacchiera 12×12. Inizialmente solo alcune caselle sono infette: una casella infetta lo rimarrà per sempre, e una casella non infetta si infetterà se avrà almeno due caselle confinanti infette. Per “confinanti” si intende “che la toccano su un lato”, quindi una casella ha al più quattro caselle confinanti. Qual è il numero minimo di caselle inizialmente infette che potrà infettare tutta la scacchiera?
Per la cronaca, è possibile partire da una configurazione di ben 132 caselle infettate (tutte tranne la riga superiore della scacchiera) e non riuscire a infettare tutta la scacchiera: è facile vedere che la riga superiore non verrà mai infettata, poiché ogni casella ha solo un vicino infetto. Ma il killer della tastiera può scegliere opportunamente i punti di infezione e usarne molto meno. Volete sapere come?
È abbastanza facile trovare una configurazione di dodici caselle iniziali che porta all’infezione completa: si può per esempio iniziare con una diagonale maggiore. A ogni passo una diagonale vicina viene infettata: al decimo passo pertanto l’epidemia si sarà propagata a tutta la scacchiera. Ci sono però molte altre configurazioni iniziali con dodici caselle che, anche se più lentamente, riescono a infettare tutta la scacchiera. Quella che ho inizialmente trovato io, per esempio, partiva dalle caselle (1,2n) e (2n,1) per arrivare in 21 passi allo stesso risultato. A questo punto sorge spontanea la domanda “ma la soluzione ottimale sarà proprio dodici?”. La risposta è sì; e la dimostrazione è almeno a mio parere bellissima.
Introduciamo innanzitutto il concetto (generale) di monovariante, che è una generalizzazione di quello di invariante. Un invariante, lo sappiamo tutti, è qualcosa che non varia. Un esempio tipico di invariante è la parità, che permette di risolvere facilmente questo gioco stupido. Ci sono i numeri da 1 a 15 a disposizione, e ogni giocatore ne sceglie a turno uno, sommandolo o sottraendolo al risultato precedente: se il risultato finale è dispari vince il primo giocatore, se è pari è il secondo. Il gioco è stupido perché non importa assolutamente quali numeri si scelgono e se li si somma o li si sottrae! In ogni caso il risultato finale sarà pari, perché la parità è invariante cambiando i segni della somma alegbrica. Il monovariante è quasi come un invariante, nel senso che può variare ma solo in una direzione: insomma è qualcosa che non decresce mai (oppure non cresce mai), anche se può restare costante.
Nel nostro problema il monovariante è dato dal perimetro della zona infetta. Immaginiamo di aggiungere una nuova casella infetta: il perimetro aumenta di quattro unità ma bisogna togliere i lati in comune. Se la casella ha due vicini infetti, il risultato netto è nullo (togliamo due lati dalla nuova casella e altri due dalle vecchie caselle); se ha tre vicini infetti il perimetro sarà più breve di due unità; se ha quattro vicini infetti il perimetro sarà più corto di quattro unità. Dunque il perimetro è un monovariante il cui valore può solo ridursi o al massimo restare costante. Ma la configurazione finale (tutte le caselle infette) ha ovviamente un perimetro 48, quello della scacchiera; ergo per poterci arrivare è necessario avere almeno 12 caselle iniziali (nessuna che si tocchi se non al più per un vertice), che danno appunto un perimetro iniziale di 48. Fine della dimostrazione.
Post scriptum: Gary Hewitt ha preparato qui un programmino per vedere il diffondersi di un’epidemia a partire da una certa configurazione di partenza. Per la cronaca, l’epidemia più lenta (ci vogliono 81 passi per riempire la scacchiera) partendo da dodici caselle infette sembrerebbe essere questa:
1,0,0,0,0,0,0,0,0,0,0,1|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,1,0,0,0,0,0,0,1,0,0|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,1,0,0,1,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,1,0,0,0,0,0|
0,0,0,0,0,0,0,1,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,1,0,0,0,0,1,0,0|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,1,0,0,0,0,0,0,0,0,1
Ma è possibile fare di meglio! La configurazione qui sotto parte con 14 caselle infette, ma le occorrono ben 95 passi per completare l’infezione.
0,0,0,0,0,0,0,0,0,0,0,1|
1,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,1|
1,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,1|
1,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,1|
1,0,0,0,1,0,0,0,1,0,0,0|
1,0,1,0,0,0,1,0,0,0,1,0
Non so se ci sia una morale in tutto questo. So però che la dimostrazione qui sopra è sicuramente nel Libro, avrebbe detto Paul Erdős.
Leave a comment