SSSUP 2009 n 4: Arginare un incendio
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Intanto è circoscritta e non inscritta, ma credo sia un refuso.Alex90 ha scritto: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 $
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.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
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.
Però non sono riuscito a trovare strategie per il caso con 4 squadre ne a dimostrare che non è possibile in alcun modo.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Tu hai fatto il concorso dove c'era questo problema? Sai se qualcuno l'ha risolto ed eventualmente l'ha generalizzato?mrossi ha scritto:Però non sono riuscito a trovare strategie per il caso con 4 squadre ne a dimostrare che non è possibile in alcun modo.
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!
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
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.
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.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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.
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.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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!
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!
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]