42. Pandemic

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

42. Pandemic

Messaggio da 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?
"We' Inge!"
LTE4LYF
Half95
Messaggi: 44
Iscritto il: 21 ago 2013, 21:55

Re: 42. Pandemic

Messaggio da 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
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 42. Pandemic

Messaggio da Triarii »

Mi pare funzioni :) A te il prossimo!
"We' Inge!"
LTE4LYF
darkcrystal
Messaggi: 706
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Re: 42. Pandemic

Messaggio da 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...
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: 42. Pandemic

Messaggio da maurizio43 »

darkcrystal ha scritto:.... 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
Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 606
Iscritto il: 01 gen 1970, 01:00
Località: Genova
Contatta:

Re: 42. Pandemic

Messaggio da 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.
Wir müssen wissen. Wir werden wissen.
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: 42. Pandemic

Messaggio da maurizio43 »

FrancescoVeneziano ha scritto:.... 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
Messaggi: 44
Iscritto il: 21 ago 2013, 21:55

Re: 42. Pandemic

Messaggio da Half95 »

darkcrystal ha scritto: E c'è un'altra strada talmente carina che vale sicuramente la pena di cercarla...
un aiutino???
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 42. Pandemic

Messaggio da Triarii »

Bon non so se dovrei pubblicarlo, però tanto vale :)
Testo nascosto:
Cosa è che non aumenta quando una cellula viene infetta?
"We' Inge!"
LTE4LYF
darkcrystal
Messaggi: 706
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Re: 42. Pandemic

Messaggio da darkcrystal »

In ordine: il primo aiutino è praticamente ovvio e non vi rovinerà il problema, il quarto è quasi una soluzione, quindi non guardatelo assolutamente :evil: 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?)
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 42. Pandemic

Messaggio da Triarii »

Uppo per non bloccare la staffetta.
Dai che con gli hint è praticamente risolto :)
"We' Inge!"
LTE4LYF
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: 42. Pandemic

Messaggio da 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
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 42. Pandemic

Messaggio da Triarii »

Ok, vai pure :)
"We' Inge!"
LTE4LYF
Rispondi