Yesterday, was late night when I wrote my solution, so, I apologize for any English slip and punctuation failure worse than my usual.

Exploring a little the solution, it is easy to see that if to walk 6 days, we’ll need 2 porters, to walk 8 days we’ll need 7, and to walk 10 days, 20!!!… in my kind of solution. Or maybe we don’t need all these but only one… doing 20 voyages from the village to hide food in the way. 8-days walking is an obvious mark: it is clear that we can’t have all porters starting at the same time and transporting all the food always with themselves (like in Andrew’s – and my friend’s – solution) since when the last porter separates himself from Marco, he’ll need 4 days of food to return and even refusing to replenish Marco food, he will not have enough. It’s doubtful if we can do it even for only 7 days walking. For these kind of solutions, we are forced to employ a new trick, to have someone starting later and encounter the returning porters in the way. We can reuse the already returned porters to do that so it will be an interesting problem to find what are the minimal number of different people able to mount the expedition for N days IF the food is never hidden.

That was the solution of my friend which I repute as more elegant than mine. My initial solution was a little different: the third porter would after the first day of walking, leave to the village taking with him one day of food, leaving with the second porter another day of food and hiding a third day of food for the second porter when he would came back through the same path at the end of the third day. I came with this solution at a place where I hadn’t paper or pencil and didn’t recalled that in the end of the third day, Marco was relieved of carrying one day of food and could carry more then. To leave provisions behind is not uncommon in expeditions to inhospitable territories like earth poles or high mountains so to be able to hide food for the return appeared to me a good allowable trick to improve the results. I convinced myself at the time my solution was better than my friend. It wasn’t, and his hadn’t the risk of seeing a raid on the hidden provisions… that’s why I think his (and yours) is more elegant FOR this problem. However, I must contend that the reasoning behind is more productive in the long run. It is not. If we change slightly the description of the problem to the following: porters payed and consuming food by the hour of walking, walking a total of 12 hours per day and resting (and not consuming) the rest, then there is a better solution than 600$:

The three will leave the village with 4 days of food in Marco, 4 days in the first porter and 3 days plus 1/3 (4 hours) in the second porter. After walking 8 hours, the last porter will return to the village carrying with him 2/3 days of food, will hide 2/3 and will give 2/3 to Marco and the first porter to replenish their carried stock. Total of these numbers: 4*2/3=8/3. Summing with the 2/3 he consumed in those 8 hours, this gives the 10/3=3+1/3 of food with which he started. He will also return to the village in the first 4 hours of the second day… he walked 16h so he will receive $133 (compare that with the day and 1/6 of the day he was out of the village).

Now, the first porter will walk 4/3 days more after that. At this point, two days had passed. He’s carrying 4-4/3 days of food, and will give 4/3 days to Marco so he can replenish his food and have enough to walk the 4 days-distance until his target. He will be left with 4-2*4/3 = 4/3, enough to return the point where they hide the food for an 8 hour return to the village.

Has you can see, in this solution, Marco only have to pay $533, or more exactly, 5+1/3 days of fare. The food needed is also less. The extra conditions are a little convoluted, but only because of the need to implement payments and consumes by the fraction of a day… The 12 hours of walking is not really a necessary condition to the problem but an human touch to it: I didn’t want to tax the credibility of the puzzle saying walking would be non-stop activity through those days. The reason for all this is better understand by explaining how I constructed the solution: I did that reverting the time, and putting the time zero in the moment of arrival to the second town.

First, only Marco needs to reach the second village. He can carry food for 4 days, so this is the time when he will walk alone. So, 4 days before arrival, he will separate from the last porter and will start the walk with 4 days of food. Before that, he has to have a porter to carry the food to him and to the porter so in order he will not use the final 4 days of food. This porter represents an additional capacity of 4 days of food but this, will serve to feed… Marco, the porter in travel with him, and the porter return to home… so these 4 days of food will only lasts for 4/3 total. 4+4/3 = 5 1/3 days, not enough to go to the second village, so it is needed another porter before that. This one represents an additional capacity for 4/5 days of travel… summing, we’ll have 5 1/3 + 4/5 = 92/15 = 6 days and 2/15 which is enough for the travel. Had we need more time and we could have added more porters at need: 4(1+1/3+1/5+1/7+1/9…). The series inside brackets are divergent so, any traveling distance is possible, subject to this fundamental restriction: it must be possible to hide and retrieve food.

The solution above is optimal, so, if the porters are payed by the day, and the second porter being out a day and a little more (1/3 of walking day time) is payed as if he was out of the village for two days (although we can doubt if in the example presented, 4 hours classify itself as a full day), then $600 will be indeed the best Marco will get.