Gaadi chalao
Problem: A set of fuel dumps on a circular racetrack have just enough gasoline for one car to make one round trip. Prove that there exists a fuel dump from which one car, starting with an empty gas tank, can complete the round trip.
Source: Read it in many puzzle books. This form taken from Manku's blog.
Update (30/12/09) Solution: From the site cut-the-knot.org in comments!!
Source: Read it in many puzzle books. This form taken from Manku's blog.
Update (30/12/09) Solution: From the site cut-the-knot.org in comments!!
Let's prove it by induction. For 1 petrol pump it is trivial. Suppose it holds true for n petrol pumps. Now for the n+1 case pick one petrol pump which has petrol less than what is required to reach the next petrol pump and call it point A on the circle (Note that there will always be at least one such pump barring the trivial case where each pump has just enough fuel to reach the next one).
ReplyDeleteNow draw an arc on the circle, starting from this pump, and covering the distance equal to the petrol in this pump. Let's call the other endpoint B.
"Remove" this arc from the circle. Now the resulting circle with AB removed has n petrol pumps which have more petrol than the length. A solution exists for this from the induction hypothesis. But since there is an extra length of AB to be covered note that you can cover AB by using the petrol of petrol pump A only.
I hope the solution is clear. Drawing it on a paper would have been a better way to explain :)
Let D, F represent the length of circular track & the total amount of fuel available, respectively, at a given stage.
ReplyDeleteInitially D = F ; this is the invariant we maintain thru out the process.
First fix upon the direction ( clockwise/ anticlockwise ).
Going around the track in the chosen direction you are guaranteed to find a petrol pump, say A, which has more(sufficient) petrol than(that) is needed to cover the distance to the next petrol pump, say B,( or else it implies that D > F, which is not true).
Now we modify the track as follows :: we remove A and the track between A & B, and dump the excess petrol ( if any ) in to the next petrol pump B. Observe that we still have D = F on this modified track;
We will carry out this process, going around in the chosen direction, until there are 2 pumps left. We can argue case-by-case at this stage.
@Asad @Giridhar.. Your solution does not give me where to start. It cannot be the case that you can do it starting from any gas station.
ReplyDeleteNice solution at http://www.cut-the-knot.org
Imagine having a big tank with enough gas for a round trip and enough room for going through the motions of emptying every gas station on your way. Start at any station and mind to record the amount of gasoline on reaching gas stations on your way around. At the end of the trip, when you pull into the station of departure with the original amount of gas, check your list. The station marked with the least number is the one where you want to start on an empty tank.
Proof:
Assume the least amount in question was, say, K gallons. Assume also you can start your second trip with this amount of gasoline. As before, as you go, record the amounts of fuel on reaching the gas stations on your way around the trek. The list of numbers will be the same as on the first trip but shifted circularly. Thus if you remove K from each of the numbers on the list, none of the numbers will become negative.
You asked only for the proof, not the solution :).
ReplyDeleteNonetheless, the starting point can be found out from my solution by working backwards. (Note that A, the starting pump, has lesser fuel than what is required to cover the distance. If we work backwards, removing pumps and shortening the circle, we would reach the case n=1 which will give the starting point).
@Asad.. Your solution is correct.. I understand it now. Thanx :)
ReplyDeleteEven my solution gives starting point. At each stage, solution for the modified track can be extended to get the solution for the original track.
ReplyDelete@Giridhar.. Sorry again.. I misinterpreted your and Asad's solutions. They are correct. Thanks.
ReplyDelete@Pratik,
ReplyDeletecan you explain this statement in more detail, possibly with some example :
"Assume the least amount in question was, say, K gallons. Assume also you can start your second trip with this amount of gasoline. As before, as you go, record the amounts of fuel on reaching the gas stations on your way around the trek. The list of numbers will be the same as on the first trip but shifted circularly. Thus if you remove K from each of the numbers on the list, none of the numbers will become negative."
Nice qs btw :)
@Himanshu,
ReplyDeleteRephrasing the solution- Suppose in the algorithm when you begin with lots of gas. When you are doing the trip, say the lowest gas fill across time is K gallons. So, at some particular time, tank had K gallons and at all other times, it had greater than K gallons. The solution is just that, if you start with this point, i.e. with 0 gallons of gas, at all points you have something positive (as K is the minimum filled amount across time). So, one can be sure that if you are starting from this point, you will complete the trip. I hope that clarifies it. Best!
@Pratik.
ReplyDeleteUnderstood the solution..Thanks ya!!
I want to know if this could be a possible solution:
ReplyDeleteLets say there does not exist any fuel dump from which one car, starting with an empty gas tank, can complete the round trip. so it means irrespective we start from any fuel dump, on the way from some fuel dump we will not be able to reach the next fuel dump.
Now lets say there are r fuel dumps with {x1, x2, ....xR} fuel .
Given (x1+x2+...XR)*k=2*Pie*R where k is the dist travelled in 1 litre fuel.
Lets say we start at the station containing x1 fuel. and last fuel pump reached was xJ i.e we couldn't reach x(J+1).
that is (x1+x2+..xJ)<2*Pi*R-(XJ+1+...xR) which is a contradiction.
x1 could be any fuel pump therefore our assumption is wrong.
@Unknown, I did not think of the word "circular" as a circle type circular. The other solutions presented do not need to assume anything about the shape. It just means that its a round trip around a point.
ReplyDelete@Pratik: ohhhh Thnx
ReplyDeletebut if once we can ignore that I used 2*Pie*R thing and consider it for a general arbitrary path then also it seems logical to me that we could find atleast one segment of the path which the car would not be able to cover and hence contradicting the assumption.
If the above approach is correct?????