Newsgroup: it.hobby.enigmi
Titolo: Banane

Il nostro amico Ali' vive in una piccola oasi a 1000 Km dal Tibur, la
citta' piu' vicina .
Ha raccolto 3000 banane e desidera portarle al mercato di Tibur per
venderle.
Il problema sta nel fatto che possiede un solo cammello in grado di
trasportare nel deserto un massimo di 1000 banane per viaggio, e per
poter procedere il cammello si mangia 1 banana ogni chilometro.
Scegliendo la miglior strategia, con quante banane riuscira' ad arrivare
a Tibur ??
:) dario

Cavolo, non lo so...500 e' il meglio che sono riuscito a fare ma non riesco
a dimostrare che sia il max...ne' a dimostrare che non lo e'...
Capisco che se voglio portare il max. numero di banane alla citta' fruttando
tutte e 3000 le banane che ho a disposizione devo chiedermi:
qual'e' il punto piu' lontano dove possa arrivare con 1000 banane, avendo
fatto (almeno) 5 viaggi ? (5 viaggi: 3 AVANTI e 2 INDIETRO se voglio usare
tutte le 3000 banane...)
Bel problema, grazie.


Sei sulla strada buona.... si puo' fare meglio.
ciao :) dario

Ciao Dario,

Supponendo che il cammello mangi una banana al chilometro sia quando
e' carico che quando e' scarico, la miglior strategia che sono
riuscito a suggerire ad Ali' gli ha permesso di arrivare a Tibur
con 532 banane.
.
.
.
.
.
.
.
.
.
<SPOILER>
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Con (km, b) indico la coppia (chilometro, banane rimanenti)
[0] =>  (0, 3000)
   1.1 Carica 1000 banane e arriva al km 200 con 800 banane.
       Ne scarica 600 e torna indietro con le 200 rimanenti.
   1.2 Carica 1000 banane e arriva al km 200 con 800 banane.
       Ne scarica 600 e torna indietro con le 200 rimanenti.
       Al km 200 ci sono ora 1200 banane.
   1.3 Carica 1000 banane e arriva al km 200 con 800 banane.
       Al km 200 ci sono ora 2000 banane.
[1] =>  (200, 2000)
   2.1 Carica 1000 banane e arriva al km 534 con 666 banane.
       Ne scarica 332 e torna indietro con le 334 rimanenti.
   2.2 Carica 1000 banane e arriva al km 534 con 666 banane.
       Al km 534 ci sono ora 998 banane.
[2] =>  (534, 998)
   3.1 Carica le 998 banane riuscendo a portarne 532 a Tibur.
[3] =>  (1000, 532) 
L'idea di base della mia strategia e' quella di minimizzare
l'andirivieni, che consuma 2n banane. Per fare questo, il
punto di sosta deve essere scelto in modo da poter sempre
caricare al massimo il cammello. Nella parte [1] si riesce
a farlo esattamente perche' dovendo fare 3 carichi bisogna
per forza fare 2 andata/ritorno e 1 sola andata, per un
totale di 5 viaggi. Pertanto volendo arrivare con 2000
banane al punto di sosta e' chiaro che ci si deve fermare al
km 1000/5=200. Nella parte [2] bisogna fare 3 viaggi fino al
punto di sosta e arrivare li' con un numero di banane prossimo
a 1000 (ma inferiore). Quindi e' ovvio che andranno percorsi
ceil(1000/3)=334 km.
E' da notare che la strategia enunciata ammette anche altre
due soluzioni diverse, ma identiche come risultato:
[1] (201, 1995)
[2] (533, 999)
[3] (1000, 532)
e
[1] (202, 1990)
[2] (532, 1000)
[3] (1000, 532)
Francamente, pero', non so come dimostrare che la strategia
che ho scelto sia la migliore possibile. Tu come faresti?
Saluti,
          iant



A dire il vero anch'io ho ragionato come te, e ne porto 533 mangiandone
addirittura una:


Partendo da 200Km con 2000 banane, arrivo a 533, ne poso 334 e torno
a 200Km. Riparto con 1000, arrivo a 533 con 667 banane, ne carico 333 e
UNA LA MANGIO (dopo tutti questi Km avro' pure fame...); Sono dunque a
533Km con 1000 banane. Dovendo percorrere


467 Km, arrivero' a destinazione con 533 banane.


Credo che questo sia il massimo perche':


1) Devo minimizzare il numero di viaggi, il che significa che devo
partire sempre con 1000 banane (e questa conclusione si puo' anche dimostrare...),
il che porte ai 200Km;


2) Devo arrivare piu' avanti possibile con 1000 banane, il che porta
al 533. Sarebbe anche possibile arrivare a 533,333... facendo mangiare
UN TERZO di banana al cammello, ma il risultato non cambia poiche' quel
terzo di Km lo devo percorrere 3 volte...l'unica cosa che cambia e' che
non mi mangio la banana ;)


Che ne pensate ?
