0
$\begingroup$

Mission: To find a minimum-length walk, for one person alone, that covers the entirety of a simple closed curve c distance units long and that begins and ends at a particular point B on that curve, given:

  1. An unlimited supply of rations, initially all at B, to be consumed continuously while walking.
  2. The ability to walk a maximum of 1 distance unit per unit of rations consumed.
  3. The ability to carry no more than 2 units of rations at a time.
  4. The ability to retrieve from any point on the curve only rations in full 1-unit packages that have remained sealed since the beginning of the mission. A sealed package must be unsealed for any of its contents to be consumed.

Michiel de Bondt seems to have solved this problem for c=5 (basically Exploring Mount Neverest by Henry Ernest Dudeney and H. F. Heath), but I am having trouble with some of de Bondt's unstated assumptions.

For example, a walk might include reaching a certain point P away from B, first from one side and later from the other side, and then returning to B. Together, B and P divide the curve into 2 parts: p1, which is completed first, and p2, which is completed second.

My question is: Is it safe to exclude from consideration any itinerary in which rations arriving at P via p1 are consumed while walking on p2?

The answer is probably obvious, but I want to know why it is obvious.

$\endgroup$
5
  • 1
    $\begingroup$ I don't understand the rules of the game and I am surely not alone. What is your simple closed curve : if I take a circle what happens ? what is "walking up" on a circle ? Under which conditions does the (unique ?) player go back, etc. You have to give a detailed example... $\endgroup$
    – Jean Marie
    Commented Mar 17, 2023 at 22:54
  • $\begingroup$ A simple closed curve is basically a circle. Yes, the player is unique. And there is no "walking up": the Professor has the ability to walk at most 1 distance unit (20 miles in the original puzzle) per unit of rations. $\endgroup$
    – Forero
    Commented Mar 18, 2023 at 4:22
  • $\begingroup$ I have made some minor changes to my wording. I am attempting to explicitly describe a particular generalization of Dudeney's "Exploring Mount Neverest" without altering the spirit of the original puzzle. $\endgroup$
    – Forero
    Commented Mar 18, 2023 at 4:41
  • 1
    $\begingroup$ Thanks. Another request : please provide a reference to the original article of Dudeney. $\endgroup$
    – Jean Marie
    Commented Mar 18, 2023 at 9:32
  • 1
    $\begingroup$ The original was in The Strand Magazine in 1922, but it was republished in 1967, edited by Martin Gardner, in a little book called 536 Puzzles & Curious Problems. My other reference is Michiel de Bondt's 2005 paper in which he seems to have actually solved the problem mathematically. All of these are available online from various places. $\endgroup$
    – Forero
    Commented Mar 18, 2023 at 13:15

2 Answers 2

1
$\begingroup$

No, it is not obvious. Consider the case $c=3$ and let $P$ be one unit clockwise from $B$. I claim the following is optimal, though there are equally efficient solutions. Set out clockwise from $B$ with two rations. Drop one at $P$, eat the other, and return to $B$. Set out counterclockwise from $B$ with two rations. Eat one at one unit, get to $P$, eat the ration that you dropped there, and continue to $B$. Another solution is the mirror image. Another is after dropping the ration at $P$ to set out clockwise with two rations, get to $P$, eat a ration and pick up the dropped one, and continue around.

With the requirement to eat continuously, let $c=3$ and place $P$ at $1/2$ clockwise. You can start from $B$, drop one at $P$ and return, then start from $B$ going counterclockwise, drop one at $5/2$ and return. Now you can start from $B$ and go either direction. When you have traveled $1/2$ drop the ration you are eating and start on the one you find. Your $2$ rations will take you to the other one you dropped and you can continue to $B$.

For larger $c$ it may be useful to solve the problem on a line of length $c/2$ starting from one end. What is the most efficient way to get to the end and return to $B$? You can then make a circle by putting two of these together. It seems you could generally make the final run by going all the way around the circle as we saw for $c=3$.

$\endgroup$
9
  • $\begingroup$ Usually in these problems you consume a ration and then can walk one unit. As you write it you don't have anything to eat on the return to $B$. I thought you eat one at $B$, set out with two, drop one and eat one at $P$, then can walk back to $B$. $\endgroup$ Commented Mar 18, 2023 at 13:49
  • $\begingroup$ About that approach, Dudeney says "he would really be carrying three rations, one inside and two on his back!" $\endgroup$
    – Forero
    Commented Mar 18, 2023 at 14:01
  • $\begingroup$ So with a full load he can get a sealed ration only halfway to P=1 and still be able to get back to B. $\endgroup$
    – Forero
    Commented Mar 18, 2023 at 14:16
  • $\begingroup$ I have added "continuously" to, hopefully, clarify that eating is done while walking, not beforehand or afterwards. $\endgroup$
    – Forero
    Commented Mar 19, 2023 at 12:50
  • $\begingroup$ Note that in one of your suggested itineraries, P=5/2, not 1/2. $\endgroup$
    – Forero
    Commented Mar 19, 2023 at 15:50
0
$\begingroup$

The paper which claims to solve the c=5 case has been updated with a new version. Two errors are fixed, of which one is the above-described gap in the argument. The gap is fixed as follows.

If there is a position which is visited only one time, then one may assume that the walk splits in the following parts:

  • Part A: a round trip from position B to position P to set up fuel for part C.
  • Part B: a one way trip from position B to position P from the other side, in which no fuel of part A is used.
  • Part C: a one way trip from position P to position B, in which only fuel of part A is used.

If there is no position which is visited only one time, then the walk is at least 25 units, which is longer than the given solutions. This is proved with "jeep arguments": the person who performs the walk is replaced by a Fine jeep which can carry the fuel equivalent of 2 rations. The jeep has more flexibility in making and using fuel depots.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .