1
$\begingroup$

The problem

The sides of a circular track contain a sequence of cans of gasoline. The total amount in the cans is sufficient to enable a certain car to make one complete circuit of the track, and it could all fit into the car's gas tank at one time. Use mathematical induction to prove that it is possible to find an initial location for placing the car so that it will be able to traverse the entire track by using the various amounts of gasoline in the cans that it encounters along the way.

My solution

Given any sequence of cans, we know that the sum of all the gasoline will traverse the car around the entire track. What is not known is the initial location of the car.

Basis step: The track has $1$ can, therefore the car will be able to traverse the track from some starting point.

$S(1) =$ some starting point; $S(1) = p_1$, where $p_1$ is the initial starting point.

Induction hypothesis: $S(k) = p_k$, such that $p_k$ is some starting point that, when traversing the track, if at any point on the track the car runs out of fuel, that point will not work. In order to find $p_k$, one will have to exhaust all possible finite points on the track in order to find the initial point that will traverse the car around the track where some nth tank will have enough fuel to get to the next tank.

Thus, $S(k + 1) = p_{k + 1}$, where $p_{k + 1}$ is some point. If at any point in traversing the track the car runs out of fuel, the chosen $p_{k + 1}$ will not work. A car will run out of fuel if it cannot travel from some $n$-th fuel tank to the $(n + 1)$-th fuel tank.

Done.

Is this right?

  • 0
    While not an answer, this question is somewhat similar to: http://programmers.stackexchange.com/questions/119827/can-anyone-help-solve-this-complex-algorithmic-problem2012-03-12

1 Answers 1

4

I’m afraid that this makes very little sense. First, the basis step for this argument consists in showing that if there is one can of gas, there is at least one starting point on the track from which the car will be able to complete a circuit. You have not proved that this is true: you’ve merely asserted it. In order to prove it, you must either specify at least one successful starting point or show in some other manner that there is one. In fact there is only one; what is it, and why does it work?

Like joriki, I can’t make much sense of your argument in the induction step. What you need to show is that IF there is always a successful starting point when there are $k$ cans of gas, THEN there is always a successful starting point when there are $k+1$ cans of gas. You seem instead to be drawing some conclusion about unsuccessful starting points. Let me see if I can get you started in the right direction without actually doing the argument for you.

Notice that a successful starting point must always be at one of the cans of fuel. (Why?) Suppose that there’s always a successful starting point whenever there are $k$ cans, and consider a track with $k+1$ cans.

  1. There must be at least one can that contains enough gas to reach the next can. (Why?) Call it Can $1$.

  2. Let Can $2$ be the next can after Can $1$. Imagine combining all of the gas from Cans $1$ and $2$ in Can $1$ and throwing away Can $2$. You now have $k$ cans, so there’s a successful starting point.

  3. Show that the same starting point works for the original $k+1$ cans.

  4. Conclude that IF there is always a successful starting point when there are $k$ cans, THEN there is always a successful starting point when there are $k+1$ cans.

Once you’ve done all this, you’ll be justified in concluding that for all $k\ge 1$ there is always a successful starting point.

  • 0
    I don't follow here. Can you please elaborate more on point 2?2017-06-27