Mathematical Induction for greedy algorithm problem?

Question

Suppose you want to place towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a tower. Devise a greedy algorithm that uses the minimum number of towers possible to provided cell service to Z buildings located at x1, x2, x3,... xd from the start of the road. Use mathematical induction to prove that the algorithm you created produces an optimal solution (uses the fewest towers possible to provide cellular service to all buildings).

Answer 1

Hint:

• To prove your algorithm: take some optimal solution, and then transform it (i.e. move towers) without losing anything (i.e. so that all the buildings have the service all the time) so that it becomes a solution generated by your algorithm.

I hope this helps $\ddot\smile$