2
$\begingroup$

Suppose there are a number of cars at the start line of circular racing track with a fueling station. Each car can carries enough fuel to drive exactly half a lap. The cars can either refuel at the finish line or transfer any amount of fuel from one car to another when they are next to each other. I am tasked to find the minimum number of cars required for at least one car to finish a loop.

My intuition tells me to approach this problem using a geometric series, but I don’t even know how to model the problem correctly. Please advise, and thank you!

$\endgroup$
3
$\begingroup$

If cars can go backwards and refuel at the start line, then 3 cars are enough:

  • Cars A and B both go out to the 0.2 lap mark and wait there.
  • Car C now uses one full tank to go out to the 0.2 lap mark, donate fuel for 0.1 lap to either A or B, and return to the start line.
  • Repeat the above step four times. Cars A and B now each has a full tank.
  • Car C refuels one last time and all three cars proceed to the 0.3 lap mark. They now have fuel for exactly one lap between them, which they split between car A and B.
  • A and B go together to the 0.5 lap mark.
  • Car B has 0.3 lap of fuel, and donates 0.2 of it to A.
  • A now has a full tank and completes the remaining half-lap alone.
| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Let us consider the most efficient use of two cars. They start with a full tank. After $1/4$ lap each car is half full. Now all the remaining fuel just fits into one car, so this is the optimal time for the second car to make its sacrifice. The refilled car then gets $(1/2)+(1/4) = 3/4$ of the way around, the first $1/4$ plus the $1/2$ it gets after refill.

For three cars, they go $1/6$ of the way around the track and then one car can give up its fuel to give the remaining two cars full tanks, giving us the situation above. Now one car ultimately gets $(1/2)+(1/4)+(1/6) = 11/12$ of a lap.

Do you see how the series is developing? What would be the next term if we try adding a fourth car? Is that enough to get the sum greater than or equal to a lap?

In a variation of this problem, we might require each "sacrificial" car to retain enough fuel to go back to the start under its own power. Then the series would be $(1/2)(1+(1/3)+(1/5)+(1/7)+...)$ and we would need eight cars to get a net full lap for one of them.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.