You go to a race track and are provided a car that can run exactly one lap with one liter of gas.
The gas tank starts empty but a random number of canisters are placed on the track, each one containing a random amount of gas.
However, the amount of gas contained in all of the canisters adds up exactly to one liter.
The initial position of the car on the track is up to you to decide. Does a strategy exist that always allows you to finish a lap?
The answer is:
Yes
Since:
We will use induction. First, suppose there is one canister. Then it contains 1 litre of fuel and we can start from there and drive around the race track.
Now suppose there are k+1 canisters (with k a positive integer, of course). If no canister has enough fuel to drive to another canister, there must be less than a litre of fuel in total, since the total proportion of the race track that could be driven is less than 1 and the whole race track is equivalent to one litre of fuel. But suppose you can drive from canister A straight to canister B using only the fuel in canister A - then canister A may as well contain the fuel for both canisters, since you can always pick up the fuel in canister B if you pick up the fuel in canister A. So then we can just consider the case with k canisters where A and B are merged at the location of A.
Note:
This argument doesn't work for an infinite number of canisters.
k(0) will have enough fuel to reach k(1), since you are starting with an empty tank, and the canisters are filled randomly. So there must be potential sets of canisters and starting canisters (starting positions) which cannot be completed, where k(0..n) is not enough fuel to reach a particular k(n+1).
$\endgroup$
Commented
Sep 8, 2017 at 21:04
k(0) has enough fuel to reach k(1). Rather, that there exists i such that k(i) has enough fuel to reach k(i+1). Thus whenever we pick up canister k(i) we are guaranteed to be able to pick up canister k(i+1), and so we may as well treat them as one canister.
$\endgroup$
Commented
Sep 8, 2017 at 21:42
I'd like to add to the puzzle description that the direction of traversal is fixed, you cannot choose it (I cannot comment yet).
Boboquack's solution is perfect, with the remark that it might be possible to make this argument work for infinite numbers, by using integration. I'd like to add a few more solutions.
Solution #2 (Source in mathematics journal KöMaL, in Hungarian)
The beginning is the same (using induction, for one canister the statement is true, suppose we have k+1 canisters and we already proven for k canisters). If we can reach the next canister from each one, the statement is trivial. Let's indirectly assume there is a canister A from where you cannot reach the next one. We can delete the canister with the road segment from A for which the gas is enough. This way, the total gas is still enough for the remaining circle, and we can use our previously proven statement. (Note that the problem and the solution at the link is slightly different: it has TWICE the gas needed for one lap with the stipulation that you have to be able to go around in either direction.)
Solution #3 (mine)
Let's color the racetrack. For each canister, choose a different color, and starting from the canister, color the racetrack as long as the gas is enough for the car. If you reach another canister, switch to it's respective color, then switch back when it's fuel is depleted. Then switch the color back. This way the each colored line will end as far as you can go by starting there. At the end, the whole race track will be colored. So if you choose the canister you started from during the last run, it will work.
Solution #4 (heard from this guy, maybe I'm paraphrasing a bit)
Draw a graph. The x axis represents the length of the track, the y axis is the amount of gas in our virtual gas tank. It's virtual, because we allow negative values as well. This graph has a value of 0 at the beginning and the end, and you have at least one minimum (just before a canister). If you start from that canister, you can go around.
The answer is yes, and I'll identify the point to start at.
Boboquack's solution is great, but I wanted a constructive proof.
This problem is asking about the partial sum of a series. If we define $f_i$ as the fuel at point $i$ and $d_i$ as the amount of fuel we'll burn driving between point $i$ and point $i+1$, then the fuel left in our tank at point $i$, starting from point $0$, is the partial sum:
$$ Y_j = \sum_{j=0}^{i-1} f_j - x_j $$
There are $n$ points, and $Y_n = 0$ because our fuel sums to 1 liter and our lap would consume a liter of fuel. $Y_0 = 0$ because it's the sum of $0$ to $0$.
We want to know if there is an intermediate point $k$ such that if we started our sum at $k$, wrapped it around at $n-1$ to go back to point $0$ and got back to $k$, every element in that sum (call that sum $S^k_j$) would be non-negative. i.e. if $\forall j S^k_j \geq 0$
We need $S^k_j$ in a simple form, so we'll first add elements between $k$ and any other point $j \geq k$.
This is simply $S^k_j = Y_j - Y_k, \forall j \geq k$.
The more difficult sum is when we start at point $k$, go past all points, and start the sum again at the beginning.
The sum between $k$ and $n$ is $Y_n - Y_k$. The sum between $0$ and $j$ is $Y_j - Y_0$. Adding these together, we get $Y_n - Y_k + Y_j - Y_0$. But both $Y_n$ and $Y_0$ are zero, giving us $S^k_j = Y_j - Y_k, \forall j < k$
Combining these two, we get a simple equation:
$S^k_j = Y_j - Y_k, \forall j$.
Now we can restate the riddle as: can we ensure this quantity is always non-negative?
Sure: if we start at point $k$ and $Y_k$ is the smallest $Y_i$, we will always make it around the circle.
This analysis can be done with integrals and continuous gas cans, with the same result. I actually did that first because integrals are more fun than series summations.
