13
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ If the piece is at either end of the row, can we assume we are still allowed to flip it? $\endgroup$ – ghosts_in_the_code Dec 22 '15 at 11:53
7
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ One note that I haven't got a good explanation for, but which is somewhat curious is that the patterns for $4n+2$ are simply the patterns for $4n$, but with X's and _'s exchanged. I haven't got a good explanation for why that is (though, I do see that if we had an infinite grid, exchanging X and _ would transform solutions to solutions, as it doesn't change the parity of the number of neighboring X's that any point has) $\endgroup$ – Milo Brandt Dec 23 '15 at 1:57
9
$\begingroup$

Only one spot works, exactly in the middle

If you have a chip somewhere in the middle, and you flip its neighbors, then flip one of the new red chips, you get a pattern of RWRR. The RR can be continuously moved down, by flipping the outside R.

Let's say you start on 3. 3-2-4 will give you spots 1-5 filled. 5-3-1 will fill you out to 6, but then you can't add any more reds.

Based on that, it looks like you can only effectively double your starting red's position, where the position is from the closest end. Therefore, your starting chip has to be exactly in the middle.

Another way of thinking about it is that you move your red chip out 1, and fill in 2 spots behind it. Eventually you'll have an odd number of chips = 2*N - 1. You can shift the chips and get 1 more from the innermost chip.

$\endgroup$
7
$\begingroup$

Edited with proof that the middle one is the only one

We can show quite simply that we're unable to solve if the red chip is on

an odd number

To show this

imagine that the row is laid out on a very long checkerboard, with the first square being black. Because we have $2015$ chips, we have $\lceil{\frac{2015}{2}}\rceil = 1008$ black squares; an even amount. We also know that with each flip centered on a white square we always flip 2 black squares. Every flip we either add 2 reds on these squares (if both were white), keep the amount the same (if one was white and one was red) or lose 2 reds (if both were red). It then follows that if we start out with an uneven amount on chips on black, we can never turn this into an even amount. As such it's unsolvable if the red chip starts on a black square.

Then let's continue to show that

The only option is the middle one, 1008

We can prove this

By noting that every change we make on the board is reversible (we can always move back to our starting position by doing the moves we did again in reverse), which means that if we can solve it from one starting state, we should be able to reach that one state from every other solvable starting state.

It is then sufficient to prove that

No other state with a single red chip can be reached from the starting state where we have 1 red chip in the middle. Since we've already proven that an 'odd' state is unsolvable, the only viable steps would be in increments of 2. To make a step of 2, we would have to flip around a neighboring (odd) chip and then remove the chip we just flipped around. However this is impossible, since we can't just flip around any point.

$\endgroup$
  • $\begingroup$ Doesn't this proof break if you have a red chip on the edge? Then you flip 1 chip. $\endgroup$ – JonTheMon Dec 22 '15 at 15:07
  • $\begingroup$ @JonTheMon it doesnt, edge flips will only ever flip chips on white squares $\endgroup$ – DrunkWolf Dec 22 '15 at 15:08
  • $\begingroup$ Oh, I get your point now. Odds are black (mentally, I was thinking start with white), and for 2015 we have an even number of them. Instead of "first chip being on a black square" maybe say, "first square is black"? $\endgroup$ – JonTheMon Dec 22 '15 at 15:20
  • 1
    $\begingroup$ @MiloBrandt Is it that easy though? taking a 7 long one as a test case, starting on 2, taking 1 as red and 0 as white: 010 0 000 -> 111 0 000 -> 101 1 000 -> 100 1 100 -> 100 0 110 -> 100 0 011. Note that all these moves are pretty much mandatory (unless i'm missing something, doing any other move would revert me to an earlier state) From here we can do 100 0 011 -> 110 0 011 -> 011 0 011 -> 001 1 011 -> 000 1 111, but at this point i don't see how you would solve from there.. $\endgroup$ – DrunkWolf Dec 22 '15 at 19:18
  • 1
    $\begingroup$ @DrunkWolf Agh! I understood the question very very poorly - thank you for correcting me. I found an actual proof that your conjecture is correct, that only the center is solvable. $\endgroup$ – Milo Brandt Dec 22 '15 at 21:06
1
$\begingroup$

I think:

All starting positions are valid

Asume we have all our chips are red, and we want to turn them white but one.

We can start from one edge choosing every 2 mod 3 chip for some chips (even 0). Then at one point, we stop choosing 2 mod 3 and we start with all 0 mod 3 after that moment, leaving one red, until the end (the last one will flip only 2 chips, because it's in the edge). That means that the starting position of one chip on one 1 mod 3 position is valid. But 1 mod 3 is 0 mod 3 by simmetry.

For all 2 mod 3, we can start fliping all 1 mod 3 chips for some chips (even 0). Then at one point we stop choosing 1 mod 3 and start choosing all 0 mod 3 until the end, leaving one red at one 2 mod 3. (2 mod 3 it 2 mod 3 by simmetry ;) )

$\endgroup$
  • 2
    $\begingroup$ This is not correct, see my answer for proof that you're not allowed to start with red on any odd position $\endgroup$ – DrunkWolf Dec 22 '15 at 17:17
1
$\begingroup$

I tried a different approach.

First, let us show that there is a solution starting with a red chip in the center. This is made by induction on the row lenghts of the form $n=2k+1$. In the case $n=3$, this is done with a single flip. In the general case $n=2k+1$, we start with the configuration $W(k)RW(k)$, where $B(k)$ is a sequence of $k$ white chips. If we keep choosing the leftmost red chip, after $n$ moves we arrive at the configuration $RRB(k-1)RB(k-1)$; the right subrow is soluble by inductive hypothesis without touching the two leftmost red chips, so we are done.

To show that there is just one solution, we know after @DrunkWolf that going from a configuration to another is reversible, and that choosing twice a specific chip, even if at non consecutive moves, has a null effect. This means that is the problem may be solved starting with a single chip in a non-central position, it is also possible to find a path which starts at that configuration and arrives at the one with only the central chip red. Without loss of generality we may suppose that the initial red chip is at the left of the center. Let us take the shortest such path and consider the leftmost chip flipped red. This chip must become white again, but it cannot be flipped choosing its left neighbour - it never was red - so it will be flipped choosing its right neighbour. But then the two moves of that neighbour may be removed from the path, which is absurde since we chose the shortest path.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.