SSSUP 2009 n 4: Arginare un incendio

[karlosson_sul_tetto]

é possibile!
Guarda:il raggio della cinconferenza circoscritta(esterna) equivale al lato del esagono.Quindi,quando il fuoco arriverà ad un vertice anche i pompieri arriveranno nello stesso momento.(non so se mi sono spiegato bene)

[Alex90]

Esatto, quindi se arrivano nello stesso momento in teoria si toccano e quindi si bruciano

[karlosson_sul_tetto]

Bé dai,mica sono kamikaze!!Alla fine vanno velocemente!!
Scerzavo:arriva la muraglia "finita" che resiste al fuoco!

[Tibor Gallai]

Veramente io credo che nel caso di un esagono regolare non sia possibile dato che il lato dell'esagono è uguale al raggio della circonferenza inscritta ed io ho inteso i dati del problema come se non potessero proprio incontrarsi...in pratica.
$ l_p < l_i $ piuttosto che $ l_p \leq l_i $

Intanto è circoscritta e non inscritta, ma credo sia un refuso.
Il punto che sollevi è sensato (complice, manco a dirlo, un testo poco chiaro) e finora non ce ne siamo occupati. Io non l'avevo menzionato per non eccedere in pedanteria, ma l'avevo tacitamente intesa così:
ogni squadra parte da un vertice diverso, e tutte procedono in senso orario.
In questo modo, l'"intervallo di tempo di costruzione" non è [0,1] con l'1 incluso, ma è [0,1) con l'1 escluso. In altre parole, quando il fuoco raggiunge un costruttore, questo si trova in un punto già barricato in precedenza da un altro costruttore, e così si salva. Insomma il fuoco non raggiunge l'argine prima che la costruzione sia finita, ma lo raggiunge quando la costruzione è già finita.
Spero di averti convinto.

[Alex90]

Intanto è circoscritta e non inscritta, ma credo sia un refuso.

Evidentemente

Comunque non saprei, anche così è sensato, in ogni caso alla fine resta comunque un problema che si può tranquillamente non affrontare, basta prendere il poligono non regolare e buonanotte.

[mrossi]

Anch'io ho inteso il problema come Tibor Gallai. Infatti secondo me quel punto del problema voleva fare notare che il caso dell'esagono regolare è il caso limite della strategia poligoni regolari.

Però non sono riuscito a trovare strategie per il caso con 4 squadre ne a dimostrare che non è possibile in alcun modo.

[Tibor Gallai]

Però non sono riuscito a trovare strategie per il caso con 4 squadre ne a dimostrare che non è possibile in alcun modo.

Tu hai fatto il concorso dove c'era questo problema? Sai se qualcuno l'ha risolto ed eventualmente l'ha generalizzato?
Io ho dimostrato che, per la gioia dei piccoli abitanti della foresta incendiata, sono sufficienti (ed ovviamente anche necessarie) solo 3 squadre per domare il fuoco.
Volevo vedere se qualcuno ha trovato costruzioni diverse dalla mia...

Ora comunque siamo ancora al caso di 5 squadre, ed è meglio arrivarci con ordine, secondo me!

[mrossi]

Si ho fatto il concorso ma non ho sentito nessuno che avesse risolto il punto delle 4 squadre...

[Tibor Gallai]

La soluzione del caso con 5 potrebbe dare qualche idea per il caso con 4.
Quindi forza!

[karlosson_sul_tetto]

Teoricamente ho un idea per cinque squadre:
Prendiamo due rette parallele;un punto tra di loro è l'inizio dell'incendio;costruiamo una retta perpendicolare alle due rette e passante per l'inizio dell'incendio;nei punti in cui la retta incrocia le altre due,i pompieri iniziano a lavorare,due squadre per retta:una si muove in una direzione,l'altra nell'altra;la quinta squadra lavora lontano in una delle due "parti" costruendo una retta perpendicolare alle due rette.Cosi,quando il fuoco arriva,la retta è stata costruita,facendo in modo che sia costruito un rettangolo senza un lato;poi le tre squadre costruiscono l'altro lato e aiutano le altre due se c'e bisogno.
Non so se avete capito;non mi sono espresso bene.

[Tibor Gallai]

No, è perfetto.
Via col 4!

[karlosson_sul_tetto]

Dal punto in cui è iniziato l'incendio costruire una retta 2 squadre(sq) per semiretta;poi le quattro sq girano a 90° e costruiscono;poi girano a 90° di nuovo e delimitano l'incendio.

Non so se avete capito;non mi sono espresso bene

[Tibor Gallai]

Ecco, qui però è un po' meno ovvio che funzioni davvero. Ci vorrebbero un po' di dettagli di spiegazione (non voglio dire "dimostrazione"! ).
Per esempio, cerca di esplicitare le coordinate esatte dei vertici del tuo rettangolo (supponendo che l'incendio parta in (0,0)), e poi provvederemo a mostrare che davvero ce la fanno.

[karlosson_sul_tetto]

Va bene:

[Tibor Gallai]

Sssì. Diciamo che ho capito che hai quasi capito, anche se comprendo che scrivere tutto come si deve sia un casino.
Però attenzione, perché la tua costruzione in realtà si blocca nel tratto finale, che dev'essere invece percorso nel senso opposto a quello che dici.

Per completezza aggiungo un po' di spiegazioni, che in fase di gara vanno comunque scritte.

Descriverò i percorsi di ogni singola squadra in coordinate, dove l'incendio parte da (0,0) e si espande di 1 unità al minuto (diciamo). Poiché tutto è simmetrico rispetto all'asse y, descriverò solo i percorsi delle 2 squadre di destra. Quelle di sinistra potranno poi copiare il programma di quelle di destra, o viceversa, cosicché i nostri pompieri, seguendo criteri analoghi, potrebbero pure buttarsi in politica.

Inoltre, ricordo che tecnicamente le squadre non potrebbero partire da (0,0), perché altrimenti sarebbero travolte immediatamente dal fuoco. Nota che questo è diverso dal caso dell'esagono, perché qui in (0,0) non c'è una barricata preesistente, nel momento in cui il fuoco arriva. Quindi modifico leggermente la tua costruzione, e li faccio partire un po' più in basso, giusto per accontentare i "puristi" (a cui io mi fregio di appartenere, beninteso).


Squadra 1

Dal minuto 0 al minuto 10. Parte da (0,-1) ed argina fino a (10,-1). Ce la fa perché (x,-1) è più vicino a (0,-1) che a (0,0), per ogni x.

Dal minuto 10 al minuto 20. Si "teletrasporta" in (20,-1) ed argina fino a (20,9). Ce la fa perché il fuoco tocca questo segmento per la prima volta nel punto già barricato (20,0), e nello stesso istante il segmento viene completato.

Dal minuto 20 al minuto 30. Si teletrasporta in (20,19) ed argina fino a (20,29). Il fuoco tocca questo segmento per la prima volta in (20,19), al minuto $ $\sqrt{20^2+19^2}>27,5 $. Quindi in quel momento i pompieri hanno già arginato più di 3/4 del segmento. D'altra parte, il fuoco raggiunge la metà del segmento al minuto $ $\sqrt{20^2+24^2}>31 $, ovvero quando i pompieri l'hanno già finito. Quindi ce la fanno.

Dal minuto 30 al minuto 40. Si teletrasporta in (0,39) ed argina fino a (10,39). Il fuoco tocca questo segmento per la prima volta nel punto già barricato (0,39) al minuto 39, ovvero quando l'argine è già arrivato a (9,39). A sua volta, questo punto dell'argine viene raggiunto dal fuoco al minuto $ $\sqrt{9^2+39^2}>40 $, quindi ce la fanno a finire.


Squadra 2

Dal minuto 0 al minuto 10. Parte da (10,-1) ed argina fino a (20,-1).

Dal minuto 10 al minuto 20. Si teletrasporta in (20,9) ed argina fino a (20,19).

Dal minuto 20 al minuto 30. Si teletrasporta in (20,29) ed argina fino a (20,39).

Dal minuto 30 al minuto 40. Si teletrasporta in (10,39) ed argina fino a (20,39).


In ogni istante, la squadra 2 è più lontana da (0,0) rispetto alla squadra 1, quindi fa un lavoro "meno rischioso", ed a maggior ragione si salva.
Infine, la squadra 3 si muove come la squadra 1 e la squadra 4 come la squadra 2, solo con le x cambiate di segno.
Poiché il percorso finale è un rettangolo completo, il fuoco viene bloccato.


Oki, adesso sboroneggiamo come dei porci e risolviamolo con solo 3 squadre!