Question :
A rectangular board with three rows and n columns is filled with 3n counters, of which n are red, n are white, and n are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish this task or prove that such an algorithm does not exist.
Solution :
If n = 1, the problem is already solved: all three counters in the only column are of the three different colors. If n > 1, we will show that the counters can be rearranged so that the three counters in the first column are of the three different colors; repeating such a rearrangement for the boards of decreasing sizes will solve the problem. Consider the counters in the first column. There are three possibilities: (i) all three of them are of the different colors, (ii) exactly two are of the same color, and (iii) all of them are of the same color.
In case (i), nothing obviously needs to be done with the counters in the first column.
Consider case (ii); we assume without loss of generality that the two counters of the same color are, say, red and they are in the first two rows, whereas the counter in the first column and the third row is, say, white (see the diagram below). Since there are n blue counters on the board and no more than n − 1 of them can be in the third row, at least one of them must be in the first two rows. Hence the algorithm in question can scan the first two rows starting with column 2 until a blue counter is encountered; after a blue counter is found, it should be swapped with the red counter in the first column.
Finally, consider case (iii). We assume, without loss of generality, that the three counters in the first column are red. Since each of the three rows must then contain at least one counter of the color other than red, we can scan, say, row 3 to find such a counter and swap it with the counter in the first column to get the situation of case (ii).
