$($c$)(7$ points$)$

Candidate Greedy Strategy II: Put the first site at $x_1.$ Eliminate all franchise sites that are within $5km$ of $x_1$ and recurse on the rest until there are no franchise sites left.

Fill in the blanks of the proof of the following lemma:

Suppose that OS is a valid assignment that does not select $x_1$ as a franchise. Show that there exists an assignment $O{S}^{\text{'}}$ that does select $x_1$ as a franchise and $|OS||O{S}^{\text{'}}|.$

proof: Let $OS$ be as above.

i$.(2$ points$)$ Define $O{S}^{\text{'}}($by explaining how to construct $O{S}^{\text{'}}$ from $OS.)$

ii$.(3$ points$)O{S}^{\text{'}}$ is a valid solution because... $($Justify why in $O{S}^{\text{'}},$ all franchises are $5km$ or more apart.$)$

iii. $(2$ points$)|OS||O{S}^{\text{'}}|$ because... $($justify$)$