There is this puzzle I was introduced many years ago:
Given are :
- a car starting with an empty tank
- n cities, ordered from 1 to n, lying on a circle (i.e. the only road between the cities is the circle)
- from the i-th city you can tank $x_i$ amount of fuel
- $\sum_{i=1}^n x_i$ is exactly the amount of fuel you need to drive once around the circle
- You are allowed to choose which city you start from and your car will magically appear there.
One is to show that there one is city you can start from with your car such that you will not run of fuel after a complete revolution.
Edit: One comment (Daniel Mathias) correctly points out that the amount of fuel needed from city $i$ to the next city is not given in the problem. So let us assume this is given as $y_i$.
I know how to prove this by contradiction, you practically allow your car to have negative fuel and show that a certain multiple of the sum $\sum_{i=1}^n (x_i-y_i)$ is not $0$, where $y_i$ is the fuel you need from the $i$-th city to the next city (next city is $i+1$ if $i<n$ and $1$ otherwise), and get the contradiction. But the proof I have is nonconstructive. So I still cannot find this city (I just know it exists) unless I search via brute force.
My question is (perhaps a naive one) whether there is an "efficient" algorithm to find this city and perhaps make a constructive proof of the statement? Maybe some sort of divide and conquer can make an efficient algorithm.
Imagine starting from city $C_1$ with enough fuel to drive around the circle. Then imagine driving around the circle, remembering the city $C_i$ where you arrived with the least amount of fuel.
Now you know that you can drive around the circle starting from city $C_i$ with no fuel, and you will always have a non-negative amount of fuel.
(Alternatively, perhaps more elegantly, you can imagine starting from city $C_1$ with no fuel, but your car is magic and it runs even with a negative amount of fuel.)