In the previous post about the following question:
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.
we proved the premise for an algorithm.
Now let us see the steps involved.
When we select a disk O that is black, we want to convert it to white and proceed to the next one in a given direction say counterclockwise on the circle.
Let us say the neighbors of this selected disk O are X and Y. When we flip X and Y, both could have become black but we can ignore X since we move in the direction of Y leaving X to be the one to satisfy termination condition. O is unchanged and black.
Now Y is black, we proceed flipping, this will make O white while Y's neighbor in the chosen direction say Z could may also become black. Thus O has become white but Y and Z are black. In order to flip Y we select Z and flip Y and the disk following Z thus making Y white. This is acceptable since Y and Z are both black. but what if Z is white. In this case both O and Z as Y's neighbors are white and flipping Y would result in undoing what we did with O to begin with. But let us say this undoing O is ok given that Y has now become the new O. In other words we pushed O forward by one position while leaving blacks in our wake. So let us make O black again and Z black.
Now we have X O Y Z black
Now we know that O was not only black disk in the circle otherwise we would not have commenced flipping. Besides we let X be the termination condition should it have become black with our flipping.
Since we will have to skip Y if we don't want to undo O, we might as well have skipped O.
Therefore the only condition in which we can move forward is the configuration in which O and Z are both black.
Moreover since we want the propagation to finish at or before O, the neighbour before X must also be black. In other words, the configuration where such moves can propagate and leave behind one black is one where black and white alternate.
we proved the premise for an algorithm.
Now let us see the steps involved.
When we select a disk O that is black, we want to convert it to white and proceed to the next one in a given direction say counterclockwise on the circle.
Let us say the neighbors of this selected disk O are X and Y. When we flip X and Y, both could have become black but we can ignore X since we move in the direction of Y leaving X to be the one to satisfy termination condition. O is unchanged and black.
Now Y is black, we proceed flipping, this will make O white while Y's neighbor in the chosen direction say Z could may also become black. Thus O has become white but Y and Z are black. In order to flip Y we select Z and flip Y and the disk following Z thus making Y white. This is acceptable since Y and Z are both black. but what if Z is white. In this case both O and Z as Y's neighbors are white and flipping Y would result in undoing what we did with O to begin with. But let us say this undoing O is ok given that Y has now become the new O. In other words we pushed O forward by one position while leaving blacks in our wake. So let us make O black again and Z black.
Now we have X O Y Z black
Now we know that O was not only black disk in the circle otherwise we would not have commenced flipping. Besides we let X be the termination condition should it have become black with our flipping.
Since we will have to skip Y if we don't want to undo O, we might as well have skipped O.
Therefore the only condition in which we can move forward is the configuration in which O and Z are both black.
Moreover since we want the propagation to finish at or before O, the neighbour before X must also be black. In other words, the configuration where such moves can propagate and leave behind one black is one where black and white alternate.
No comments:
Post a Comment