TransWikia.com

Induction. Circular track and fuel stations

Mathematics Asked on November 9, 2021

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.

2 Answers

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.

Answered by Dylan on November 9, 2021

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.

Answered by shai horowitz on November 9, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP