# Proving a greedy algorithm for pairing people.

Question: There are $n$ people, labeled $1, 2, . . . , n$ with weights $w_1,w_2,\dots, w_n$ and we are trying to pair as many people up such that there total weights don't exceed $C$.

A greedy algorithm that would result in an optimal solution would be to sort the people by increasing weight and if $n<2$ then return the empty set, otherwise pair the lightest person $l$ with the heaviest person $h$ such that $w_l+w_h\leq C$ and then recursively apply the algorithm to the remaining set of people. If $w_l+w_h\geq C$ then discard $h$ and run the algorithm on the rest of the set.

I am trying to prove that this greedy algorithm finds an optimal set.

Here's my attempt: My attempt for proving this is to apply proof by induction.

Base case: If $n=0$ or $n=1$. Then by our greedy algorithm it would return an empty set, which is the optimal solution.

Inductive step: Suppose $n\geq2$ and that $w_1\leq w_2 \leq \dots w_n$. There there are two cases to consider.

Case 1: When the lightest person and heaviest person have a combined weight exceeding $C$. i.e $$w_1+w_n > C$$

Proof. We know that for every $i$, $1 \leq i \leq n$, $w_i \geq w_1$ (because we ordered them by increasing weight). And so we have $$w_i+w_n \geq w_1+w_n \geq C$$ This tells us that the optimal set doesn't contain $w_n$. Thus, our algorithm would return the optimal set among the people $1, 2, . . . , n−1$

Case 2: When the lightest person and heaviest person have a combined weight less than or equal to $C$. i.e $$w_1+w_n \leq C$$

This is the part I don't know how to prove and was wondering is someone could lead me in the right direction for this part of the proof.

For case 2: You know that your algorithm give you the optimal set among the people $2,...,n−1$ plus the pair $(1,n)$
Consider an optimal set for $1,...,n$. We can assume, without loss of generality, that it contains $1$ (otherwise just replace any people by $1$ and you still have an optimal set). Moreover you can assume, without loss of generality, that it contains $n$ (otherwise just replace the people paired with $1$ by $n$ and you still have an optimal set).
Now two cases: Either the optimal set contains the pair $(1,n)$. In this case you know that your algorithm return the optimal set for $2,...,n-1$ and the pair $(1,n)$ thus return an optimal set.
Or the optimal set contains does not contain the pair $(1,n)$. Let $i,j$ be such that it contain $(1,i)$ and $(j,n)$. You can remark that the set where you remove those two pairs and ad the pair $(1,n)$ and $(i,j)$ is also an optimal set (since $w_i<w_n$ and $w_j<C-w_n$). Thus you are back to the first case.