Greedy Strategy for assigning skis to skiers We have n skiers with increasing heights $p_1,...,p_n$ and n skis with increasing heights $s_1,...,s_n$.
We want to minimize the average difference between the height of a skier and his assigned ski.
That is, if skier $p_i$ is assigned $s_{a(i)}$ we want to minimize:
$$\frac1n \sum_{i=1}^n(|\,p_i-s_{a(i)}\,|)$$  
Consider the following Greedy Strategy:  
$\qquad$Give the shortest skier the shortest ski, give the second
shortest skier the second shortest ski, 
$\qquad$give the third shortest skier the third shortest ski, etc.  
The following is a proof by contradiction that the strategy is optimal:  
If the greedy algorithm is not optimal, then there is some input $p_1,...,p_n, s_1,...,s_n$ for which it does not produce an optimal solution.
Let the optimal solution be $T = \{ (p_1, s_{j(1)}),...,(p_n, s_{j(n)}) \}$
Let the output of the Greedy algorithm be $G = \{ (p_1, s_1),...,(p_n, s_n) \}$    
1) Beginning with $p_1$, compare $T$ and $G$.
2) Let $p_i$ be the first person who is assigned different skis in $G$ than in $T$.
3) Let $s_j$ be the pair of skis assigned to $p_i$ in $T$.
4) Create solution $T'$ by switching the ski assignments of $p_i$ and $p_j$.  
By definition of the Greedy Algorithm, $s_i \le s_j$.
The total cost of $T'$  is given by:  
$Cost(T')=Cost(T)-\frac1n (|p_i-s_j|+|p_j-s_i|-|p_i-s_i|-|p_j-s_j|)$ 
Since $p_i \le p_j$ and $s_i \le s_j$ there are 6 possible cases to consider:  
Case 1: $p_i \le p_j \le s_i \le s_j$
Case 2: $p_i \le s_i \le p_j \le s_j$
Case 3: $p_i \le s_i \le s_j \le p_j$
Case 4: $s_i \le s_j \le p_i \le p_j$
Case 5: $s_i \le p_i \le s_j \le p_j$
Case 6: $s_i \le p_i \le p_j \le s_j$  
In all cases, we can show that:   
$(|p_i-s_j|+|p_j-s_i|-|p_i-s_i|-|p_j-s_j|) \ge 0$   
which would be a contradiction that $T$ is optimal.
I don't understand step 4 of the proof where it says:
$\qquad$Create solution $T'$ by switching the ski assignments of $p_i$ and $p_j$.     
In $T$,$\,$$p_j$ is assigned $s_{j(j)}$.
The proof appears to be assuming that $s_{j(j)}=s_i$.
Shouldn't we be saying switch the assignments in $T$ of $p_i$ and whatever $p_k$ is assigned $s_i$? 
Could someone clarify? Thanks!

I think your correction that $p_i$ and $p_k$ should be switched is correct, since in general, $s_j(j) \neq s_i$. However, you should check if in all 6 cases
$$
  \left(|p_i - s_j| + |p_k - s_i| - |p_i - s_i| - |p_k - s_j|\right) \geq 0
$$
still holds.
