Question

Consider the following problem. The input consists of n skiers with heights h1, . . . , hn and n skis with lengths `1, . . . , `n. The problem is to assign each skier a ski so as to minimize the average difference between the height of a skier and his/her assigned ski. That is, if the ith skier is given the s(i)th ski, then you want to minimize 1 n Xn i=1 |hi − `s(i) | . (a) (6 points) Prove that the following algorithm fails to find an optimal solution on some input. Describe the input, the algorithm’s solution, and the optimal solution. Algorithm 1: Find the skier i and ski s(i) whose height difference is minimized (i.e. |hi −`s(i) | minimum). Assign this skier this ski. Repeat the process until every skier has a ski. (b) (9 points) Prove that the following algorithm is correct. Algorithm 2: Give the shortest skier the shortest ski, give the second shortest skier the second shortest ski, give the third shortest skier the third shortest ski, etc. [Hint: Consider the two-skier case first.]

Answer 1

The question assesses two algorithms for pairing skiers with skis to minimize the average height difference. Algorithm 1 fails with a specific example provided, and Algorithm 2, which involves sorting skiers and skis by height and length, respectively, is suggested to be correct.

Step-by-step explanation:

The question pertains to an optimization problem in mathematics where two different algorithms are considered for minimizing the average difference in lengths between skiers' heights and their assigned skis. This algorithm selects the pair of skier and ski with the smallest height difference and assigns them to each other, repeating the process until all pairs are assigned. However, this approach can fail to find the optimal solution. For example, consider two skiers with heights 100 cm and 110 cm and two skis with lengths of 105 cm and 90 cm. Algorithm 1 would first pair the 100 cm skier with the 105 cm ski and then the 110 cm skier with the 90 cm ski, giving an average difference of 7.5 cm. The optimal solution would pair the 100 cm skier with the 90 cm ski and the 110 cm skier with the 105 cm ski, yielding a lower average difference of 7.5 cm.

The second algorithm pairs skiers with skis based on their sorted order by height and length, respectively, ensuring that the shortest skier gets the shortest ski and so on. This method is known as the sort-and-assign algorithm and it can be proved to be correct using a mathematical proof, often starting with the simplest case of two skiers and two skis and expanding the logic to n pairs.