Here is the formal structure of an exchange argument: Claim: The greedy solution G is optimal. Proof: Let OPT be any optimal solution. I will show OPT can be transformed into G without losing optimality. Find the first position where OPT and G differ.
Let G choose item and OPT choose item at position .
Construct a new solution OPT' by swapping for in OPT.
Show that OPT' is valid and has quality >= OPT.
OPT' agrees with G on one more position. Repeat until OPT' = G. Since G can be reached from any OPT without losing quality, G is optimal.