Lanterna e passerella

[Marco]

Ciao. Questo è un rompicapo matematico graziosissimo, con cui si può fare un figurone e passare da matematico pazzo alle feste con amici. E' molto famoso, quindi penso che lo conoscano in molti, e forse è già addirittura apparso sul Forum.

Anyway, here it goes.

---------------------------------------

Siamo in quattro, di sera e dobbiamo attraversare un ponte che però può sostenere solo due persone per volta. E' buio ed abbiamo una sola lanterna (*). Per passare quindi occorre che qualcuno torni indietro con la luce e recuperi gli altri.
Vogliamo attraversare il ponte tutti e quattro nel minor tempo possibile. Sapendo che i tempi di attraversamento sono 10, 5, 3 e 2 minuti e che, ovviamente, il tempo impiegato da due persone che viaggino assieme ad attraversare è quello della persona più lenta, calcolare il tempo minimo richiesto.

(*) A beneficio dei pignoli come me, supponiamo che la lanterna illumini una zona puntiforme

---------------------------------------

Il gioco è tricky. E la soluzione spiazzante. Buon divertimento. M.

[hydro]

la sol potrebbe essere questa...
- passano per primi i due più veloci (3 min)
- il secondo più veloce riporta la lanterna (3 min)
- passano i due più lenti (10 min)
- il più veloce di tutti riporta la lanterna (2 min)
- i due rimasti a questo punto passano insieme (3 min)

in tutto impiegano quindi 21 minuti

[moebius]

Pure io avevo pensato questo... solo che il fatto della soluzione spiazzante mi fa pensare che non sia quella giusta

[Marco]

Ah, no. Nessun segreto. 21 è proprio la risposta giusta.

Ho detto che il problema era tricky perché l'errore comune che normalmente la gente commette è di minimizzare i tempi dei due ritorni, con il risultato che 2 va avanti e indietro e gli altri a turno, totalizzando 22 minuti.

Provate con qualche vostro amico e sappiatemi dire.
Beh, Hydro, se non conoscevi il quiz e hai trovato subito la risposta, complimenti.

Ciao. M.

[Hammond]

Si riesce a dimostrare che è la soluzione migliore (ovvero che non si può in 20 minuti) ?

[MindFlyer]

Si riesce a dimostrare che è la soluzione migliore (ovvero che non si può in 20 minuti) ?

Certo che si riesce: le configurazioni "candidate ottime" non sono infinite (e non sono nemmeno tante).

[Azarus]

E con tempi a,b,c,d generici?

[MindFlyer]

Con tempi generici cadiamo nel solito problema di inconsistenza del testo. Ovvero, esiste banalmente una funzione primitiva ricorsiva che dà il tempo minimo in funzione di a,b,c,d, ma forse non in una forma che soddisfi certi vaghi requisiti di estetica che i più sembrano imporre implicitamente.

[enomis_costa88]

@ hammond:si si può dimostrare e penso che così vada bene.
si assegna un valore alle 6 coppie e uno ai 4 singoli.
scegliendo 3 coppie che usino tutte le persone e due numeri singoli in modo tale che la somma dei valori sia minima(se si usa due volte una coppia non si può usare 2 volte la stessa persona perchè entrambe le persone della coppia devono tornare indietro..a meno che non si voglia fare 2 viaggi in+..molto sconveniente direi) il min=21
ok mi spiego meglio: si vede subito che servono 3 viaggi di coppia e 2 singoli. scegliendo il minimo singolo e le minime 3 coppie che usino tutti i numeri si ha
$ 2+2+10+3+3=20 $
che è l'unico 20 possibile e non è accettabile per quanto detto sopra (userebbe 2 volte il 2) per cui essendo il 21 accettabile è il minimo. Mi sembrerebbe che questa strategia sia usabile anche per tempi a,b,c,d generici..ovviamente osservando prima se è più conveniente usare due volte la coppia migliore o il singolo migliore.

[enomis_costa88]

provo a dimostrare il caso generale:

ponendo $ a \ge b \ge c \ge d $
th: $ f(a,b,c,d) = 3c+a+d $ se $ d+b \ge 2c $ altrimenti
$ f(a,b,c,d)= 2d+c+a+b $

assegno qesti valori: $ ab,ac,ad=a;bc,bd=b;cd=c $
esiste una strategia 1(quella usata nel problema originale) che usa $ cd,c,ab,d,cd $ che vale $ 3c+a+d $ e un'altra(2) che usa $ dc,d,db,d,da $ che vale $ 2d+c+a+b $
vediamo quando la prima è più conveniente:
$ 3c+a+d < 2d+c+a+b $ ovvero $ 2c < b+d $ negli altri casi è più conveniente l'altra(nell'uguaglianza è indifferente). per cui se tutte le altre strategie sono più sconvenienti la Th è vera.

dimostro ora che le altre strategie sono più sconvnienti.
è palese che serve una a ma che è sconveniente averne più di una.
rimangono 4 viaggi e 3 lettere.
1)se uso 2(o più..) b: avrei a,b,b e anche supponenedo di usare 2d risulterebbe peggiore della strategia 2
2) se uso una b: a,b e noto che è impossibile avere 3 d perchè non può esserci d nelle coppie. quindi la migliore sarebbe a,b,c,d,d cioè la 2
3) se non uso b: devo riempire quattro viaggi con 3 lettere e due viaggi sono di coppia per cui dovendo usare solo c e d l'unica coppia possibile(da usare 2 volte)vale c, e i due singoli sono c e d perchè entrambi devono tornare indietro. ma questa è la strategia 1
per cui non ci sono strategie migliori.

@MF ma era questo che intendevi come funzione primitiva in 4 variabili a,b,c,d?