Diffusione

[axpgn]

Supponiamo di avere una scacchiera $10 xx 10$.
Nove celle di questa scacchiera sono infette.
Ad ogni unità di tempo, una cella che abbia almeno due celle vicine infette si infetta anch'essa (celle vicine significa che hanno un lato in comune).

Può l'infezione estendersi all'intera scacchiera?


Cordialmente, Alex

[Drazen77]

Credo ce ne vogliano almeno 11

[axpgn]

O sì o no.

Dimostrandolo


Cordialmente, Alex

[Drazen77]

"Drazen77":Credo ce ne vogliano almeno 11

Anzi 10

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Non necessariamente, se le celle infettate sono tutte sulla riga \(1\), la riga \(2\) non si infetta mai perché hanno sempre solo un solo lato in comune.
Non ho guardato però se esiste una configurazione di 9 celle infette che infetta tutta la scacchiera.

[Quinzio]

No.

Direi che la configurazione migliore (o peggiore se preferite) per infettare tutte le celle sia avere le prime celle infette sulla diagonale $\delta_{i, j}, $ con $ i,j \in [1,10]$.
$\delta$ e' il delta di Kroneker.
Infatti queste celle infettano le celle (con $ i,j \in [1,10]$)
$\delta_{i-1, j}$ e
$\delta_{i, j-1}$
e poi (con $ i,j \in [1,10]$)
$\delta_{i-2, j}$ e
$\delta_{i, j-2}$.

Ma la diagonale di partenza deve essere completa, altrimenti anche le altre diagonali saranno incomplete.
Quindi servono almeno 10 celle infette disposte sulla diagonale.

Spiegazione alternativa e piu' "aulica".
Sia ${C_{i,j}}$ un gruppo di celle infette.
Siano ${i}$ e ${j}$ gli insiemi degli indici $i$ e $j$ rispettivamente delle celle del gruppo.
Siano $i_m$ e $i_M$ rispettivamente il minimo e il massimo dell'insieme ${i}$.
Idem per ${j}$.
Se gli insiemi ${i}$ e ${j}$ formano due intervalli, ovvero
$\forall k\in [i_m, i_M]: k \in {i} $ e
$\forall k\in [i_m, j_M]: k \in {j} $,
si puo' dimostrare che il gruppo di celle infettera' l'intero rettangolo sulla scacchiera di coordinate:
${i} \times {j}$.
Conclusione: servono almeno 10 celle, altrimenti si infetta al massimo un rettangolo 9x9 con 9 celle infette di partenza.

[axpgn]

@Quinzio

Se ho capito bene, hai dimostrato che esistono particolari configurazioni, aventi inizialmente $10$ celle infette, le quali portano alla diffusione dell'infezione all'intera scacchiera.
Ma ciò non esclude che ne possano esistere alcune con sole $9$ celle inizialmente infette e che conducano all'infezione completa della scacchiera.

Cordialmente, Alex

[Quinzio]

@Alex

No, scusami, mi sono espresso in un modo pessimo.
Per infettare una scacchiera 10x10 servono almeno 10 celle di partenza.

La mia tesi e' proprio che non e' possibile infettare una scacchiera $n times n$a partire da $n-1$ celle infette.

Considerando casi banali come la scacchiera $2 times 2$ o $3 times 3$, si vede che non e' possibile semplicemente provando tutte le combinazioni.

Ma nel caso generale, quella specie di teorema che ho enunciato prima, serve proprio a dimostrare che un gruppo di $n$ celle riesce al massimo ad infettare un quadrato $n times n$.

Ho voluto metter giu' quel teoremino in forma rigorosa, ma forse per questo e' anche molto criptico.
In altre parole dice che:
su una scacchiera ci sono delle celle infette di partenza.
Preso un qualunque gruppo di queste celle, le celle infettano il piu' piccolo rettangolo che le contiene a patto che:
su ogni riga del rettangolo ci sia una cella infetta, e su ogni colonna del rettangolo ci sia una cella infetta.
Ora, su una scacchiera da $10 times 10 $ celle, se ci sono 9 celle infette di partenza, queste non riusciranno mai a infettare tutta la scacchiera, perche' ci sara' sempre una colonna e una riga vuota.
Dimostrare il teoremino non deve essere troppo difficile, ma non ho la dimostrazione pronta (e' abbastanza intuitivo).

Ad esempio nella scacchiera sottostante il gruppo di celle A,B,C non riesce a infettare il rettangolo (1,1)-(2,5) perche' non c'e' nessuna cella sulla colonna 2.

 12345
1A   C
2   B 
3      
4
5

E' abbastanza intuitivo da vedere. La colonna 2 fa come da linea tagliafuoco per la diffusione.

[axpgn]

@Quinzio

Avevo capito cosa volevi dire (cioè tutte le celle infette stanno in un rettangolo e al massimo possono infettare quel rettangolo, a patto che ci sia almeno una cella per ogni riga e per ogni colonna) però manca la dimostrazione
E quella conta

Cordialmente, Alex

[axpgn]

Ecco la mia dimostrazione ...

Consideriamo il caso di una cella sana avente due celle vicine infette.
Prima dell'infezione, il perimetro della zona infetta è pari a $8=4 xx 2$; dopo l'infezione, il perimetro della zona infetta è ancora pari a $8=3+1+3+1$.
Ovvero non è aumentato.
Nei casi di un cella sana con tre o quattro celle vicine infette, dopo l'infezione, il perimetro dell'infezione è addirittura diminuito.
Dato che il perimetro infetto inziale è pari a $36=4 xx 9$, ne consegue che non potrà coprire tutta l'area del quadrato che ha perimetro $40=4 xx 10$

Cordialmente, Alex

[Folpo13]

"axpgn":
...

Veramente carina come dimostrazione. Penso a pochi sarebbe venuto in mente

di considerare il perimetro delle celle infette

... Almeno a me non sarebbe mai venuto in mente

[axpgn]