n marbles are placed in a line. A marbles color is either red or blue. The colors can appear in any arbitrary manner (e.g., they can all be red or blue, or some may be red and the others blue). The goal is to remove all the marbles by a sequence of moves. In each move, a red marble can be removed; at the same time, we replace its neighbors (if any) by marbles of opposite color (i.e., Red becomes Blue and vice versa). A marble is a neighbor of another if it is adjacent to it in the original line (two marbles are not neighbors if there are gaps between them, which can occur when in-between marbles are removed). To illustrate, see the following example. Let RBBBRBRBB be the initial arrangement of marbles. Then the successive steps are shown as follows (a removed marble is shown as X): XRBBRBRBB XRBBRRXRB XRBBRRXXR XRBBRRXXX XRBBBXXXX XXRBBXXXX XXXRBXXXX XXXXRXXXX XXXXXXXXX. 1. It is clear that problem does not always have a solution (i.e., all marbles cannot be removed); for example, if all marbles are blue then nothing can be removed. Give a necessary and sufficient condition for the problem to have a solution. Prove that your condition is indeed necessary and also sufficient. Necessary means that without the condition, there is no solution; Sufficient means that with the condition there is a solution. (Hint: Consider small problem sizes to understand; red marbles are the key, in particular the number of red marbles.) 2. Assuming that there is a solution, give an algorithm to remove all the marbles. Prove that your algorithm indeed works. (Hint: It is important to remove the red marbles in a proper manner. Consider the example: the arrangement RRR clearly has a solution: XBR XRX XXX. However, if you remove the middle red first, then you will be stuck. Consider small problem sizes to understand what happens. For large sizes, use decrease/divide and conquer. Use induction in your proof.)