Problem $1.$ We are given $2n$ equally$-$spaced points on a line. Half the points are black, and

half are white. The goal is to connect every black point to a distinct white point with a wire

so as to minimize the total wire length.

Below are two suggestions for greedy algorithms, which may or may not solve the problem

correctly. For each suggested algorithm, if it is correct, prove its correctness. If it is incorrect,

prove that by providing an input on which the algorithm does not find an optimal solution.

Each of the suggested algorithms performs $n$ iterations. In every iteration, it selects a

single pair of points to connect and then deletes these two points from the line. In order to

define each algorithm, it is now enough to specify the greedy rule for selecting the pair of

points to connect.

Greedy Rule $1$: find any pair $(a,b)$ of points, where $a$ is black and $b$ is white, and no

other point lies between the two. Connect $a$ to $b$ and delete both points from the line.

Greedy Rule $2$: Let $a$ be the leftmost black point and let $b$ be the leftmost white point.

Connect $a$ to $b$ and delete both points from the line.