The messenger and the provisions

1. Don't optimize individual routes: think about turning each intermediate house into a new supplied base.
2. To make another day of distance possible, you must first prepare the previous point as if it were the new starting point.
3. If T(n) is the minimum for n days of distance, the key step is T(n)=2T(n−1).

Answer: you need 128 days of marching. Let's call $T(n)$ the minimum number of walking days necessary to go to a destination located $n$ days away and return to the starting point. If the destination is just one day away, the answer is clear: $$
T(1)=2.

$$ One day to go and another to return. Now let's think about a destination located $n$ days away. The first house is one day away from departure. If the messenger manages to convert that first house into a new well-supplied base, then from there he has exactly the same problem, but with a distance of $n-1$ days. The question is how much does it cost to turn that first house into a useful base. So that the remaining trip can be made from there and return, the necessary provisions for the entire $n-1$ day plan must be prepared there. And, furthermore, the courier must have been able to go back and forth between the initial house and that first house while transporting them. Since it can carry four days' worth of food, each round trip between two consecutive houses consumes two days' worth of food and still allows net supplies to be moved to the next point. In this way, preparing the next base costs as much as the trip that will later be made from it. Therefore, by adding one more day of distance, the total cost doubles: $$

T(n)=2T(n-1).

$$ Starting from $T(1)=2$, we obtain: $$

T(2)=4,

$$ $$

T(3)=8,

$$ $$

T(4)=16,

$$ $$

T(5)=32,

$$ $$

T(6)=64,

$$ $$

T(7)=128.
$$ So the minimum is 128 days of marching. The essential idea is that each new house is not just a passing point: it must be prepared as if it were the new starting point. This preparation forces us to repeat, backwards, all the work necessary for the remaining section. That is why growth is not linear, but rather by doubling.