L'explorateur - Détails (4)

Etapes entières

Pour atteindre 50 jours et revenir, il faut 82 porteurs et la première étape est de 20/166 ≈ 0.12 jours Si on pense que cette valeur est sans signification, on peut utiliser le nombre exponentiellement croissant de porteurs autrement : Avec des étapes de durée constante et un nombre exponentiellement croissant de porteurs qui reviennent à chaque étape.
Soit bn le nombre de porteurs qui reviennent à l'étape n, b1 = 1 = l'explorateur seul.
A l'étape courrante, démarrant avec sn = ∑bi = bn + sn-1 porteurs depuis xn avec une quantité totale de nourriture de q(bn + sn-1)
Terminant l'étape à xn-1, après un = xn-1 - xn, ils ont consommé (bn + sn-1)un
Les sn-1 porteurs (y compris l'explorateur) continuent emportant sn-1×q
Les bn reviennent au début de l'étape emportant bnun
Ils laissent un dépôt de nourriture de sn-1un pour ceux qui reviendront plus tard.
Bilan : q(bn + sn-1) = (bn + sn-1)un + q×sn-1 + bnun + sn-1un
C'est à dire : q×bn = 2(bn + sn-1)un ou bn/sn-1 = 2un/(q - 2un)
 sn/sn-1 = 1 + bn/sn-1 = q/(q - 2un) 
 bn/bn-1 = un/un-1 × q/(q-2un) 

Avec un = q/4 = 5 jours constant pour n ≥ 2, et u1 = 10, en partant de b1 = 1 (l'explorateur seul),
b2 = b1 × 5/10 × 2 = 1, bn = 2bn-1 = 2n-2 pour n > 2
Il faut (30 - 10)/5 = 4 étapes soit 16 porteurs, y compris l'explorateur. Ceci est la seule solution avec des étapes constantes entières. Pour diminuer le nombre de porteurs il faut utiliser des étapes plus petites, mais un processus bien plus compliqué.

Nourriture en rab

La méthode optimale est de faire revenir les porteurs un par un, mais ceci résulte, comme vu ci-dessus, en des étapes non entières. Pour avoir des étapes entières, il faut combiner les deux méthodes et utiliser des étapes variables et un nombre de porteurs variable à chaque étape. Ceci va gaspiller de la nourriture, aussi nous utiliserons un processus de transfert en arrière de la nourriture en rab, pour économiser des porteurs :

En partant de la fin, l'optimum est encore 10 jours + 5 jours avec b1 = 1 (explorateur), b2 = 1.
b3 = 1 conduirait à une étape de 20/6 = 3.33 jours, que l'on va réduire à 3 jours.
Le bilan de cette étape est :
au départ 3×20 = 60 jours, consommé 3×3 = 9 jours, plein = 2×20 = 40 jours, 1 porteur retourne = 3 jours, dépôt pour 1 porteur + explorateur revenant plus tard = 6 jours. C'est à dire 9 + 40 + 3 + 6 = 58 jours.
Ils reste 2 jours de nourriture gaspillée, que l'on économise en commençant l'étape précédente avec moins de nourriture, ou en permettant aux porteurs de revenir plus loin que le début de l'étape.
En appliquant ce procédé à une étape quelconque :
Départ avec sn = ∑bi = bn + sn-1 porteurs, explorateur compris
marche un et consommé (bn + sn-1)un
bn porteurs reviennent au début de l'étape, consommant bnun
sn-1 persones continuent en emportant sn-1q
dépôt pour le retour ultérieur des sn-1 au début de l'étape : sn-1un
Si on considère que ceci est trop de nourriture pour les étapes suivantes, elles ont fn-1 en rab porté par les hommes qui reviennent, ou laissé en dépôt à la fin de cette étape-ci.
Le bilan de l'étape est fn = (bn + sn-1)q + fn-1 - (bn + sn-1)un - bnun - sn-1un - sn-1q

  fn = bnq + fn-1 - 2(bn + sn-1)un  
Cette étape est OK si fn≥0 c'est à dire bnq + fn-1 ≥ 2(bn + sn-1)un
Comme le nombre minimum de porteurs est bn = 1 et que la durée minimum de l'étape est un = 1 jour, ceci conduit à :
  • si q + fn-1 ≥ 2(1 + sn-1), un porteur est suffisant pour cette étape et un = floor( (q+fn-1)/(2 + 2sn-1) )
  • sinon il faut plusieurs porteurs et une étape de 1 jour, alors bn = ceil( (2sn-1 - fn-1)/(q - 2) )
On calcule alors le rab de nourriture propagé vers les étapes précédentes fn

Ceci donne en partant de la fin :

jours/porteur, Distance (details)
 
Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Précédent Suivant Parent