Its Laundry Day!!! You have just cleaned and dried all of your black socks. Oh no!!! you had dropped a little bit of bleach in the washing machine so your socks are no longer all black! Now your socks are all different shades of grey. You wish to pair the socks in such a way so that their shades of grey are not too different. What is the maximum number of pairs you can make.

You have n socks numbered 1 through n and each sock i is given a value $c_i$ ranging from 0 to 100 with 0 meaning black and 100 meaning white. Any number in between is a shade of grey.

In order for two socks to be a "passable" pair, the difference of their shades c and c' is less than or equal to a given threshold value T, i.e., |c c'| T. Otherwise, the two socks is not a passable pair. The goal is to maximize the number of passable pairs of socks.

Question 1:

Candidate Greedy Strategy: Sort the socks in increasing order by shade: c1 c2 cn. If |c1 c2| T then pair (c1, c2) and recurse on the remaining socks (c3, . . . , cn). If |c1 c2| > T then throw away c1 and recurse on the remaining socks (c2, . . . , cn).

Either prove that this strategy always yields an optimal solution or give a counterexample to show that it is not always optimal.