# A walk into the desert and back - have some hard-won answers but can't see the pattern

Mission: To find a minimum-length walk from "base" to a point g distance units away and back for 1 person alone, given:

1. An unlimited supply of rations provided at base, to be consumed continuously while walking.
2. The ability to walk up to 1 distance unit per unit of rations consumed.
3. The ability to carry no more than 2 total units of rations at a time, including those about to be consumed.
4. The ability to walk away from and return to sealed rations only, i.e. rations in full 1-unit packages kept sealed since leaving base. Of course each such package has to be unsealed for any of its contents to be consumed.

Let us assume we have a rule that no more than 1 unit of rations is available (ready to be consumed without an unsealing) at any given time and that an increase in available rations always implies an unsealing. (Such a rule is not really required, but explaining why requires some wordy lemmas and would distract from what I am trying to ask.)

Using a long-running simplex algorithm computer program, I think I have found minimum walks for g between 1 and 195/64 (= 3.046875) distance units, and I would like to do the same for even greater values of g.

But first, I would really like to find a way to cut down on the computation time, if possible, by eliminating a bifurcation of my objective function.

Total walk length, to be minimized, equals twice the amount of walking toward g (because we end where we begin); and the amount of walking toward g has to include the sum of distances from base of all unsealings (because all sealed packages begin at base and no more than 1 can move at a time), plus the distance to g from the nearest unsealing (because the person has to get to g even if no unsealing occurs there).

It is that nearest unsealing that causes the bifurcation. My constraints have to distinguish unsealings before reaching g from unsealings after reaching g because the contents of the packages unsealed after reaching g cannot be used to move any packages unsealed before reaching g.

So I have been having to run the dual simplex algorithm twice for each value of g, once with an objective that assumes the closest unsealing to g happens no later than the arrival at g, and once with an objective that assumes the closest unsealing to g happens no earlier than the arrival at g. Then the result with the smaller minimum walk is my answer.

I find it interesting that none of the results I have gotten so far put the 2 closest unsealings to g equal to each other.

Question 1: Is it impossible to minimize walking with the 2 closest unsealings to g > 1 equal?

Question 2: Is there a clue here as to how to eliminate the bifurcation?

• 1) Is it a homework 2) If yes, is it in an Operational Research lecture ? Commented Jun 24, 2020 at 21:21
• Connected : math.stackexchange.com/q/97419 Commented Jun 24, 2020 at 21:38
• Not homework. Just a curiosity based on Dudeney's "Exploring Mount Neverest", which I've been trying to understand for 20 years. Commented Jun 24, 2020 at 22:47
• Have you seen this article ? Commented Jun 24, 2020 at 22:58
• Yes. I was in contact with the author years ago, but he apparently got too busy to answer my emails. Commented Jun 24, 2020 at 23:01

We shall assume the artificial rule already mentioned, so the amount of walking between consecutive unsealings will always be at least zero and at most 1 unit, and we shall follow the convention of using the same names for locations as for their respective distances from base, and answer Questions 1 and 2 assuming g > 1.

Let g′ = g − ½, and let I be any valid itinerary that fulfills the mission, i.e. in which the person reaches g and then returns to base. Since g′ > ½, there must be at least one location between base and g′ where in I the person changes direction, unseals a package, or walks away from stationary rations. Let g″ be the closest such location to g′.

Lemma 1: For any valid itinerary I that fulfills the round-trip-to-g mission, there exists an itinerary I′ fulfilling the same mission in which the person takes the same actions between base and g″ and does only 2(gg″) units of walking between g″ and g.

Proof of Lemma 1:

Let mb be the moment in I of the person’s last departure from g″ before reaching g and ma the moment of their next arrival at g″, after reaching g. Between mb and ma, the person must walk from g″ to g, a distance of gg″ units, and then from g back to g″, a further gg″ units, and may change direction multiple times and may unseal multiple packages. Since the person has to cover more than 1 unit of distance in that interval, at least one unsealing must occur between mb and ma. Let my be the moment of the first such unsealing.

Altering I by replacing all walking beyond g″ with just consuming the same rations without walking anywhere would give us a valid itinerary for a round trip to g″ with some wasting of rations at g″. But the unsealing at my is unnecessary in such an itinerary because the amount of walking between mx, the moment of the latest unsealing before my (the beginning of the mission if none), and mz, the moment of the first unsealing after my (the end of the mission if none), which is no more than 2 units in I, invariably gets reduced to 1 unit or less by the alteration: If my is the only unsealing between mb and ma, then the whole interval from mb to ma, in which walking gets reduced from greater than 1 unit to zero, is contained within the interval from mx to mz, and otherwise mz occurs before ma so that walking between my and mz gets reduced to zero, leaving only the walking between mx and my, 1 unit or less, between mx and mz.

Since all rations begin at base and only 1 sealed package can be carried at a time, the person must have, at some point prior to my, departed from g″ carrying a sealed package toward g′ when there were no rations at or beyond g′. Let mi be the latest such time before my, and let mj be the moment of the person’s next arrival back at g″ after mi.

Altering I by eliminating both all walking beyond g″ and the unnecessary unsealing at my gives us a valid itinerary for a round trip to g″ in which there is at least 1 sealed package at g″ at all times after mi. Call this altered itinerary J. Assuring that the sealed package being carried at mi is never unsealed or even carried back toward base after mi in J is not a real restriction. Since all sealed packages are the same, the person can always, whenever an unsealing or removal is required after mi, choose a different package to unseal or carry away and leave that particular package undisturbed.

If mi = mb, then in I the person has to be carrying at least 2(gg″) units more rations at mi = mb than at mj = ma, including a sealed package, in order to walk to g and return to g″. Otherwise, between mi and mj in I, the person takes a sealed package to g′ or beyond and returns to g″, so in this case too the person has to be carrying at least 2(gg″) more rations at mi than at mj, 1 sealed package plus 2(g′g″).

If the difference in rations being carried between mi and mj is greater than 2(gg″), the excess can be discarded or consumed without walking at the corresponding point in I′. Then in I′ the person can simply walk directly to g and back, consuming exactly 2(gg″) units of rations, and the part of I′ beginning at the point corresponding to mj will suffice to return the person to base. The sealed package being carried at mi will of course need to be unsealed at the exact moment when the other rations inevitably get used up. If the unsealing will happen after the person reaches g, the person can even leave the package at its unsealing location when on the way to g. Q.E.D.

Answer to Question 1: At least 1 unsealing must occur between mb and ma, when the person is beyond g″, so if the 2 closest unsealing positions to g are equal in some valid itinerary I, they must both occur beyond g″, and this requires more than 2(gg″) units of walking beyond g″ in I. But by Lemma 1 there exists an itinerary J with less walking, so yes, it is impossible to minimize walking with the 2 closest unsealing positions to g > 1 equal.