7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you mean does this strategy instead of "does a strategy" ? $\endgroup$ – Mea Culpa Nay Sep 8 '17 at 8:58
  • $\begingroup$ @MeaCulpaNay I think the sentence is perfectly fine. The question is asking about the existence of any strategy, not whether a certain strategy works. $\endgroup$ – boboquack Sep 8 '17 at 9:07
  • 2
    $\begingroup$ If you car starts empty. How does one even get to the first canister? You won't be able to start your car. $\endgroup$ – Totumus Maximus Sep 8 '17 at 11:17
  • 1
    $\begingroup$ Does one or does one not know the location and quantity of fuel in each canister? $\endgroup$ – wizzwizz4 Sep 8 '17 at 19:28
  • 1
    $\begingroup$ Does "up to you to decide" imply that I know the amount of fuel in my starting canister and the distance to the next one? $\endgroup$ – willoller Sep 8 '17 at 21:13
10
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ As a matter of fact, isn't your solution using backward induction rather? $\endgroup$ – sousben Sep 8 '17 at 11:04
  • $\begingroup$ It doesn't look like it is; it proves its case for k = 1 and then for k = i + 1 given it's true for k = i. That's pretty standard induction. $\endgroup$ – BlueHairedMeerkat Sep 8 '17 at 14:21
  • $\begingroup$ There is no reason stated that canister 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$ – willoller Sep 8 '17 at 21:04
  • $\begingroup$ @willoller You're right. I haven't said that 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$ – boboquack Sep 8 '17 at 21:42
  • $\begingroup$ Oh, because the question was "does a strategy exist", not "what is the strategy"; that is, prove you can always complete the lap from at least one position. $\endgroup$ – willoller Sep 8 '17 at 21:52
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice insights, and thanks for posting additional solutions. What does it change if you can chose the direction? $\endgroup$ – sousben Sep 8 '17 at 11:13
  • $\begingroup$ Not much really. But if you can choose a direction, then the statement to prove is weaker. So it would be entirely possible that the weaker version is solvable, but the stronger one is not. It's interesting that with double the gas you can find one to both directions. I'd be interested if you really need to double the resources? Btw, where did you get this puzzle from? $\endgroup$ – GregT Sep 8 '17 at 11:25
  • $\begingroup$ A friend of mine was asked this puzzle in a job interview $\endgroup$ – sousben Sep 8 '17 at 11:28
  • $\begingroup$ It's a tough puzzle for a job interview, unless your friend is a mathematician. I've though a long time about it before I came up with a solution. I guess it was a top company, like Google (but they don't ask puzzles any more). $\endgroup$ – GregT Sep 8 '17 at 11:31
  • 1
    $\begingroup$ Well, he seems like an expert puzzler. Maybe he also knew the solution. But at the job interview, probably they were looking more for thinking patterns rather than the correct solution. $\endgroup$ – GregT Sep 8 '17 at 11:57
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Solutions #3 and #4 at my answer are also constructive. $\endgroup$ – GregT Sep 14 '17 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.