Traveling salesman-like problem where we need to find branch $j$ such that enough revenue is received to continue travel to next branch

Question

I'm not quite sure what type of problem this is, although at the first glance it looks similar to traveling salesman (if you know the specific name of such variation please let me know).

The problem is:

A store has $n$ branches $s_1,s_2,...,s_n$. The salesman has to travel all of them in order to collect different products.

1. When the salesman finishes his work in the branch $1 \le j \le n$ he receives $m_j$ revenue.
2. For $j \le n-1$ from branch $s_j$ departs a flight to the next branch $s_{j+1}$ for the cost of $c_j$. From the last branch $s_n$ departs a flight to the first branch $s_1$ for the cost of $c_n$.

It's given that the total amount of revenue equals the total amount of flights cost that is: $$ \sum_{j=1}^n m_j=\sum_{j=1}^n c_j $$ At each time the salesman can only pay for the next flight from the money he currently has.

The salesman can decide from which branch to start the journey and the first flight will be free for him.

Prove that there's always $a \le j \le n$ such that if the salesman starts the journey from branch $s_j$ he will be able to finish his journey with his budget.

I thought first of all that we can express mathematically the problem as follows: $$ \exists j, s_j|m_j \ge c_{j+1} $$ because the way I understand it there has to be a branch where the salesman will receive enough money to cover the cost of traveling to the next branch.

If we suppose that there's not such a branch I guess the equivalent will be: $$ \forall j, s_j|m_j < c_{j+1} $$ but then $\sum_{j=1}^n m_j<\sum_{j=1}^n c_j$ which is a contradiction.

Answer 1

The order of visiting the branches is a fixed cycle, so this isn't really a traveling salesman problem. The only degree of freedom is the choice of which branch to visit first.

Note that

$$\sum_{j=1}^n m_j=\sum_{j=1}^n c_j\implies\sum_{j=1}^n m_j-\sum_{j=1}^n c_j=0\implies\sum_{j=1}^n(m_j-c_j)=0$$

There will exist some $k$, $1\le k \le n$, that minimizes $$\sum_{j=1}^k(m_j-c_j)$$

Start at branch $s_{k+1}$, or $s_1$ if $k=n$.

This makes the minimum point in the cycle the point where the salesman has zero money; that is, there will be no point in the cycle where the salesman has less than zero money, as required.

Edit:

An equivalent problem replaces revenue with gasoline and flying with driving. References:

n number of cans on a circular track will traverse a car around it

Alternative solution and generalization to a puzzle "gasoline crisis".

Cut the Knot: Gasoline Stations on a Circular Track

Answer 2

You are guaranteed to find such a starting point in the following way:

First, just start at $a_1$, go around, and keep track of how much money you have, even if it is negative at times.

For example:

(the number by node $a_i$ is $m_i$, and $c_i$ is placed along the arrow from $a_i$ to $a_j$)

So, starting at $a_1$ with $0$, we successively get:

$$0,2,-1,2,0,1,-1,3,-1,4,0$$

Note that of course we started and ended up with $0$, and this will be true for any starting node.

So, pick the node where you were at a minimum, which actually happens 3 times: you are at $-1$ right before you get to node $a_2$, $a_4$, and $a_5$. If you now pick one of these, say $a_2$, and you start going around from $a_2$, then you get:

$$0,3,1,2,0,4,0,5,1,2,0$$

And here of course all values are $\ge 0$, because at $a_2$ you were at a 'dip' of the original sequence, so you cannot get below that, and since this time you started at $a_2$ with $0$, you won't get below $0$.

I think it is clear that this idea generalizes to any graph: going around, there has to be a point where your money is at a minimum, so choose your starting point there.