Find the maximum distance covered using n bikes

Problem

There are n bikes and each can cover 100 km when fully fueled. What is the maximum amount of distance you can go using n bikes? You may assume that all bikes are similar and a bike takes 1 litre to cover 1 km.

Solution

There are couple of ways. Lets find the right solution. Say n = 50.

Naive Solution:

The most naive solution would be to just make all the bikes go together. Hence, the maximum distance travelled will be 100km.

Better Solution:

Move all the bikes 50km, so that each bike has half tank empty.

Now pour the fuel of 25 bikes (whose tanks are half filled) into other 25 bikes. Now we have 25 bikes will full tanks and these 25 bikes can go upto 100km each

Repeat the same after next 50 km.

Hence the number of bikes will go down after every 50 km, like:

50 -> 25 -> 12 -> 6 -> 3 -> 1

Total distance covered will be 5*50 + 100= 350 kms (At the end you have a bike filled with 100km fuel).

Note: You can further optimize few more km, because we are ignoring one bike’s (50 km fuel) when 25->12 and 3->1.. Since it is not the best solution, I have ignored that.

Best Solution (Actual solution) :

In this solution we will vacate the tank of a bike as soon as there is capacity in other bikes (not waiting for 50 km). Lets do it by breaking into the cases. 

Case 1 - Only 1 bike - The biker will drive for 100 km

Case 2 - Only 2 bikes -  Both bikers will drive to the point such that first biker can transfer the fuel to the other guy. So, for the 1st 50km they will go together, and then the fuel in both will be 50L and then 1st biker will give fuel to the other biker, and that biker will cover the rest with 100L of fuel.

So, Distance = Distance covered together + distance covered by fuel transfer = 50 + 100 = 150 km

Case 3 - Only 3 bikes - All the bikers will travel together to the point where fuel of the 1st biker can fill the oil in other 2 bikes. So, first distance will be 33.3 km. After this other 2 bikers will take fuel from 1st one and it will become like the old case of 2 bikes. Answer = 33.3 + 150 = 100/3 + 100/2 + 100 /1 = 183.3 km.

So empty one bike into rest 49 bikes. (49*2 = 98).

Again travel a distance of 100/49km, that is sufficient to vacate the fuel of one more bike in other 48 bikes.

The actual number of km traveled will be:

= 100/50 + 100/49 +......+100/1 = 

= 449.92 km

References
http://www.geeksforgeeks.org/find-maximum-distance-covered-100-bikes/
http://www.ritambhara.in/maximum-distance-with-50-bikes-each-having-fuel-capacity-of-100-kms/