Quadrato infetto

[MindFlyer]

Abbiamo una scacchiera $ n\times n $, in cui inizialmente $ n-1 $ delle $ n^2 $ caselle sono infette. Ad ogni secondo, viene infettata ogni casella adiacente ad almeno altre 2 caselle infette.
Dimostrare che esiste almeno una casella che non verrà mai infettata.

[fph]

Era anche sull'ultimo giornalino (19 IIRC).
Carino comunque, sotto a chi tocca con le soluzioni...

[piever]

Essendo le caselle infette iniziali $ n-1 $, resta almeno una riga senza caselle infette. Evidentemente la riga non contaminata non può stare al bordo ma deve stare tra 2 righe. La prima riga non contaminata richiede per essere interamente contagiata almeno $ {\frac{n+3}{2} $ caselle infette iniziali se $ n $ è dispari e $ {\frac{n+4}{2} $ caselle infette se $ n $ è pari. Il caso più conveniente per provare a contagiare tutte le caselle è quindi con $ n $ dispari. A questo punto restano altre $ n-3 $ righe da infettare con $ {\frac{n-5}{2} $ caselle infette ancora disponibili. Essendo che 3 righe sono interamente infette servono $ {\frac{n-3}{2} $ caselle infette per contagiare tutta la scacchiera, visto che con una casella infetta si possono contagiare 2 righe. Ma con qualsiasi $ n $ intero positivo si ha che $ {\frac{n-5}{2}<{\frac{n-3}{2} $ perciò $ n-1 $ caselle infette iniziali non bastano a infettare tutte le caselle. Di conseguenza resta almeno una casella non contaminata.

[fph]

Evidentemente la riga non contaminata non può stare al bordo ma deve stare tra 2 righe.

uhm... forse intendi dire che "nel caso in cui la riga non contaminata sta sul bordo, la tesi si dimostra facilmente"? Se sì, devi dimostrarlo. O, almeno, in una gara dovresti, se non vuoi perder punti. Queste sono solo questioni di scrittura, ma purtroppo i punti partono facilmente per cose come queste, c'è da stare molto attenti.

La prima riga non contaminata richiede per essere interamente contagiata almeno $ {\frac{n+3}{2} $ caselle infette iniziali se $ n $ è dispari e $ {\frac{n+4}{2} $ caselle infette se $ n $ è pari.

Questo non mi è chiaro perché sia vero. E' una parte abbastanza importante della dimostrazione, quindi andrebbe espansa per benino... ma leggi anche sotto.

Il caso più conveniente per provare a contagiare tutte le caselle è quindi con $ n $ dispari.

Attento, non devi dimostrarlo nel "caso più conveniente", devi dimostrarlo in tutti i casi, devi trattare in qualche modo anche l'altro (dicendo per esempio come si può ricondurre a quello "più conveniente".

A questo punto restano altre $ n-3 $ righe da infettare con $ {\frac{n-5}{2} $ caselle infette ancora disponibili. Essendo che 3 righe sono interamente infette servono $ {\frac{n-3}{2} $ caselle infette per contagiare tutta la scacchiera, visto che con una casella infetta si possono contagiare 2 righe. Ma con qualsiasi $ n $ intero positivo si ha che $ {\frac{n-5}{2}<{\frac{n-3}{2} $ perciò $ n-1 $ caselle infette iniziali non bastano a infettare tutte le caselle. Di conseguenza resta almeno una casella non contaminata.

hmm... qui però supponi di essere già nel caso che tu chiami "più favorevole". In realtà al di fuori delle tre righe iniziali potrebbero già essere successe cose nei "turni" precedenti, e quindi nel momento in cui tu le analizzi potrebbero esserci ben più di $ n-3 $ caselle infette.
In generale se tu provi con un ragionamento di questo tipo riesci a renderti conto del perché la tesi è vera e a trovare qualche utile caso particolare, ma per una dimostrazione che funzioni in tutti i casi devi fare qualcosa di più generale e considerare tutte le situazioni possibili...
Questo poi è un problema con una soluzione un po' "truccosa", forse non è l'ideale per spiegare/capire come si risolvono in generale i problemi di questa razza.

ciao,

[piever]

Evidentemente la riga non contaminata non può stare al bordo ma deve stare tra 2 righe.

uhm... forse intendi dire che "nel caso in cui la riga non contaminata sta sul bordo, la tesi si dimostra facilmente"? Se sì, devi dimostrarlo. O, almeno, in una gara dovresti, se non vuoi perder punti. Queste sono solo questioni di scrittura, ma purtroppo i punti partono facilmente per cose come queste, c'è da stare molto attenti.

Ok, grazie per la dritta (alle gare non ho mai fatto punti con le dimostrazioni, ora so perché): una casella che ha un lato sul bordo e 2 lati adiacenti a caselle non infette oppure 2 lati sul bordo e un lato adiacente a una casella non adiacente non può avere 2 lati adiacenti a caselle infette, ma al massimo 1 (infatti 4-2-1=1).

La prima riga non contaminata richiede per essere interamente contagiata almeno $ {\frac{n+3}{2} $ caselle infette iniziali se $ n $ è dispari e $ {\frac{n+4}{2} $ caselle infette se $ n $ è pari.

Questo non mi è chiaro perché sia vero. E' una parte abbastanza importante della dimostrazione, quindi andrebbe espansa per benino...

Espandiamola un po':il più piccolo contagio che coinvolga la riga incontaminata necessita 2 caselle una di fronte all'altra. Poi, aggiungendo un'altra casella infetta si espande questa zona (che prima coinvolgeva un rettangolo 1x3) a un quadrato 3x3 la cui base aumenta di 2 caselle per ogni casella infetta aggiunta. Per gli n pari avanza una casella (se n è pari allora n-1=1 mod 2) dunque bisogna aggiungere un'altra casella infetta.

Il caso più conveniente per provare a contagiare tutte le caselle è quindi con $ n $ dispari.

Attento, non devi dimostrarlo nel "caso più conveniente", devi dimostrarlo in tutti i casi, devi trattare in qualche modo anche l'altro (dicendo per esempio come si può ricondurre a quello "più conveniente".

Se n è pari allora si ha comunque che $ {\frac{n-5}{2}<{\frac{n-2}{2} $ (infatti con $ {\frac{n-4}{2} $ caselle infette si infettano n-4 righe, poi con un'altra casella si infetta la restante riga).

A questo punto restano altre $ n-3 $ righe da infettare con $ {\frac{n-5}{2} $ caselle infette ancora disponibili. Essendo che 3 righe sono interamente infette servono $ {\frac{n-3}{2} $ caselle infette per contagiare tutta la scacchiera, visto che con una casella infetta si possono contagiare 2 righe. Ma con qualsiasi $ n $ intero positivo si ha che $ {\frac{n-5}{2}<{\frac{n-3}{2} $ perciò $ n-1 $ caselle infette iniziali non bastano a infettare tutte le caselle. Di conseguenza resta almeno una casella non contaminata.

hmm... qui però supponi di essere già nel caso che tu chiami "più favorevole". In realtà al di fuori delle tre righe iniziali potrebbero già essere successe cose nei "turni" precedenti, e quindi nel momento in cui tu le analizzi potrebbero esserci ben più di $ n-3 $ caselle infette.

Non può esser successo nulla perché le caselle contaminate sono interne al rettangolo nx3 e quindi nessuna casella esterna ad esso può essere adiacente a 2 caselle infette visto che le caselle infette sono su un unico lato. Evidentemente non conta l'ordine di tempo in cui le metto.
Aggiungo un punto che mi ero scordato: se n è dispari e il lato n del rettangolo nx3 non è adiacente al bordo della scacchiera, allora servono $ {\frac{n-1}{2} $ caselle infette per terminare il contagio: con $ {\frac{n-5}{2} $ caselle infette si contagiano le righe a 2 a 2 e così avanzano 2 righe, una sopra una sotto, che richiedono altre 2 caselle infette.

Che fatica! Almeno così andrà bene, spero...

ciao ciao

[MindFlyer]

Era anche sull'ultimo giornalino (19 IIRC).

Ops, non l'ho mica visto..

[fph]

Non può esser successo nulla perché le caselle contaminate sono interne al rettangolo nx3 e quindi nessuna casella esterna ad esso può essere adiacente a 2 caselle infette visto che le caselle infette sono su un unico lato. Evidentemente non conta l'ordine di tempo in cui le metto.

uhm... forse non ci capiamo molto, qui avere una lavagna o un foglio sottomano ci aiuterebbe.
Cosa succede se tu hai due piccoli "nuclei" lontani in cui ci sono tante caselle infette vicine, e un po' di caselle infette isolate sparse nel mezzo? All'inizio le caselle infette cominciano ad espandersi a partire da tutti e due i "nuclei", e potrebbero espandersi a macchia d'olio fino a congiungersi... Mi sembra che tu non contempli che possa succedere una cosa di questo tipo, ma dici che al di fuori di una sola area "calda" le caselle infette restano abbastanza stabili.

[piever]

Finalmente le carenze della dimostrazione sono quasi interamente colmate. Se le caselle infette sono tutte all'interno di un quadrato o di un rettangolo ovviamente non potranno uscirne, no? In assenza di foglio provo a fare un esempio con un disegnino. x=casella infetta, o=casella sana

x______x______x______o______x
x______x______x______o______o
x______x______x______o______x
o______o______o______o______o

Ora è ovvio che le caselle infette non potranno uscire all'esterno di quel quadrato 3x3 perché dato un qualsiasi rettangolo (per semplificare considero il quadrato un rettangolo, visto che è un quadrilatero con 4 angoli retti) nessuna casella esterna ad esso potrà avere 2 lati adiacenti ad esso. Per cui quell'area non si può estendere oltre. L'altro nucleo, dopo aver infettato un rettangolo 1x3 non va oltre. Quindi le due aree infette non si possono congiungere. Nella mia dimostrazione le caselle infette dapprima sono riunite nel rettangolo nx3, poi, aggiungendo una casella infetta ogni 2 righe proseguo il contagio nel modo + efficace.
Tornando a quello che tu dici, un nucleo non si espande a macchia d'olio, si espande fino a occupare il più piccolo rettangolo che inizialmente lo delimitava.

[fph]

Finalmente le carenze della dimostrazione sono quasi interamente colmate. Se le caselle infette sono tutte all'interno di un quadrato o di un rettangolo ovviamente non potranno uscirne, no?

Ottima osservazione.
Ma, continuando a fare l'avvocato del diavolo (spero che tu non la prenda male...), nel tuo disegnino effettivamente le caselle infette "escono" dal rettangolo infettando le caselle (1,4) e (3,4) e riempono completamente le prime quattro righe...
E comunque basta una casella ogni tanto (proprio ogni due colonne, per esempio) "sparsa" nell'area in mezzo ai due "nuclei" per ingrandire l'area del nucleo a un rettangolo più grande; non sono troppo convinto che si possa dire che non succede niente al di fuori di una singola area.

(a proposito, prevedo che quando troverai/leggerai la soluzione "ufficiale" ti incavolerai abbastanza )

ciao,

[piever]

Ma, continuando a fare l'avvocato del diavolo (spero che tu non la prenda male...), nel tuo disegnino effettivamente le caselle infette "escono" dal rettangolo infettando le caselle (1,4) e (3,4) e riempono completamente le prime quattro righe...

Sì, non me ne ero accorto. Effettivamente è il sistema con cui pensavo di infettare la maggior parte della scacchiera. Devono esserci almeno 2 spazi a separare i 2 campi infetti. Quello che può accadere all'esterno del rettangolo infetto è stato accuratamente calcolato: il sistema + efficace consiste nel mettere una casella infetta ogni 2 righe, perché, come mi hai fatto venire in mente facendo l'avvocato del diavolo (lavoro per il quale dovrei ringraziarti), se ci sono 2 righe in mezzo il contagio non può avvenire. Quindi, qualsiasi altra cosa avvenga all'esterno del rettangolo, non farà che aumentare il numero di caselle finali non contagiate.
Finalmente una soluzione trovata!!!
Comunque anch'io credo che, appena scoprirò la soluzione ufficiale, prenderò a testate il primo muro a portata di mano.

[MindFlyer]

Finalmente una soluzione trovata!!!

Per quanto mi riguarda, il problema non è ancora stato risolto.