Il ponte

[WonderP]

Visto che ci siamo lanciati con i problemini matematici (ho perso quello delle freccette in quanto ero ammalato, ma ora lo risolvo anche io) qualche tempo fa ho sentito questo, che è molto simpatico:

4 persone devono attraversare un ponte di notte;
posso attraversare al massimo due persone alla volta;
si può attraversare il ponte solo con una torcia accesa;
c'è una sola torcia;
sapendo che le quattro persone hanno tempi di percorrenza diversi (la persona A impiega 1 minuto, B 2 minuti, C 5 e D 10 minuti) e che quello più veloce deve aspettare il puù lento (es. se vanno A e B impiegano 2 minuti ma per tornare A ne impiega 1, ricordo che deve portare la torcia)
<b>Quanto tempo impiegano al minimo tutti e quattro ad attraversare il ponte?</b>

Vi dico già che 19 minuti è troppo.

WonderP.

[Thomas]

Ehilà wonderp è da un pò che non ci si sente<img src=icon_smile_big.gif border=0 align=middle>
Incomincio subito col dire che appena ho trovato una sol sotto il 19 ho scritto, quindi se la mia sol è sbagliata è colpa di wonderp che mi ha messo sulla cattiva strada <img src=icon_smile_wink.gif border=0 align=middle>.
Allora, li chiamo 1-2-5-10 per ovvie ragioni [sull'isola]:
1)partono 2-1;
2)torna 1; [2]
3)partono 10-5;
4)torna 2; [10,5]
5)partono 1,2;
in totale 2+1+10+2+2=17 minuti
A proposito, quest'anno la gara si fa o no. E se si fa, quando inizia?
Ciao

[WonderP]

<b>Corretto</b> di questo problema è interessante notare, per chi cercherà di risolverlo, come istintivamente si cerchi di ottimizzare i "ritorni" facendo tornare sempre A che impiega 1 minuto (almeno queste sono le conclusioni che ho tratto proponendo questo quesito a divesre persone), mentre la soluzione si ha con un'ottimizzazione delle "antate" facendo attraversare il ponte a C e D (5 e 10 minuti).
Ditemi se non è vero?

WonderP.

[vecchio]

hi hi carino...
compolimenti a Thomas!! io mi ero fossilizzato sul 19...continuavo a far tornare indietro uno dei due che partivano, senza pensare che poteva tornare indietro uno arrivato prima...credo che sia questo che induce molti in errore...o almeno è questo che è successo a me...
cmq, rifaccio la domanda di Thomas...si fanno quest'anno le gare..
non vedo l'ora...anche se non sono a certi livelli... <img src=icon_smile_wink.gif border=0 align=middle>..però mi diverto cmq.

ciao a presto

il vecchio

[tony]

Bello, bello, e divertente, grazie WonderP!

Non l'ho saputo risolvere.
Comunque, mi pare che la soluz. ottimale di Thomas (+1+2 -1 +10+5 -2 +1+2 ==> 17) non sia unica.

Ci scaviamo un poco dentro?
[1] Qualcuno approfondisce la non unicità della soluzione?
[2] Qualcuno, per amore dell'affascinante (?) calcolo combinatorio, ci dice quante possibili soluzioni ci sono? (ovviamente anche quelle non ottimali, tipo quelle che assommano a 19 o più).
[3] Qualcuno risolverebbe questi quesiti con 5 persone invece di 4? (brrr...)

Ancora, ancora di questi giochini!
Ciao a tutti, da Tony

[drake53]

Ci sarebbe la soluzione:

1) partono 1 e 2
2) torna 2
3) partono 5 e 10
4) torna 1
5) partono 1 e 2

Totale 17 minuti

Non credo ci siano altre soluzioni con 17 minuti, visto che 5 e 10
devono partire insieme e quindi tornare uno veloce.
Con 5 persone c'e' da decidere il tempo da assegnare alla quinta,
ma da qualche prova fatta mi sembra che il principio da usare sia
lo stesso.

Drake

[WonderP]

<b>[2]</b> Ho provato a vedere quante possibili combinazioni ci sono e mi sembra siano 108, ma non vorrei aver sbagliato:
inizialmente ci sono 4 persone e dobbiamo prenderne 2, calcolo combinatorio

2 su 4 = 6

(non conta l'ordine, si va sempre alla velocità del più lento, cioè che scelga A e B o B e A non cambia nulla) a questo punto deve tornare uno dei due che ha attraversato il ponte

2 possibilità

ci sono 3 persone che devono attraversare, quindi

2 su 3 = 3

e una delle tre che ora sono al di là del ponte deve ritornare

3 possibilità

infine devono attraversare le ultime due, quindi

2 su 2 = 1

moltiplicando risulta 6*2*3*3*1=108.

<b>[1]</b> direi che la soluzione non è unica nei casi in cui a tornare non sia la stessa persona, ad esempio nella soluzione da 17 minuti tornano A (1 minuto) e B (2 minuti) ma l'ordine in cui tornano non conta, di più non so dire.

<b>[3]</b> penso che dipenda molto dal minutaggio, ad esempio se la persona C invece di 5 minuti na impiegasse 3 anche la soluzione più ovvia, cioè quella che fa tornare sempre A (1 minuto) risulta ottimale (totale 17 minuti). C'è da dire però che se C impegasse 4 minuti la soluzione ottimale sarebbe del tipo trovato da Thomas e drake53, mentre se ne impiegasse 2 come B si tornerebbe ad avere come soluzione quella in cui torna sempre A. Quindi posso dedurre che con 5 persone ci siano dei minutaggi "disciminanti", cioè non valga sempre un unica successione.
Con 5 persone le possibili combinazioni sono (omaglio dovrebbero essere 10*2*6*3*3*4*1=4320.

WonderP.



Modificato da - WonderP il 02/10/2003 10:30:22

[WonderP]

Ho prevato a ragionare un'altro po' sulle possibili combinazioni e spero di aver trovato una formula generale per qualsiasi numero di persone.
Da mio topic precedente si può notare che ci sono due distinte serie una che rappresenta le combinazioni delle persone che vanno, una di quelle che tornano. La prima è
2 su 4
2 su 3
2 su 2
per 4 persone, per 5 aggiungo
2 su 5
quindi esplicidando si ha
5*4/2
4*3/2
3*2/2
2*2/2
quindi generalizzando n*[(n-1)!]^2/2^(n-1), (ad esempio il 5 compare una volta nell'esempio sopra)

L'altra serie di cui parlavo riguarda le persone che tornano e si ha la seria
2, 3, 4 nel esempio di 5 persone (nel topic precedente le due serie sono alternate, 10*2*6*3*3*4*1 che posso scrivere 10*6*3*1 * 2*3*4)
quindi in generale (n-1)!

moltiplicando assieme le due serie risulta:

<img src="http://utentiforum.supereva.it/WonderP/ponte.gif" border=0>




Modificato da - WonderP il 02/10/2003 16:21:17

[WonderP]

Ho provato ad analizzare il problema con 5 persone. Imponendo che la quinta persona E impieghi più di 10 minuti ho notato che la soluzione ottimale si ha sempre quando in un’andata questa viene associata con la persona D (10 minuti), cioè le due persone che impiegano più tempo devono attraversare assieme (come nel caso di quattro persone). Ci sono più soluzione, come prima, ma tutte con la costante sopra detta e poi una permutazione delle altre accoppiate. Un esempio:
1-2
1
10-x
2
1-5
1
1-2

dove x è il tempo di percorrenza della quinta persona, con x>10 minuti.
Ho notato anche che la soluzione non varia per x>=5, si può infatti notare che la persona D e la persona E rimangono comunque le due persone che impiegano più tempo.

WonderP.

[tony]

Ciao a tutti.

Corretto, Drake, corretto e bello, WonderP; vedo che ti ci sei appassionato.

Non riesco a mettere a fuoco lucidamente, WonderP, le implicazioni della tua frase
"[3] penso che dipenda molto dal minutaggio, ..."
da te poi riammodernata nei post successivi, che devo rileggere con maggior calma.

Lo pensavo anch'io fino a che non ho scritto il solito programmino che passa brutalmente (ma ordinatamente) tutti i casi (108 e 4320 risp.), e, per ogni prova che migliora il minimo, mi stampa il numero della prova, il punteggio e il "log" dell' andirivieni.
E' stato facile assegnare tempi *diversi* ai singoli partecipanti (ho provato solo con 4 e 5), e sono ancora confuso dai risultati (che in certi casi mi invitano a credere a miraggi).

Divertente, direi, ma stiamo giocandoci in pochi

Tony