42. Pandemic

[Triarii]

In un laboratorio c'è un vetrino di forma quadrata suddiviso in 100 caselle, 10 per ogni lato. In ogni casella c'è una cellula. Tuttavia in 9 di queste caselle la cellula è infetta da un mortalissimo virus. Sfortunatamente le cellule sane possono contrarre il virus, e quindi diventare infette, se la casella nella quale si trovano è adiacente a 2 caselle contenenti cellule infette (per adiacenti si intende che hanno un lato in comune). Ce la farà il virus a infettare tutte le caselle del vetrino?

[Half95]

Osserviamo che affinché le due colonne e le due righe più esterne siano interamente contagiate c' è bisogno che ci sia almeno una cellula contagiata in ambedue le colonne e in ambedue le righe. Ci bastano due cellule infette da porre in due vertici opposti del quadrato 10x10 per assicurarci di poter infettare tutte queste caselle. Il problema ora diventa di analizzare un quadrato 8x8 avendo a disposizione 7 cellule infette. Il ragionamento fatto sopra si può rifare anche in questo caso e continuare fino a che non otterremo un quadrato 3x3 che deve essere infettato con solo due cellule. A questo punto possiamo dire che le due cellule infette potranno essere posizionate in soli due modi se vogliamo infettare altre cellule:
1. hanno un vertice in comune e quindi riescono ad infettare solamente un quadrato 2x2
2.giacciono sulla stessa riga o sulla stessa colonna ma non sono adiacenti: riescono ad infettare solamente un' altra cellula.
Pertanto il virus non riuscirà ad infettare tutte le cellule.

[Triarii]

Mi pare funzioni A te il prossimo!

[darkcrystal]

Uhm, mi permetto di dissentire... chi ti dice che quello di mettere due cellule contagiate in due angoli opposti sia il modo migliore? A priori (poi non è vero, ma perché si dimostra in un altro modo) potresti anche voler mettere tutte e nove le cellule infette sul bordo: se per caso ti bastassero a contagiare tutto il bordo, ad esempio, a quel punto avresti vinto (forse "perso" è più adatto, dato il testo...), perché se tutto il bordo è contagiato è chiaro che il contagio si diffonde dentro. Insomma, o dimostri che non si può fare meglio che mettere due cellule infette in due caselle opposte, oppure devi trovare un altra strada. E c'è un'altra strada talmente carina che vale sicuramente la pena di cercarla...

[maurizio43]

.... potresti anche voler mettere tutte e nove le cellule infette sul bordo: se per caso ti bastassero a contagiare tutto il bordo, ad esempio, ....., perché se tutto il bordo è contagiato è chiaro che il contagio si diffonde dentro. ......

Veramente mi sembra che se tutto e solo un bordo è contagiato il contagio dovrebbe fermarsi lì .
Comunque è facile vedere che, se si parte da un rettangolo con 2 righe e 4 colonne , il minimo numero di cellule infette che serve per contagiarlo tutto è 3 .
Se poi estendiamo la figura a un quadrato 4x4, accostandole un altro rettangolo identico e "vuoto" , è anche evidente che per il contagio totale occorre un' altra cellula infetta.
E' altresì chiaro che aggiungendo 2 bordi consecutivi 5x1, per estendere a tutto il quadrato 5x5 il contagio serve un'altra cellula infetta nello spigolo in comune tra i due bordi.
Continuando in estensioni analoghe della figura si vede che resta sempre il legame : n cellule infette per provocare la pandemia in un quadrato n x n

[FrancescoVeneziano]

Maurizio, questa argomentazione ha lo stesso errore di quella di Half95: tu assumi che la configurazione "migliore" per il quadrato 4x4 sia ottenuta giustapponendo la configurazione "migliore" per il rettangolo 4x2 con un altro rettangolo 4x2, ma questo non deve essere necessariamente vero. Potrebbero esserci due caselle sul rettangolo 4x2 che da sole non riescono a riempirlo ma che, insieme ad una terza casella sul secondo rettangolo 4x2 riescono a riempire tutto il quadrato 4x4.

Quando darkcrystal diceva "tutto il bordo" intendeva tutti e 4 i lati.

[maurizio43]

.... Potrebbero esserci due caselle sul rettangolo 4x2 che da sole non riescono a riempirlo ma che, insieme ad una terza casella sul secondo rettangolo 4x2 riescono a riempire tutto il quadrato 4x4.

Stai dicendo che non ho dimostrato l' impossibilità di questa terza casella così utile, vero ? Non che ci possa veramente essere !

[Half95]

E c'è un'altra strada talmente carina che vale sicuramente la pena di cercarla...

un aiutino???

[Triarii]

Bon non so se dovrei pubblicarlo, però tanto vale

Testo nascosto:

Cosa è che non aumenta quando una cellula viene infetta?

[darkcrystal]

In ordine: il primo aiutino è praticamente ovvio e non vi rovinerà il problema, il quarto è quasi una soluzione, quindi non guardatelo assolutamente a meno che non siate disperati. Dovreste passare almeno un giorno a pensare al problema dopo ogni aiutino (magari tranne il primo)!

Testo nascosto:

"invarianti"

Testo nascosto:

non un invariante, ma una quantità che varia in maniera controllata

Testo nascosto:

in particolare, un "invariante" che diminuisce

Testo nascosto:

pensare al perimetro (di cosa?)

[Triarii]

Uppo per non bloccare la staffetta.
Dai che con gli hint è praticamente risolto

[marconato]

Notiamo che ad ogni infezione, la somma dei perimetri dei poligoni che separano le cellule infette da quelle non infette, non può aumentare. Il perimetro iniziale con 9 cellule infette è al più 36 lati, mentre per infettare tutte le cellule è necessario un perimetro di almeno 40 lati.

[Triarii]

Ok, vai pure