SSSUP 2009 n 4: Arginare un incendio

[Haile]

\begin{OT}

Torbi Gialla

\end{OT}

[karlosson_sul_tetto]

(OT1 begin)

Torbi Gialla

Concordo!! (OT1 end).
(OT2 begin)Come si fa a scrivere nella citazione"Pingo Pallino ha scritto ste scemita:Torbi Gialla".Grazie! (OT2 end)
Nessuno ha dimostrato che con due squadre non si può fare...

[Haile]

Nessuno ha dimostrato che con due squadre non si può fare...

Nessuno, fin'ora. Come ci dice Xamog, è un problema aperto... ovviamente questo non vuol dire che sia irrisolvibile =) Anzi, dimostrare che è irrisolvibile sarebbe... un modo per risolverlo.

[karlosson_sul_tetto]

Scusa,volevo dire "nessuno l'ha scritto".
Nessuno ha risposto al mio secondo OT?

[Tibor Gallai]

Ad esempio, clicca su "riporta" in alto a destra di un post.
Alternativamente, scrivi

Codice: Seleziona tutto

[quote="Pinco Pallino"]bla bla bla[/quote]

[karlosson_sul_tetto]

"Pinco Pallino"

Era questo passaggio.Grazie!!

[Xamog]

Il caso $ 2+\epsilon $ viene anche, in modo abbastanza elegante, facendo partire da un punto qualunque due squadre da $ 1+\epsilon/2 $ che percorrono due spirali logaritmiche divergenti in senso opposto, mantenendo costante l'angolo fra la propria direzione di marcia e la direzione del centro dell'incendio,

E infatti questa è la soluzione ufficiale. Mi pare che si dimostri anche che, a meno di omotetie, è la più efficiente.

Credo che se le trincee scavate dai pompieri, alla fine, descrivono una curva chiusa che non si autointerseca, allora i miserrimi siano destinati al fallimento. Insomma, se hanno un modo per circondare l'incendio, allora devono farlo scavando delle isole che verranno circondate dal fuoco, oppure dei moli protesi sulle fiamme.

Hai colto esattamente il punto. L'idea è che in un dominio regolare il "diametro geodetico" (cioè la massima distanza tra 2 punti rimanendo all'interno del dominio) è minore di metà del perimetro. Questo penso che si possa dimostrare, anche se farlo in maniera completamente rigorosa potrebbe essere seccante. In un dominio qualunque invece il "diametro geodetico" è solo minore di una volta il perimetro (e la costante 1 è ottimale, come Katerina ci convincerà con un facile esempio). Questo è un modo per dimostrare che una squadra non basta.

Secondo me potrebbe essere interessante considerare il problema anche in versione discreta, sul piano suddiviso in quadratrini unitari. Il fuoco parte da un quadratino ed al tempo t+1 occupa tutti i quadratini che hanno un lato in comune con quelli occupati al tempo t; i pompieri ad ogni turno tracciano 2 lati e ciascuno di quelli blocca la propagazione del fuoco tra i 2 quadratini che separa.

Sono stato un po' veloce, ma spero di aver reso l'idea. Volevo aprire un topic su questa versione disceta, ma ho un impegno alle 19:00. Penso che la versione discreta liberi da tutte le difficoltà "measure theoretic" del problema originario, permettendo a più persone di pensarci liberamente. Magari poi una buona idea discreta si potrà generalizzare al continuo . Ripeto che l'interesse del problema va ben al di là dell'ambito olimpico.

[Katerina89]

In un dominio qualunque invece il "diametro geodetico" è solo minore di una volta il perimetro (e la costante 1 è ottimale, come Katerina ci convincerà con un facile esempio).

Potrei non aver capito precisamente, nel senso che potrebbe dipendere da come le cose sono definite. Tuttavia, assumendo che le cose siano definite nel modo che serve ai pompieri, allora una spirale dovrebbe andare come controesempio.

Anzi, credo che esista questa soluzione con velocita' 2.5: non serve a niente, ma, secondo me, fa capire che questo problema non e' banale. Parte una sola squadra a velocita', appunto, 2.5, da un punto a caso, e inizia a fare la spirale logaritmica allontatandosi dal centro a velocita' 1. Dopo un po' di giri, si vede che il fuoco, intrappolato nelle spire della spirale, e' un po' rallentato nella sua espansione radiale. Nel senso che al tempo t non arriva piu' a distanza t dal centro, ma a distanza kt per qualche k<1; e questo avviene perche' non puo' piu' espandersi in linea retta, ma deve seguire i giri della spirale. Bene, i pompieri possono, allora, approfittarne per rallentare leggermente la loro corsa in direzione radiale e stringere un po' la spirale. La cosa si ripete e si ripete, e, se i pompieri sono abbastanza veloci - 2.5 dovrebbe bastare, ma ho fatto un conto molto rozzo - riescono a stringere e stringere la spirale fino a chiuderla, e con essa l'incendio. La cosa buffa e' che non possono limitarsi a fare da subito l'ultimo giro della spirale, perche' non ne avrebbero il tempo.

In realta', il fatto che la soluzione di prima, se funziona, non funzioni per velocita' 2 sembra cosi' incidentale, che non mi stupirei se qualche sua parente fosse piu' fortunata... Non sto facendo un'affermazione molto sensata matematicamente, ma voglio dire che sembra sfruttare un fenomeno che la soluzione del $ 2+\epsilon $ non sfrutta, per cui sembra suggerire la possibilita' di fare di meglio. C'e' qualche argomento a favore dell'impossibilita' del 2, salvo il fatto che bisogna non fare una curva chiusa coi pompieri?

Cia' eh raga!

[Tibor Gallai]

Eh, in effetti dalle costruzioni di quel tipo si vede che non è così assurdo strategicamente fare degli "sbarramenti intermedi" interni al poligono esterno per rallentare il fuoco. Anche se mi sembra più o meno intuitivo che sotto una certa velocità questo diventi davvero inutile. Ma non so bene come convincere qualcuno di questa intuizione.