# How to prove correctness of this algorithm

## Situation

There is a long patch of grass with seeds planted along it. Each seed needs to be within 2 metres of a sprinkler in order to be watered daily. Describe an algorithm that will result in every seed being watered using the minimum number of sprinklers.

## My Algorithm

Start walking along the patch of grass. Upon reaching the first seed - travel 2 metres and install a sprinkler. Continuing walking until you reach a seed that is not within 2 metres of the previously installed sprinkler - travel 2 metres and install a sprinkler. Repeat this step until all the seeds have a sprinkler within 2 metres of them.

I'm not 100% sure that this algorithm is correct but when I think about it and do examples it works. But the problem is, how am I supposed to formally prove the correctness of this algorithm? I've looked at examples of other algorithms having their correctness proven but I can't apply it to this situation. Any help is appreciated.

It seems to me that simple induction would suffice, going up in increments of $2$ metres.

Let your strategy be $S_{opt}$, and denote the number of sprinklers required to cover an unwatered patch of length $L$, with seeds distributed at locations $\Sigma$, using some strategy $S$ as $N\left( S, L, \Sigma\right)$.

Start with the trivial proof that $N\left( S_{opt}, L, \Sigma\right) \leq N\left( S, L, \Sigma\right)\;\forall S$ for $L \leq 4$.

Then move up to the case where $4 < L \leq 6$ and consider adding one sprinkler "somewhere". This will necessarily split the unwatered patch into one or two unwatered patches of lengths $\leq 4$. Consider all 8 possible cases:

1. both right and left patches remain; seeds in neither
2. both right and left patches remain; seeds in right only
3. both right and left patches remain; seeds in left only
4. both right and left patches remain; seeds in both
5. only right patch remains; no seeds
6. only right patch remains; has seeds
7. only left patch remains; no seeds
8. only left patch remains; has seeds

For the $i$th case, let $N_{i}\left( L, \Sigma\right)$ be the number of sprinklers needed for total coverage that case. Express $N_{i}\left( L, \Sigma\right)$ in terms of $1$ plus the optimum $N\left( S, L, \Sigma\right),\;L\leq 4$ solutions for the child patches.

Let ${N_{opt}}\left( {L,\Sigma } \right) = \mathop {\min }\limits_i {N_i}\left( {L,\Sigma } \right)$ be the minimum number of sprinklers needed over all cases, and show that your strategy $S_{opt}$ only gives rise to cases $\left\{ j \right\}$ where ${N_j}\left( {L,\Sigma } \right) = {N_{opt}}\left( {L,\Sigma } \right)\;\forall j$. Thus $N\left( S_{opt}, L, \Sigma\right) = {N_{opt}}\left( {L,\Sigma } \right)$, and hence $$N\left( S_{opt}, L, \Sigma\right) \leq N\left( S, L, \Sigma\right)\;\forall S, 4 < L \leq 6$$ which combines with the first interval to become $$N\left( S_{opt}, L, \Sigma\right) \leq N\left( S, L, \Sigma\right)\;\forall S, L \leq 6$$ Continue inductively in this fashion, going up by increments of $2$ metres, to complete the proof.

• Maybe I've misunderstood your work but the grass doesn't need maximum coverage. The only requirement is to have every seed within 2 metres of any sprinkler. – Ogen Aug 13 '14 at 7:52
• This is a proof for minimum number of sprinklers subject to the condition that all seeds must be covered (i.e. be within 2 meters of a sprinkler). However, Adriano's proof is briefer and written more in the style of greedy algorithm literature, hence use that one. ;) – COTO Aug 13 '14 at 13:40

Our greedy choice is:

Place a sprinkler $2$ metres to the right of the leftmost uncovered seed.

There are two steps in proving the correctness of a greedy algorithm.

Greedy Choice Property: We want to show that our greedy choice is part of some optimal solution. To this end, suppose that we have an optimal sprinkler distribution (call it $A$) where the leftmost uncovered seed (call it $s$) does NOT have a sprinkler that is exactly $2$ metres to its right. Now since $A$ is a solution, we know that there exists some sprinkler (call it $a$) that is within $2$ metres of $s$. Now suppose that we move $a$ to the right until it is exactly $2$ metres to the right of $s$ (call this new sprinkler distribution $A'$). To see that $A'$ is still a valid solution, observe that moving sprinkler $a$ to the right could not have resulted in some seed $t$ to become uncovered (otherwise, $t$ would be to the left of $s$, a contradiction). Thus, since the total number of sprinklers didn't change, we have obtained a solution $A'$ that uses our greedy choice and is just as optimal as $A$ (as desired!).

Optimal Substructure Property: We want to show that our greedy choice leads to a subproblem that can actually be recursively solved with more greedy choices. To this end, let $A$ be an optimal sprinkler distribution that always makes our greedy choice so that in the first step, it places some sprinkler $a \in A$ that is exactly $2$ metres to the right of $s$, where $s$ is the leftmost seed in $S$ (the set of all seeds). Then we claim that the sprinkler distribution given by $A \setminus \{a\}$ is an optimal sprinkler distribution that covers the remaining seeds in the set $S \setminus \{s\}$. To see this, we argue by contradiction.

Suppose instead that there exists some better sprinkler distribution $B$ for this subproblem so that $|B| < |A \setminus \{a\}|$. But then consider the sprinkler distribution $B \cup \{a\}$ for the original problem. Since: $$|B \cup \{a\}| \leq |B| + |\{a\}| = |B| + 1 < |A \setminus \{a\}| + 1 = (|A| - 1) + 1 = |A|$$ it follows that we have found a better solution to the original problem, contradicting the optimality of $A$ (as desired!).

• This is very complicated. I wish I could just explain something this simple with words. It's similar to explaining why 1=1 - it just does. – Ogen Aug 14 '14 at 10:23
• When it comes to algorithms, it can sometimes be easy to fool yourself into thinking that a simply greedy algorithm will work. Proving these two steps usually helps. For the Greedy Choice Property step, we usually try to argue that being greedy "couldn't hurt". For the Optimal Substructure Property, we usually try to do an exchange or cut-and-paste argument – Adriano Aug 14 '14 at 15:57

Here's a proof: seeds either had a sprinkler placed within two metres of them or were already within two metres of a sprinkler therefore all seeds are within two metres of a sprinkler.

Correction: we need to prove that we are using the minimum number of sprinklers. The seeds are sown along a line. The first seed determines the position of the first sprinkler. The first seed outside the first sprinkler's range determines the position of the second sprinkler, and so on. Therefore we first place the sprinklers from one end and then the other. Whichever of the two uses the fewer sprinklers represents the minimum.

• Yeah but how can you also prove that the number of sprinklers used was minimized? – Ogen Aug 13 '14 at 7:41
• Ah yes, will correct. – user117644 Aug 13 '14 at 7:45

I think the following is optimal:

The seeds can be partitioned into successive groups $\sigma_j$ $(1\leq j\leq m)$ as follows: The distance between any two successive seeds of the same group is $\leq 4$, and the distance between the last seed in $\sigma_j$ and the first seed in $\sigma_{j+1}$ is $>4$.

Let $\sigma:=(S_0,S_2,\ldots,S_r)$, $r\geq0$, be such a group, and let $x_0<x_1<\ldots<x_r=:L$ be the positions of the seeds in $\sigma$. Seed $S_0$ needs to be sprinkled. Putting a sprinkler at some point $s_1<2$ would moisture points $x<0$ for no avail. So the best we can do is put a first sprinkler at $s_1=2$. If $L>4$ we put another sprinkler at $s_2=L-2$.

Do the same with the "subgroup" $\sigma'$, consisting of the seeds in $\sigma$ which are not yet sprinkled, and repeat until the resulting "subgroup" $\sigma^{(k)}$ is empty.

Do this for all groups $\sigma_j$ $(1\leq j\leq m)$.