SSSUP 2009 n 4: Arginare un incendio

[karlosson_sul_tetto]

A dire la verità non ho capito quasi niente di quello che hai scritto!
Velocita:5 al min
1 sq ins 2 sq.:
0,-1;10,-1;19,10;se ne va sq 2.;24,10;29,10;34,10;39,10
3sq.:
0,-1;-5,-1;-10,-1;si aggiunge sq. 2;-25,-1;-25,9;(ho perso il conto ma ci provo lo stesso...)-25,29;-25,39.
Quindi abbiamo la situazione del 5 con tre lati fatti.

[Tibor Gallai]

A dire la verità non ho capito quasi niente di quello che hai scritto!

Oh Gesù Bambino, questo non mi rende molto gaio, devo dire.

In che senso non capisci? E' per colpa delle coordinate? Sai cos'è un piano cartesiano? Vedi qui:
http://it.wikipedia.org/wiki/Sistema_di ... cartesiano

[karlosson_sul_tetto]

No!
Volevo dire che lo schema che hai fatto presenta "buchi",o non ho capito bene.

[Tibor Gallai]

Volevo dire che lo schema che hai fatto presenta "buchi",o non ho capito bene.

Non presenta buchi, per convincerti segui contemporaneamente le prime 2 squadre.
Squadra 1 va da (0,-1) a (10,-1), e intanto squadra 2 va da (10,-1) a (20,-1).
Poi squadra 1 va da (20,-1) a (20,9), e intanto squadra 2 va da (20,9) a (20,19).
Etc etc...
Squadra 1 e 2 fanno tutta la parte di destra del rettangolo, squadra 3 e 4 fanno in modo simmetrico la parte sinistra.

[karlosson_sul_tetto]

Ah,scusa Tibor.
P.S. la risposta del tre è giusta?

[Tibor Gallai]

P.S. la risposta del tre è giusta?

Purtroppo non capisco la notazione. Puoi spiegare la soluzione a parole? O anche solo semplicemente definire la notazione...

[karlosson_sul_tetto]

Non te ne andare,faccio lo schema come nel 4.

[Tibor Gallai]

Non te ne andare,faccio lo schema come nel 4.

Non mi muovo!

[karlosson_sul_tetto]

Ecco qua:

(poi diventa la situazione con 5 squadre e un lato finito).

[Tibor Gallai]

Ok, ho capito quello che vuoi fare, e ti dico che l'idea è ottima. Ora, al di là della costruzione specifica che hai disegnato, e per la quale andrebbero fatti dei calcoli che dimostrino che davvero funziona, si può vedere che una sua opportuna "estensione" funziona anche senza nessun calcolo!

L'idea che suggerisci è di utilizzare inizialmente squadra 1 e 2 come nella soluzione del caso con 4 squadre, fino ad arrivare ad una situazione con squadra 1 "salva", che va verso l'alto.
A quel punto squadra 2 abbandona squadra 1 e va da squadra 3, che nel frattempo stava andando in orizzontale verso sinistra. Rifanno il giochino, ma tutto scalato e ingrandito di un opportuno fattore. Il fattore va scelto così grande da rendere trascurabile il vantaggio che il fuoco ha accumulato nella 1^ fase. Questo si può fare perché abbiamo dimostrato che la costruzione con 4 squadre ci dà un margine di salvezza non nullo.
Quando anche squadra 3 è salva e sta andando verso l'alto, squadra 2 va abbastanza lontano e costruisce l'ultimo lato.

Quindi benissimo. Ora non ti montare la testa, ma credo che tu abbia un potenziale olimpico gigantesco. Ti faccio tanti auguri.


P.S. Ah, per finire, qualcuno dimostri che con 2 squadre non è possibile arginare il fuoco. Decisamente più facile, mi sembra...

[karlosson_sul_tetto]

Quindi benissimo. Ora non ti montare la testa, ma credo che tu abbia un potenziale olimpico gigantesco. Ti faccio tanti auguri.

Be grazie!!
Però dimostrare la"non possibilita"non è il mio forte...
Forse penso e se mi viene qualche idea te la do.

[Xamog]

P.S. Ah, per finire, qualcuno dimostri che con 2 squadre non è possibile arginare il fuoco. Decisamente più facile, mi sembra...

Ehm, per quanto ne so io questo è un problema aperto. Quello che si sa è che

• $ 2+\epsilon $ squadre bastano (una $ \epsilon $ squadra è ovviamente una squadra che lavora a velocità $ \epsilon $): una costruzione possibile è sostanzialmente il rettangolone asimmetrico che gira in un po' di post precedenti;
• una squadra non basta (questo è stato dimostrato, ma la dimostrazione non è per nulla ovvia);
• quello che succede tra 1 e 2 non si sa ancora.

Se qualcuno ha qualche idea per dimostrare l'impossibilità del 2, o anche solo dell'$ 1+\epsilon $, si faccia vivo.

L'importanza e la ricaduta della cosa andrebbe ben oltre l'ambito olimpico.

[Tibor Gallai]

Haha! Grazie, Xamog!
Ho visto malissimo.
In realtà avevo pensato velocemente a una cosa tipo: nell'ipotetica situazione "finale" col fuoco arginato, ogni segmento di fuoco dovrà essere circondato da argini di lunghezza più che doppia. Ovviamente questa cosa da sola non risolve il problema, anche se mi era parso momentaneamente di sì.
Chiedo venia.

Qualche riferimento per il caso con 1 squadra?

[Katerina89]

Ciao eh!

Oggi Torbi Gialla mi ha raccontato questo problema. Quelle che seguno sono le due cose che mi e' capitato di mettere insieme in un viaggio in treno:

1 - 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 scegliendo questo angolo in modo tale da allontanarsi dal centro a velocita' 1. Chiaramente spezzatando tutto quanto nella maniera opportuna, se il problema ci impone che quelle debbano fare dei tratti rettilinei anziche' delle curve, etc.

1.5 - A Torbi l'avevo gia' detto, ma tanto il punto 1 non e' interessante.

2 - Caso $ 2-\epsilon $. Ovviamente non so come mostrare che non bastano, ma posso mostrare che se ce la fanno devono fare qualcosa di piuttosto buffo. 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. E questo, ammettiamolo, e' controintuitivo.

Perche'?

Bah, insomma, non ne sono certissima, ma mi pare che si possa dimostrare questo fatto: consideriamo un sottoinsieme chiuso F (per Fuoco) del piano semplicemente connesso, e consideriamo un punto P nella sua parte interna. Consideriamo, adesso, un altro punto Q di F, e la curva piu' breve $ \gamma $ che connette P a Q passando dentro F. Ok, non e' detto che ci sia, ma se F e' abbastanza bello c'e', e le nostre squadre, se ho capito bene, fanno dei poligoni, che sono abbastanza belli. In un intorno di P, la curva $ \gamma $ e' un segmento di retta. Prolunghiamo $ \gamma $ a partire da P, in linea retta e dalla parte opposta, finche' non incontra il bordo di F, diciamo in R. Sostengo che la nostra e' la piu' breve curva che connette R a Q passando dentro F.

Ora, posto questo, supponiamo che i pompieri ottengano, alla fine, un bel recinto attorno all'incendio senza isole nel mezzo: una curva chiusa. Allora, la porzione di piano in cui divamperanno le fiamme e' semplicemente connessa. Prendiamo come P il centro dell'incendio, e come Q l'ultimo punto del recinto ad essere completato. E' chiaro che la linea RQ taglia il recinto in due meta', ciascuna delle quali e' lunga almeno quanto la linea RQ stessa. D'altro canto questa e' piu' lunga di PQ, etc.

Ne segue, se non ho sbagliato, che se pochi pompieri possono farcela, allora non possono limitarsi a circondare l'incendio. In qualche modo, devono sacrificare parte del loro lavoro alle fiamme.

Cia' eh!

[Tibor Gallai]

Bah, insomma, non ne sono certissima, ma mi pare che si possa dimostrare questo fatto: consideriamo un sottoinsieme chiuso F (per Fuoco) del piano semplicemente connesso, e consideriamo un punto P nella sua parte interna. Consideriamo, adesso, un altro punto Q di F, e la curva piu' breve $ \gamma $ che connette P a Q passando dentro F. Ok, non e' detto che ci sia, ma se F e' abbastanza bello c'e', e le nostre squadre, se ho capito bene, fanno dei poligoni, che sono abbastanza belli. In un intorno di P, la curva $ \gamma $ e' un segmento di retta. Prolunghiamo $ \gamma $ a partire da P, in linea retta e dalla parte opposta, finche' non incontra il bordo di F, diciamo in R. Sostengo che la nostra e' la piu' breve curva che connette R a Q passando dentro F.

Secondo me questo ha qualche speranza di generalizzarsi agli F non semplicemente connessi quando Q è il punto più lontando possibile da P. Però non ho avuto tempo di cercare controesempi, che potrebbero anche essere molto banali... In ogni caso, delle caratterizzazioni "stringenti" sugli eventuali controesempi potrebbero non essere impossibili da trovare, specialmente con l'ulteriore ipotesi che P sia in effetti il centro dell'incendio, e che i giochi non si concludano istantaneamente...