There is a row of 2015 chips, of which 2014 are white and one is red. You are allowed to make moves of the following type: "Choose one red chip, and flip the colors of its two neighboring chips (from red to white, respectively from white to red)." Your goal is to turn all chips red by a sequence of such moves.
Question: For which positions of the red chip (in the initial situation) can you reach your goal?
Answer
As has been conjectured by others, this is solvable for only the chip in the middle. To show this, let us look at the problem in a new way; instead of considering which chips are red, let us consider which have been chosen an odd number of times.
___*___
___X___
__XX___
__XXX__
_XXXX__
_XXXXX_
_XX_XX_
where a move is legal on the starting square (marked by *) when it has either $0$ or $2$ neighbors which are $X$'s (meaning it remains red) and a move is legal on any other square when it has exactly $1$ neighbor which is an $X$ (meaning it was flipped from white to red). Obviously, we win when a move would be legal on every square, since that means that all squares are red. This is the case in the last line of the solution above.
We will show that all reachable positions have a common form. In particular, any position may be reached by alternatively adding and subtracting intervals from atop each other where each successive interval contains the initial position and is strictly contained in the previous interval. So, for instance, here is a few steps of addition and subtraction showing the form of such an interval:
__________*_______________
_XXXXXXXXXXXXXXXXXXXXXX__
_X___________________XX__
_X_XXXXXXXXXXXXXXXX__XX__
_X_XXX____________X__XX__
_X_XXX_XXXXXXX____X__XX__
_X_XXX_XX___XX____X__XX__
_X_XXX_XX_X_XX____X__XX__
where all the lines are legal positions. Notice that any such position is easily obtainable since one can flip the center when it is strictly contained in an interval (as it would have either $2$ or $0$ neighbors) and then one may expand out the new interval until it hits the boundary of the old interval, since until that point, the change from new interval to old interval would make moves legal at the edge where it went from all X's to all _'s.
Conversely, if we are in a state which is such a nest of intervals, any legal move leads us to a state which is still expressible as a nest of intervals. A convenient way to show this is to note that an equivalent characterization is that "the number of changes from _ to X is the same going out from the initial block to either edge" To show this, one may consider two cases. First, if the move must either be in the original chip's position, meaning that it was either contained wholly in some other interval (meaning both sides gain a change) or was the unique point in some interval (meaning both sides lose a change). Otherwise, the move must have occurred at a point . in the pattern X._ or _.X. Either way, the number of changes does not depend on whether . is X or _ so this move maintains the nested interval property.
This means that this is a complete characterization of the legal moves from a given center. The important thing to note is that there is are precisely two solutions in terms of where the $X$'s go for any starting solution. To prove this, notice that flipping any interior position flips two pieces and that no non-trivial such set of flips yields no change, as the rightmost/leftmost affected piece are affected precisely once. Thus, any change affected by interior pieces may be made in precisely one way. Then, a boundary piece may be flipped, and if so, so must the other one - giving one degree of freedom in whether to flip both boundaries. Moreover, by the argument presented by @DrunkWolf, odd positions are non-solvable. One may check that the following four patterns solve every possible board (as long as the length of the board is of the form $4n-1$ and the * is at an even position). In particular, if * is at a position of the form $4n$ then the following two patterns apply:
...___________*___________...
..._XX__XX__XX_XX__XX__XX_...
or
...___________*___________...
...XX__XX__XX___XX__XX__XX...
and if * is at a position of the form $4n+2$ then the following two patterns apply:
..._____________*_____________...
..._XX__XX__XX__X__XX__XX__XX_...
or
..._____________*_____________...
...XX__XX__XX__XXX__XX__XX__XX...
Merely verifying that the relevant two these are indeed solutions for any setup suffices to show that they are the unique two solutions. Note that all solutions are shown on a row where, without the ellipses, they are valid. All of these change state every two lengths, meaning that, unless they are within one chip of the center, the number of changes from X to _ will not be balanced on each side, meaning that the move will not be possible to reach. Conversely, if * is directly in the center, either solution is symmetric, meaning both sides obviously have the same number of changes and the solution is obtainable (and we can achieve it without flipping the outer pieces, since exactly one of the solutions above will do that and the other will not)
No comments:
Post a Comment