Optimizing Fuel Usage on a Circular Route with Squares: A Mathematical Proof

[mathmari]

Hey!

I am looking at an exercise that is formulated as follows: Finite number k of squares on a circular route. The whole fuel in all is enough for 1 circle.

Show that there is a way to integrate the circle however the squares and the fuel are distributed. There is also the following picture:

View attachment 8472 I haven't really understood the exercise statement. Could you explain that to me? What exactly do I have to show? (Wondering)

 

[I like Serena]

Hey!

I am looking at an exercise that is formulated as follows: Finite number k of squares on a circular route. The whole fuel in all is enough for 1 circle.

Show that there is a way to integrate the circle however the squares and the fuel are distributed. There is also the following picture:

I haven't really understood the exercise statement. Could you explain that to me? What exactly do I have to show? (Wondering)

Hey mathmari!

Here's my best guess for the interpretation.

Every square corresponds to a fuel stop with some amount of fuel $f_i$ where $i=1, ..., k$.
The total amount of fuel is exactly what is needed to travel the complete circle.
Show that however the fuel is distributed over the fuel stops, that we can always find a starting point that allows us to travel the complete circle without running out of fuel. (Thinking)

 

[mathmari]

Here's my best guess for the interpretation.

Every square corresponds to a fuel stop with some amount of fuel $f_i$ where $i=1, ..., k$.
The total amount of fuel is exactly what is needed to travel the complete circle.
Show that however the fuel is distributed over the fuel stops, that we can always find a starting point that allows us to travel the complete circle without running out of fuel. (Thinking)

Ahh ok! That makes sense! (Nerd) Is this problem related to the set cover problem?

Can we solve that problem with deterministic or non-deterministic machines?

(Wondering)

 

[I like Serena]

Ahh ok! That makes sense! Is this problem related to the set cover problem?

Can we solve that problem with deterministic or non-deterministic machines?

Could be. (Thinking)

Either way, I'm inclined to solve it with analysis techniques.

Let $s$ be the distance along the circle starting from the rightmost point.
Let $s_i$ be the distance where square/fuel stop $i$ is located ($i=1,...,k$).
Let $f_i$ be the fuel at $s_i$.
Let $f(s)=\sum\limits_{s_i<s} f_i - s$.
Then $f(s)$ is the amount of fuel we have at $s$ if we start from the rightmost point and if we allow our fuel to become negative.
Let $s_0 = \underset{s}{\operatorname{arg\,min}} f(s)$.
Then starting at $s_0$ solves the problem. (Thinking)

 

[mathmari]

Let $s$ be the distance along the circle starting from the rightmost point.

So, is $s$ the distance between the starting point and our current position? (Wondering)

Let $s_i$ be the distance where square/fuel stop $i$ is located ($i=1,...,k$).

$s_i$ is the distance between the starting point and the fuel stop $i$, or not? (Wondering)

Let $f_i$ be the fuel at $s_i$.
Let $f(s)=\sum\limits_{s_i<s} f_i - s$.
Then $f(s)$ is the amount of fuel we have at $s$ if we start from the rightmost point and if we allow our fuel to become negative.

So, we add the fuel till the current position and we subtract the distance that we have done so far, and that is the fuel that we have now. Have I understood that correctly? (Wondering)

Let $s_0 = \underset{s}{\operatorname{arg\,min}} f(s)$.
Then starting at $s_0$ solves the problem. (Thinking)

What exactly is $s_0$ ? I haven't really understood that part. (Wondering)

 

[I like Serena]

So, is $s$ the distance between the starting point and our current position?

It's the arc distance along the circle.
That is, $s=r\phi$ if we have a circle with radius $r$, and if we are at angle $\phi$ with the positive x-axis. (Thinking)

$s_i$ is the distance between the starting point and the fuel stop $i$, or not?

The arc distance.

So, we add the fuel till the current position and we subtract the distance that we have done so far, and that is the fuel that we have now. Have I understood that correctly?

Yep.

What exactly is $s_0$ ? I haven't really understood that part.

The arc distance $s_0$ is the $s$ for which $f(s)$ takes its minimum value. (Thinking)

 

[mathmari]

It's the arc distance along the circle.
That is, $s=r\phi$ if we have a circle with radius $r$, and if we are at angle $\phi$ with the positive x-axis. (Thinking)

Ah ok!

The arc distance $s_0$ is the $s$ for which $f(s)$ takes its minimum value. (Thinking)

And what happens when $f(s)$ is negative? (Wondering)

 

[I like Serena]

Ah ok!

And what happens when $f(s)$ is negative?

We'll find an $s_0$ where $f(s)$ is the most negative.
If we start from that $s_0$ instead of from the rightmost point, we'll have fuel at all times. (Thinking)

 

[mathmari]

We'll find an $s_0$ where $f(s)$ is the most negative.
If we start from that $s_0$ instead of from the rightmost point, we'll have fuel at all times. (Thinking)

I haven't really understood that part. Could you explain it further to me? (Wondering)

 

[I like Serena]

I haven't really understood that part. Could you explain it further to me? (Wondering)

Let's pick an example.
Suppose we have a circle with circumference $10$.
The total fuel is $10$ as well.
Let's pick $k=2$, $s_1=3$, $s_2=6$, and let's pick $f_1=2$, $f_2=8$.
Then we have:
\begin{tikzpicture}
\def\xmin{0}
\def\ymin{-4}
\def\xmax{10}
\def\ymax{8}
\draw[help lines] (\xmin,\ymin) grid (\xmax,\ymax);
\draw[<->] (\xmin,0) -- ({\xmax+0.4},0) node

{$s$};
\draw[<->] (0,{\ymin-0.4}) -- (0,{\ymax+0.4}) node

{$fuel$};
\draw foreach \i in {\xmin,...,\xmax} { (\i,0.1) -- (\i,-0.1) node[below] {$\i$} };
\draw foreach \i in {\ymin,...,\ymax} { (0.1,\i) -- (-0.1,\i) node

{$\i$} };

\draw[red, ultra thick] (3,0) node[above right] {$s_1$} -- (3,2) node

{$f_1$};
\draw[red, ultra thick] (6,0) node[above right] {$s_2$} -- (6,8) node

{$f_2$};
\draw[blue] (0,0) -- (3,-3) -- (3,-1) -- (6,-4) node[above right] {$f$} -- (6,4) -- (10,0);
\end{tikzpicture}

In this diagram we assume we start at $0$, meaning we get negative fuel.
We will end at $10$ with zero fuel, since it is given that we have exactly the fuel we need to travel the complete circumference.
If we want to make it without negative fuel, we need to start at either $s_1$ or $s_2$.
Where should we start to make it around without negative fuel? (Wondering)​

 

[mathmari]

Is the most negative $f$ always at the same point where a $s_i$ is maximum? (Wondering)

 

[I like Serena]

Is the most negative $f$ always at the same point where a $s_i$ is maximum? (Wondering)

Not necessarily.
Consider for instance:
\begin{tikzpicture}
\def\xmin{0}
\def\ymin{-4}
\def\xmax{10}
\def\ymax{8}
\draw[help lines] (\xmin,\ymin) grid (\xmax,\ymax);
\draw[<->] (\xmin,0) -- ({\xmax+0.4},0) node

{$s$};
\draw[<->] (0,{\ymin-0.4}) -- (0,{\ymax+0.4}) node

{$fuel$};
\draw foreach \i in {\xmin,...,\xmax} { (\i,0.1) -- (\i,-0.1) node[below] {$\i$} };
\draw foreach \i in {\ymin,...,\ymax} { (0.1,\i) -- (-0.1,\i) node

{$\i$} };

\draw[red, ultra thick] (3,0) node[above right] {$s_1$} -- (3,4) node

{$f_1$};
\draw[red, ultra thick] (6,0) node[above right] {$s_2$} -- (6,6) node

{$f_2$};
\draw[blue] (0,0) -- (3,-3) -- (3,1) -- (6,-2) node[above right] {$f$} -- (6,4) -- (10,0);
\end{tikzpicture}
(Thinking)​

 

[mathmari]

Ah ok! But I am still facing some difficulties understanding that. (Thinking)

The most negative value of $f$ is at position 3. So we start from there. Then we continue to the right side. If we reach at the position 10 we have to go again to the part 0 to 3 of the axis, or not? Do we have fuel if we are at the part 0-3 ? (Wondering)

 

[I like Serena]

Ah ok! But I am still facing some difficulties understanding that. (Thinking)

The most negative value of $f$ is at position 3. So we start from there. Then we continue to the right side. If we reach at the position 10 we have to go again to the part 0 to 3 of the axis, or not? Do we have fuel if we are at the part 0-3 ? (Wondering)

Yes, the resulting diagram is:
\begin{tikzpicture}
\def\xmin{0}
\def\ymin{-4}
\def\xmax{13}
\def\ymax{8}
\draw[help lines] (\xmin,\ymin) grid (\xmax,\ymax);
\draw[<->] (\xmin,0) -- ({\xmax+0.4},0) node

{$s$};
\draw[<->] (0,{\ymin-0.4}) -- (0,{\ymax+0.4}) node

{$fuel$};
\draw foreach \i in {\xmin,...,\xmax} { (\i,0.1) -- (\i,-0.1) node[below] {$\i$} };
\draw foreach \i in {\ymin,...,\ymax} { (0.1,\i) -- (-0.1,\i) node

{$\i$} };

\draw[red, ultra thick] (3,0) node[above right] {$s_1$} -- (3,4) node

{$f_1$};
\draw[red, ultra thick] (6,0) node[above right] {$s_2$} -- (6,6) node

{$f_2$};
\draw (10,\ymin) -- (10,\ymax);
\draw[blue, dashed] (0,3) -- (3,0);
\draw[blue] (3,4) -- (6,1) -- (6,7) node[above right] {$f$} -- (10,3) -- (13,0);
\end{tikzpicture}

It's really a periodic function.
Changing the starting point corresponds to changing the y-level so that the starting point is at fuel-level 0.​

 

[mathmari]

Ah ok! I think I got now the idea!

If at some point of the route we are out of fuel, we consider that point as the starting point of the route, that means that we get some fuel from that fuel stop so we start with a positive amount of fuel. At the remaining route we always have enough fuel, since we change the y-level and now everything is at the positive part of the $f$-axis.

Is that the correct idea? (Wondering) But how can we prove formally that starting each time at $s_0 = \underset{s}{\operatorname{arg\,min}} f(s)$ will solve the problem? (Wondering) Could we solve that problem with deterministic or non-deterministic machines? (Wondering)

 

[mathmari]

Can we maybe show the statement by induction?

Base Case: We have $k=1$ fuel stop, that means that we start from the fuel stop, we get all the fuel that we need for the whole route, and we get to the end of the route and we will never run out of fuel.

Inductive Hypothesis: We suppose that the statement holds for $k=n$ fuel stops, i.e. however the fuel is distributed over the $k=n$ fuel stops, we can always find a starting point that allows us to travel the complete circle without running out of fuel.

Inductive step: We want to show that the statement holds also for $k=n+1$.
From the inductive hypothesis we can go along the circular route with $n$ fuel stops without running out of fuel. Now we consider $n+1$ fuel stops. We could get some fuel from the $n$-th fuel stop and use that for the last $(n+1)$-th fuel stop. Would we get then the desired result?

Or do we not have then "however the fuel is distributed over the fuel stops" ?

Or can we not use the induction here?

(Wondering)

 

[I like Serena]

We would indeed not achieve what we want to achieve.
I think we can't really do it with induction.
Instead we can observe that f is a periodic function. And if we start at a minimum, we get a fuel usage that is f shifted upwards so that it is positive.
This holds true for any distribution of the fuel, which completes the proof.

To find the solutions we can iterate through the minima iteratively. We can have multiple absolute minima, but we can deterministically find all of them in linear time. So all solutions can be found with a deterministic machine.

 

[mathmari]

We would indeed not achieve what we want to achieve.
I think we can't really do it with induction.

Ah ok

To find the solutions we can iterate through the minima iteratively. We can have multiple absolute minima, but we can deterministically find all of them in linear time. So all solutions can be found with a deterministic machine.

What exactly is meant by "we can deterministically find all of them in linear time" ? (Wondering)

 

[I like Serena]

What exactly is meant by "we can deterministically find all of them in linear time" ? (Wondering)

Let me read up again on deterministic machines... (Time)

A deterministic Turing machine reads a tape with a set of input symbols, which it either accepts or rejects.
In our case, the input can be the set of fuel locations, the fuel amounts, and one of the fuel locations that may be a solution.
The machine will accept the input if the presumed solution is an absolute minimum of $f$, and otherwise it rejects it.
That can be done deterministically can't it? (Thinking)

If additionally we can solve the problem in polynomial time, the problem is said to be in 'P' (see P-complexity).
We can iterate over each fuel location once and verify that the value of $f$ that we find for the supposed solution, is equal or less than any other value that we find. That is, we can do this in polynomial time (and actually linear time). (Thinking)

 

[mathmari]

Instead we can observe that f is a periodic function. And if we start at a minimum, we get a fuel usage that is f shifted upwards so that it is positive.
This holds true for any distribution of the fuel, which completes the proof.

Is $f$ periodic because we consider the distance along a circle? (Wondering)

 

[I like Serena]

Is $f$ periodic because we consider the distance along a circle? (Wondering)

That is half of it.
Yes, after completing the circle we are again in the same situation.
In addition, it is given that we have exactly the amount of fuel to complete the circle.
It means that - if we allow negative fuel, or sufficient initial fuel - at start and end we will have exactly the same amount of fuel. (Thinking)