March 13, 20179 yr 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.
March 15, 20179 yr Author Soluzione: 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.
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.