From Sanandan Swaminathan comes a logic puzzle about a picturesque drive, and getting by with a little help from your friends:
There is a circular road, along which travelers can drive in either direction. However, there is only one gas station on the loop. Driving the full loop in your car requires 40 gallons of gas, but your car’s fuel tank has a maximum capacity of 20 gallons. That said, you’d love to see every last spot along the route.
Of course, you can’t achieve this with just your own car. Fortunately, you can call on any number of your Fiddler Nation friends, all of whom happen to have the same make and model car as you, each with a 20-gallon fuel tank and identical fuel efficiency.
Now, all the cars, including yours, must start and end at the gas station. However, only your car must cover the entire route. The gas station can be visited (and refueled at) by any car, any number of times. Cars may also transfer fuel from one to another, provided they meet up together at a spot along the route.
What is the smallest number of cars (including yours) needed for you to see every spot on the circular route?
(Note: There’s no “cheating” here. No towing or pushing of cars. Every car must be driven on its own, and by one person. No jerrycans for lugging around extra fuel, and so on and so forth.)
If you are the only car, you can only go a maximum of $\frac{1}{4}$ of the circular road from the gas station, as you need the rest of your tank to go back to the gas station. If you go further than $\frac{1}{4}$ of the circular road, you will be stranded. Therefore, it is impossible.
Consider now that you are trying to make it around and you have a helper, $H_1$. $H_1$ will meet you anywhere and give you gas, but they always leave enough gas for themselves so they can make it back to the gas station. Similar to above, they will only go a maximum of $\frac{1}{4}$ of the circular road from the gas station.
This means the stretch from $\frac{1}{4}$ to $\frac{3}{4}$ around the track would have to be without the helper. There is no way only one other helper could provide gas for you and be able to return back to the gas station.
The minimimum is $3$ cars. See below for explanation.
Assuming you’ve used the smallest number of cars to complete your tour of the entire circular road, Sanandan offers the following as Extra Credit:
What is the minimum amount of gas collectively needed by all cars for this journey? (Remember, all the cars must begin and end at the gas station.)
A second helper, $H_2$, is now available.
You, $H_1$, and $H_2$ leave the gas station with $20$ gallons. $H_2$'s job is to ensure that you and $H_1$ have a full tank of gas before they turn around and go back to the gas station. This is a $\frac{20}{4} = 5$ gallon trip, or $\frac{1}{8}$ of the road. $H_2$ drove $5$ gallons worth, donated $5$ to you and $H_1$ so both of you are back to full tanks, and has $5$ gallons to return themself to the gas station
You and $H_1$ continue another $5$ gallon trip to $\frac{1}{4}$ mark of the road. They need $10$ gallons to get back to the gas station, so they transfer $5$ to you. You have a full tank at the $\frac{1}{4}$ mark.
You can drive unassisted to the $\frac{3}{4}$ mark in the road, but you will be empty. Fortunately, $H_1$ has drove back to the gas station, filled up, and meets you at the $\frac{3}{4}$ with $10$ gallons. They donate $5$ to you so both of you can drive to the $\frac{7}{8}$ mark.
As you and $H_1$ depart the $\frac{3}{4}$ mark, $H_2$ leaves with a full tank from the gas station to meet at $\frac{7}{8}$ mark. You and $H_1$ run down to empty at the $\frac{7}{8}$ mark, and $H_2$ has $15$ gallons, enough for 3 cars to make a $5$ gallon trip back to the gas station.
(Gas transfer is instantaneous. Even at the gas station.)
You drive the entire loop, which is $40$ gallons. While you are driving, $H_1$ is also always driving. They also use $40$ gallons. $H_2$ only drives between the gas station and the $\frac{1}{8}$ mark, as well as between the gas station and the $\frac{7}{8}$ mark. This is only $\frac{1}{2}$ the road distance, or $20$ gallons.
$$40 + 40 + 20 = 100 \text{ gallons}$$For a particular number of cars, what is the minimum tank size for each car $T$ that allows you to drive the full route and all helpers be able to start and stop at the gas station? $T$ is a fraction of that needed for the total road.
Optimization occurs when anyone leaving the gas station is full and arriving at the gas station is empty. Optimization should should also occur with a bit of symmetry.
You can travel the entire route as long as the car tank is greater than or equal to the amount needed for the road. The total gas consumed is that of the trip.
Define $x$ as some fraction of the road where $H_1$ gives you enough gas to travel $y$ to make it to $1-x$, and they still have the ability to get back to the gas station.
You and $H_1$ will drive to $x$, transfer, they will head back to the gas station and fill up. They will then meet you at $1-x$, transfer, and both of you will be empty upon arriving at the gas station.
For $H_1$ a full tank is $T = 2x + y$. For $H_1$'s final trip, a full tank is $T = 3x$. This yields $x = y$.
For you, $T+x = 1-x$. Substituting from above, $x = y = \frac{1}{5}$, and $T = \dfrac{3}{5}$ of that needed for the road.
The total gas consumed is $3$ full tanks, or $\dfrac{9}{5}$ of that needed for the road.
Using what we learned from 2 Cars, all cars will drive to $x$, $H_2$ will give you and $H_1$ enough gas to drive $x$ more each, and drive back to the gas station.
You and $H_1$ continue on to some fraction of the road $y$ where $H_1$ gives you enough gas to travel $z$ more, and they make it back to the gas station. You will then drive to $1-y$ and be empty upon arrival. They will meet you at $1-y$, give you enough gas so you will drive together to $\frac{3}{4}$ and both be empty. $H_2$ will meet and give a $\frac{1}{4}$ of a tank to each of you, so everyone returns to the gas station empty.
For $H_2$ a full tank $T = 4x$.
For $H_1$ a full tank $T + \frac{T}{4}= 2y + z$. For $H_1$'s final trip, $T = y + 2\cdot(y-\frac{T}{4})$ or $T = 2y$. This yields $T = 4z$.
For you, $T+x+z = 1-y$. Substituting from above, $T+\frac{T}{4}+\frac{T}{4}= 1-\frac{T}{2}$, or $T = \frac{1}{2}$ of that needed for the road.
The total gas consumed is $5$ full tanks, or $\dfrac{5}{2}$ of that needed for the road.
(Not symmetric)
Using what we learned from 2 Cars, all cars will drive to $x$, $H_2$ will give you and $H_1$ enough gas to drive $x$ more each, and drive back to the gas station.
You and $H_1$ continue to some fraction of the road $y$ where $H_1$ gives you enough gas $y-x$ to travel all the way back to the gas station. This time however, they will drive back to some fraction of the road $z$, where $H_2$ will meet them, transfer gas, and they will both return back to the gas station.
For $H_2$ a full tank $T = 4x = 3z$.
For $H_1$ a full tank $T + \frac{T}{4} = y + (y-x) + (y-z)$. Substituting from above, $T + \frac{T}{4} = 3y - \frac{T}{4} - \frac{T}{3}$, or $\frac{11T}{18} = y$.
For you, $T = 1-y$. Substituting from above, $T = \frac{18}{29}$ of that needed for the road.
The total gas consumed is $5$ full tanks, or $\dfrac{90}{29}$ of that needed for the road.
This is more gas than Option 1.
This gets very complicated...
| Number of Cars Needed | Minimum Tank Size | Number of Tanks Needed |
|---|---|---|
| $1$ | $1$ | $1$ |
| $2$ | $\dfrac{3}{5}$ | $3$ |
| $3$ | $\dfrac{1}{2}$ | $5$ |
| $4$ | ?? | ?? |
| $5$ | ?? | ?? |