1

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.

This question has been asked here before but I don't really understand the answers. I'd like to solve this by induction.

Parseval
  • 6,413
  • Does the car start out with any gas, or does the car have to start next to a gas can? – Franklin Pezzuti Dyer Jun 27 '17 at 20:46
  • Does it really matter? @Nilknarf – shai horowitz Jun 27 '17 at 20:48
  • 1
    @shaihorowitz Nah, not really. Just wondering. :P – Franklin Pezzuti Dyer Jun 27 '17 at 20:50
  • You must assume that the car starts without gas. If it has a full tank, then it can circle the track without needing any cans. – Doug M Jun 27 '17 at 20:52
  • Car starts with no gas att all. So one has to find a good starting point such that the car is allowed to circle completely. – Parseval Jun 28 '17 at 06:15
  • I asked this same question last year (it's from some Spanish math contest if I remember correctly). Not sure about an inductive solution, but there's a very nice solution here: https://math.stackexchange.com/questions/1611350/showing-there-exists-a-sequence-that-majorizes-another – Max Jun 29 '17 at 20:43

2 Answers2

2

We proceed by induction on $n$, which is the number of cans.

In the case that $n=1$, it is clear that the result holds since the $1$ can that exists contains sufficient fuel for the car to travel around the track, and so we can place the car at this $1$ can of fuel, let it fill up with the fuel that is in the can, and then travel around the track.

Now suppose that the result holds for every possible placement of $n$ cans and any possible division of the total fuel into those cans.

Consider an arrangement of $n+1$ cans. Since the total amount of the fuel in the cans is sufficient to travel around the track, at least one of the cans contains enough fuel for the car to travel to the next can. (As otherwise the total amount of fuel would only be enough to cover a distance strictly smaller than the total distance between the cans, which is of course the distance around the track.)

Consider this can that contains enough fuel to get to the next can. Call it $C$. Let the can which appears after $C$ be called $D$, and imagine adding the fuel contained in $D$ to the fuel contained in $C$. This gives us an (imaginary) arrangement of $n$ cans which together contain enough fuel to travel around the track, and so by the induction hypothesis, there is a point on the track where we can place the car so that it can travel around the track.

Place the real (non-imaginary) car at the same point on the track and let it start circling the track. It is then able to travel to $C$ since the real cans before $C$ are identical to the imaginary cans before $C$. There is enough fuel in the real can $C$ for it to reach the real can $D$, and so it can reach $D$. Once it reaches $D$, it tops up with the fuel contained in $D$, and then it has exactly the same amount of fuel as the imaginary car contains at this point on the track. Its journey from here on is therefor identical to the imaginary car's, and so it follows that it will be able to complete its journey around the track.

There is thus a location on the track where we can place the car such that it completes its journey around the track, and so the result follows by induction.

Dylan
  • 7,416
0

suppose there was one can, then it can be placed at the start. now suppose there are n cans positioned, this can get you $n/l$ of the track of length $l$. if you have $n+1$ cans then you have enough $n$ cans and can get $n/l$ at least with some combo if $n$ cans by first assumption. now you either have enough gas to make it around the track or the next gas can is placed within reach $n-$amount of gas of small can in distance$/l$ and you can get around the track.

shai horowitz
  • 2,086
  • You have assumed that the cans have equal quantities of gas. Futhermore, you have assumed that you can place the cans. The cans have been placed. You get to place the car. – Doug M Jun 27 '17 at 20:51
  • no, i used the induction step that there is a placement of n cans that can be placed to get you n/l the way there. it doesn't matter if there are equally spaced (amount of gas) cans just take the smallest as last can. @DougM – shai horowitz Jun 27 '17 at 20:52
  • I don't follow on this answer, can you elaborate? $n+1$ cans can get me $(n+1)/l=n/l+1/l$ of the track length, but how do I use the induction hypothesis here? – Parseval Jun 28 '17 at 06:45
  • furthermore, I want to show that no matter the amount of cans, I'd be able to go $l$ distance, whole circle and not $n/l$. – Parseval Jun 28 '17 at 06:47
  • will edit soon, the induction hypothesis is simply showing that the remaining can, may always be placed in the part of the track that you can get to. – shai horowitz Jun 28 '17 at 14:15