L'enigma del virus informatico

[paperino]

Questo, invece, è dedicato a @davydenkovic90, perché è un matematico.

 

Cento computer sono connessi in rete tra loro in una griglia 10x10, come nell'immagine. Inizialmente nove di loro sono stati infettati da un virus. Il virus si diffonde come segue: se un computer qualsiasi è collegato direttamente ad almeno due vicini infetti, verrà infettato a sua volta.

 

Il virus infetterà tutti e cento i computer?

 

L'immagine mostra un possibile esempio di un infezione iniziale,  ma la domanda non chiede cosa succede in questo esempio, bensì cosa accadrà a partire da qualsiasi configurazione iniziale di computer infetti.

 

Hint: La soluzione ha una connessione con π, in onore del giorno del pi greco, che sarà domani.

[paperino]

Soluzione:

 

  Reveal hidden contents

 

No, il virus non infetterà tutti e 100 i computer.

 

La chiave è il perimetro dell’infezione; per perimetro, si intende la lunghezza del confine dell’infezione. Affinché l’infezione si estenda a tutti i computer il perimetro finale deve essere 40 (perimetro di un quadrato 10x10).

 

Si noti che l’infezione può essere composta da una singola area o da più aree separate. In quest’ultimo caso dobbiamo combinare i perimetri di tutte le aree infette.

 

Il perimetro di un singolo computer infetto è 4, come da figura. Quindi il perimetro di 9 computer infetti sarà al massimo 36, cioè 4x9. (Nel caso in cui nessuno dei computer infetti sia adiacente).

 

 

Il fatto è che il perimetro della stessa non cresce mai con il diffondersi dell’infezione. Si pensi a cosa succede quando un computer non infetto viene contagiato da altri due computer. Due dei suoi lati sono assorbiti in una singola area infetta e gli altri due diventano parte del perimetro della stessa: il perimetro diminuisce di 2 e aumenta di 2, la variazione netta è 0. Per esempio si veda la griglia qui sotto: in A, l’area infetta ha un perimetro di 8; in B, un nuovo computer è contagiato ma il perimetro resta 8; in C, un altro computer contrae il virus ma il perimetro resta 8.

 

Se un computer sano viene contagiato da tre computer, tre lati vengono assorbiti dall’infezione e il suo quarto lato diventa parte del perimetro: in totale il perimetro si riduce di 2. E se un computer sano contrae il virus da quattro computer, la diminuzione del perimetro è 4.

 

In conclusione, se il perimetro di nove computer infetti è al massimo 36, e questo non può aumentare, non potrà mai diventare 40 e, di conseguenza, l’infezione non si può diffondere a tutti i computer.