Ciao. Questo alcuni di voi dovrebbero averlo già visto...
4) In una piccola citta`ci sono $ n^2 $ case sistemate in un quadrato nxn chiamate $ (i,j) $ dove $ i $ e` l'indice della riga e $ j $ quello della colonna, che vanno da $ 1 $ a $ n $ spostandosi da in alto a sinistra a in basso a destra. In un certo istante $ 0 $ la casa $ (1,c) $ con un certo $ c <= n/2 $ si incendia. Da allora in poi, i pompieri occupano l'intervallo lungo $ 1 $ tra $ n $ e $ n + 1 $ per mettere al sicuro una casa che non fosse in fiamme all'istante $ n $, mentre il fuoco si trasmette a tutte le case vicine a quelle in fiamme allo stesso istante $ n $ (due case sono vicine se sono successive in una riga o in una colonna). Una casa messa al sicuro non puo` mai piu` incendiarsi e il tutto finisce quando il fuoco non puo` piu`raggiungere nuove case. Quante case al massimo possono essere salvate dalle fiamme?
Per gli stagisti: chi è riuscito a risolverlo? la strategia ottimale è abbastanza facile da capire, ma non sono riuscito a dimostrare che non si potesse fare di meglio.
Scacchiera in fiamme
Bel problema. Tricky tricky. Facile da vedere, difficile da spiegare. Io seguirei una strada del genere:
-------------------------------
Per semplificarci la vita e non doverci preoccupare degli "effetti di bordo", possiamo supporre che la città sia una striscia di $ \scriptstyle n $ case (ossia si Estenda infinitamente sul lato Sud (l'incendio parte dal lato Nord). Risulterà chiaro che su una città quadrata abbastanza grande(*), il lato Sud non viene mai raggiunto e quindi è ininfluente ai fini della strategia ottimale.
[(*) "Abbastanza grande" in questo caso significa almeno 2. Ma per $ \scriptstyle n=1 $ il problema è banale.]
Definiamo la distanza di una casa [dall'incendio], come il numero di turni che l'incendio impiega a raggiungerla in assenza di interventi da parte dei pompieri.
Dopo qualche spippolamento si trova una strategia che ha tutta l'aria di essere quella ottimale, che brucia $ \scriptstyle c(n-c+1) $ case: ogni volta i pompieri bonificano la casa immediatamente a Sud dell'incendio, nella colonna scelta così: partendo dalla colonna $ \scriptstyle c $ e scegliendo sempre la colonna più vicina non ancora bonificata, alternativamente a Est e ad Ovest (indifferente con quale si inizia). Dopo aver bonificato $ \scriptstyle n $ case, l'incendio si ferma.
La linea dimostrativa che suggerisco è questa:
- mostrare che la mia strategia salva 1 casa a distanza 1, 2 case a distanza 2, ... $ \scriptstyle n $ case a distanza $ \scriptstyle n $. [facile]
- mostrare che non è possibile salvare più di $ \scriptstyle d $ case a distanza $ \scriptstyle d $, per $ \scriptstyle d = 1, \dots, n $. [rognosetto]
Facendo il conto delle case ad una data distanza $ \scriptstyle d $, si vede che effettivamente il conto torna: se i pompieri salvano esattamente $ \scriptstyle d $ case a distanza $ \scriptstyle d $, bruciano proprio $ \scriptstyle c(n-c+1) $case.
Per dimostrare il punto rognoso, utilizzerei un "incendio a senso unico", cioè un incendio che si trasmette solo da case con distanza $ \scriptstyle d $ a case con distanza $ \scriptstyle d+1 $ (l'incendio non può mai aggirare case bonificate, in un certo senso...).
L'incendio a senso unico è meno pericoloso dell'incendio vero; se dimostro il claim rognoso per il pigro incendio a senso unico, a maggior ragione varrà per il più cattivo incendio originario.
Per visualizzare meglio la situazione, è utile disegnare un grafo ad albero delle case, organizzando i nodi in $ \scriptstyle n $ colonne (rispecchiando le colonne originali), ma allineando le case alla stessa distanza. La radice sarà il focolaio iniziale e congiungiamo le case con archi in base alla trasmissibilità dell'incendio pigro.
Risulta quasi un'albero binario: le case in colonna $ \scriptstyle c $ sono congiunte ognuna con le tre case a Sud, Sud-Ovest e Sud-Est; le case ad Ovest sono congiunte con le due case a Sud e a Sud-Ovest (salvo che abbiamo raggiunto il bordo Ovest); analogamente ad Est.
Con questa nuova topografia, all'inizio brucia la radice e i pompieri, al loro $ \scriptstyle t $-esimo turno bonificano una casa con distanza almeno $ \scriptstyle t $ (le case più vicine all'incendio sono già bruciate. Quando bonificano una casa, è possibile che creino una "zona d'ombra" a Sud di essa (=nei livelli successivi dell'albero) di case che non sono più raggiungibili dall'incendio. E' ovvio che ai pompieri non conviene mai salvare una casa in una zona d'ombra, dato che perdono solo tempo.
Il fatto è che le zone d'ombra non si allargano mai (alla peggio, si stringono!) e se la sezione di una zona d'ombra è larga $ \scriptstyle k $, ci devono essere [almeno] $ \scriptstyle k $ case bonificate dai pompieri a Nord rispetto la sezione.
In questo modo se - fissato $ \scriptstyle d \leqslant n $ - all'istante $ \scriptstyle d $ ci fossero $ \scriptstyle d'>d $ case salvate con distanza $ \scriptstyle d $, i pompieri dovrebbero aver bonificato almeno $ \scriptstyle d' $ case distanti $ \scriptstyle \leqslant d $. Ma all'istante $ \scriptstyle d $ i pompieri hanno bonificato $ \scriptstyle d $ case, cioè troppo poche.
Quindi il claim rognoso è vero: una strategia per fermare l'incendio a senso unico brucia almeno il numero voluto di case. Se esistesse una strategia che ferma l'incendio vero sacrificando meno case, applicando la stessa strategia all'incendio a senso unico darebbe una contraddizione, quindi non può esistere una strategia strettamente migliore di quella che ho descritto. []
-------------------------------
Per semplificarci la vita e non doverci preoccupare degli "effetti di bordo", possiamo supporre che la città sia una striscia di $ \scriptstyle n $ case (ossia si Estenda infinitamente sul lato Sud (l'incendio parte dal lato Nord). Risulterà chiaro che su una città quadrata abbastanza grande(*), il lato Sud non viene mai raggiunto e quindi è ininfluente ai fini della strategia ottimale.
[(*) "Abbastanza grande" in questo caso significa almeno 2. Ma per $ \scriptstyle n=1 $ il problema è banale.]
Definiamo la distanza di una casa [dall'incendio], come il numero di turni che l'incendio impiega a raggiungerla in assenza di interventi da parte dei pompieri.
Dopo qualche spippolamento si trova una strategia che ha tutta l'aria di essere quella ottimale, che brucia $ \scriptstyle c(n-c+1) $ case: ogni volta i pompieri bonificano la casa immediatamente a Sud dell'incendio, nella colonna scelta così: partendo dalla colonna $ \scriptstyle c $ e scegliendo sempre la colonna più vicina non ancora bonificata, alternativamente a Est e ad Ovest (indifferente con quale si inizia). Dopo aver bonificato $ \scriptstyle n $ case, l'incendio si ferma.
La linea dimostrativa che suggerisco è questa:
- mostrare che la mia strategia salva 1 casa a distanza 1, 2 case a distanza 2, ... $ \scriptstyle n $ case a distanza $ \scriptstyle n $. [facile]
- mostrare che non è possibile salvare più di $ \scriptstyle d $ case a distanza $ \scriptstyle d $, per $ \scriptstyle d = 1, \dots, n $. [rognosetto]
Facendo il conto delle case ad una data distanza $ \scriptstyle d $, si vede che effettivamente il conto torna: se i pompieri salvano esattamente $ \scriptstyle d $ case a distanza $ \scriptstyle d $, bruciano proprio $ \scriptstyle c(n-c+1) $case.
Per dimostrare il punto rognoso, utilizzerei un "incendio a senso unico", cioè un incendio che si trasmette solo da case con distanza $ \scriptstyle d $ a case con distanza $ \scriptstyle d+1 $ (l'incendio non può mai aggirare case bonificate, in un certo senso...).
L'incendio a senso unico è meno pericoloso dell'incendio vero; se dimostro il claim rognoso per il pigro incendio a senso unico, a maggior ragione varrà per il più cattivo incendio originario.
Per visualizzare meglio la situazione, è utile disegnare un grafo ad albero delle case, organizzando i nodi in $ \scriptstyle n $ colonne (rispecchiando le colonne originali), ma allineando le case alla stessa distanza. La radice sarà il focolaio iniziale e congiungiamo le case con archi in base alla trasmissibilità dell'incendio pigro.
Risulta quasi un'albero binario: le case in colonna $ \scriptstyle c $ sono congiunte ognuna con le tre case a Sud, Sud-Ovest e Sud-Est; le case ad Ovest sono congiunte con le due case a Sud e a Sud-Ovest (salvo che abbiamo raggiunto il bordo Ovest); analogamente ad Est.
Con questa nuova topografia, all'inizio brucia la radice e i pompieri, al loro $ \scriptstyle t $-esimo turno bonificano una casa con distanza almeno $ \scriptstyle t $ (le case più vicine all'incendio sono già bruciate. Quando bonificano una casa, è possibile che creino una "zona d'ombra" a Sud di essa (=nei livelli successivi dell'albero) di case che non sono più raggiungibili dall'incendio. E' ovvio che ai pompieri non conviene mai salvare una casa in una zona d'ombra, dato che perdono solo tempo.
Il fatto è che le zone d'ombra non si allargano mai (alla peggio, si stringono!) e se la sezione di una zona d'ombra è larga $ \scriptstyle k $, ci devono essere [almeno] $ \scriptstyle k $ case bonificate dai pompieri a Nord rispetto la sezione.
In questo modo se - fissato $ \scriptstyle d \leqslant n $ - all'istante $ \scriptstyle d $ ci fossero $ \scriptstyle d'>d $ case salvate con distanza $ \scriptstyle d $, i pompieri dovrebbero aver bonificato almeno $ \scriptstyle d' $ case distanti $ \scriptstyle \leqslant d $. Ma all'istante $ \scriptstyle d $ i pompieri hanno bonificato $ \scriptstyle d $ case, cioè troppo poche.
Quindi il claim rognoso è vero: una strategia per fermare l'incendio a senso unico brucia almeno il numero voluto di case. Se esistesse una strategia che ferma l'incendio vero sacrificando meno case, applicando la stessa strategia all'incendio a senso unico darebbe una contraddizione, quindi non può esistere una strategia strettamente migliore di quella che ho descritto. []
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."