An Interlacing Transformation Problem
Yeong-Wen Hwang · American Mathematical Monthly · 1960
In each case we have a solution in n moves. We will prove that, for n 2 3, the chessmen can be realigned in n moves but not in fewer. The case in = 1 is trivial and the puzzle has no solution if n=2, so we assume n > 3. First we prove that the puzzle cannot be solved in fewer than n moves. To do this we count the number of variations, WB and B W, similarly to the counting of changes of sign in Descarte's rule of signs. The starting alignment (1) has 1 variation, and (2) has 2n -1. The first step in (3) for n = 3 has 2 variations. The first part of a move consists of removing two adjacent chessmen, X1X2X3X4 becoming X1-X4. It cannot increase, and may decrease the number of variations. In fact, if X1 and X4 are of the same color, then X1 X4 presents no variation. If Xi and X4 are of different colors, then X1X2X3X4 presents at least 1 variation, while X1 X4 presents exactly 1. The second part of a move consists of setting two chessmen back down, YY4 becoming Y1 Y2 Y3 Y4, where Y1 and Y2 may possibly be blank spaces. Now Y1 Y2 Y3 Y4 can present at most 3 variations and this can happen only if Y1, Y2, Y3, Y4alternate in color. In this case YY4 presents 1 variation, and the increase in number of variations is 2. In all other cases Yi Y2 Y3 Y4 presents at most 2 variations and the increase is at most 2. Thus we see that each complete move can increase the total number of variations by no more than 2. Consider the first move. It picks up two adjacent chessmen in (1) and sets them down at one end of the row. Clearly if a pair WW or BB is moved the number of variations is increased by at most 1, from 1 to 2. If the pair WB is moved, say to the right, we get