How can I prove that my greedy algorithm for least guards is optimal? This is the problem:


  An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of 10 meters (5m on the right, 5m on the left with him being in the middle).


No matter where the artworks are put in the hallway we want the minimal amount of guards as possible.

My Greedy Algorithm:

Start at the beginning of the hallway.
Find the position of the closest artwork from the entrance.
Put the guard at position closest artwork + 5m ahead.
Eliminate all the artworks covered by the guard.
Re-do the process but this time start where the range of the previous guard ended


Now how do I write a proof for this? How do I prove that my algorithm is indeed optimal? Which mathematical proof techniques can I use?
You can achieve this per induction over the position of the last artwork. Note that in the optimal strategy the guard must be put 5 meter ahead of the left most artwork and not exactly at it.

In the induction step you have to consider an additional artwork and distinct two cases, whether it is covered by the last fixed guard or not. If it is, you do not have to add one and hence, the optimal can not be better. In case it is not, it is easy to show, that an optimal that woul have covered it should have used strictly more guards.