Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since the distance is quite long you will need to fill up your tank several times. There are $n$ petrol stations along the way, and your goal is to stop at as few petrol stations as possible.
A natural greedy approach would be to make your first stop at the furthest petrol station, $s$, that is reachable from Eindhoven, then fill up your tank, drive again to the furthest reachable petrol station, and so on, until you can reach your destination. Prove or disprove that this is a good greedy choice. In other words, prove or disprove that there is an optimal solution for this problem that includes a stop at petrol station $s$.
Here is my solution. I prove the greedy strategy leads to an optimal solution. Let $OPT$ be the optimum solution, the set of all stations stopped at whose cardinality is minimal, and let $s$ be the first furthest station reachable from Eindhoven. I consider two cases. The first being that $s \in OPT$. In this case we are done. Now I consider the case where $s \notin OPT$. Then, some other station $s'$ was stopped at, sooner than $s$, since $s$ is the furthest station from Eindhoven. Now, stopping at an earlier station does not decrease the minimum number of stops required and so replacing $s'$ with $s$ leads to another solution $OPT^* = \{ OPT \setminus s' \} \cup \{ s \}$ which is no worse, i.e.:
$size(OPT^*) \leq size(OPT)$
Implying that the optimal solution $OPT$ can potentially be improved by using the greedy choice, contradicting the fact that $OPT$ is optimal and so $OPT$ must contain the greedy choice, i.e. $s \in OPT$. This concludes the proof. A proof could have also been obtained using the "greedy stays ahead" method, but I preferred to use the "cut and paste" reasoning.
Now, what could possible alternative approaches be to solving this problem? For example, a solution using the greedy stays ahead approach would be welcome. Also, if there are any errors with the reasoning it would be appreciated if these are pointed out :).
This problem comes from an algorithms course: https://www.win.tue.nl/~kbuchin/teaching/2IL15/
The problem set itself can be found at: https://www.win.tue.nl/~kbuchin/teaching/2IL15/Homework/hw-A1.pdf
The author of the problem set is Kevin Buchin.