Saturday, September 26, 2015

[Japan 1998] 
Let n be a positive integer. At each of 2n points around a circle we place a disk with one white side and one black side. We may perform the following move: select a black disk, and flip over its two neighbors. Find all initial configurations from which some sequence of such moves leads to a position where all disks but one are white. 

If we can find a move that progressively converts one disk after the other to the desirable color, then we can go around the circle and stop at the one with the black. Why do we want a progression because we are only allowed to select one disk at a time and our goal is to ensure the same snd state configuration all around the circle. Moreover, if we are able to achieve a progression, then we don't have to concern the direction we traverse around the circle or the number of times we go around the circle, reassuring ourselves that each disk can be visited and tested.

Also note that while the question asks for all initial configuration, we can generalize it to saying if we can tackle one with an arbitrary number of disks that we can select to perform flips, then the strategy of using a progression will work for any number of such disks, in this case, black disks, around the circle.

Finally the termination condition is given by the fact that we stop short when there is only one black disk around the circle. If we had started out with all white, then there are no moves possible and would not contribute to the end goal, hence our assumption that there are arbitrary number of black disks around the circle to begin with holds true.

With the initial condition established, the progression required and the same final goal, we have the premise for an algorithm that can steadily decrease the number of blacks around the circle proving that such an algorithm will work.

All that the algorithm needs to focus on now is to make sure that each disk traversed in one direction  around the circle is flipped to white if it is not already white and stopping when there is only one black.

No comments:

Post a Comment