How to get the least number of flips to a plastic chips to get a certain figure?

Question

The puzzle is as follows:

(Transcription with grammar errors fixed)

A game consists of the following:

The challenge is to flip the chips in such a way so that they are as in state 2. You start in state 1. A movement is valid when you flip a chip, and the two that are next to it, at the same time.
What is the minimum number of movements to do so?

(A and B are the two states)

A B A     B A B
B   B --> A   A
A B A     B A B

The alternatives given are:

1. 8 movements
2. 9 movements
3. 5 movements
4. 6 movements

This puzzle doesn't have an official answer. But I'm getting 8. I don't know if my answer is right or reasonable.

Does a method exist to solve these kinds of puzzles? The thing here is that the figure makes a closed loop and because the only allowed movement is to flip three chips that means one plus the other two which are next to it.

Thus what I did was begin at the top left, to try to make the figure be entirely the cherry shade instead of the orange one.

Once I made this, then my next move was to cancel the necessary cherry chips by flipping them.

In the end this yielded me 8 movements. But is this the least?

Can someone help me with a drawing or sketch to better understand this?. Because the intended method for solution which it would help me best is the kind which doesn't rely too heavily on advanced mathematics, but something which could be done without too many manipulation of variables. Does it exist a way or a suggested approach on these lines?.

For reference, I got this from my Logical games book sheet from 2000's. It seems to be an adaptation from a reprinted copy of Martin Gardner's Puzzle carnival book of the 1970s.

Answer 1

Suppose there are $n\geq 3$ chips. It's easy to see that $n$ moves is possible, making each move exactly once (this flips each chip three times). Since making the same move twice cancels out, any optimal solution also involves making each move at most once.

Since each chip needs to be flipped an odd number of times, in any optimal solution each chip is flipped either once or three times. But the only way a chip can be flipped three times in an optimal solution is if all three moves involving that chip are used once each. If this happens, both the adjacent chips are flipped at least twice, so they must also be flipped three times.

It follows that in any optimal solution, either every chip is flipped three times or every chip is flipped exactly once. The former case takes $n$ moves, since each move flips three chips and there are $3n$ total flips. The latter case takes exactly $n/3$ moves for the same reason; this is only possible if $n$ is a multiple of $3$. (It is possible in this case, by dividing the chips into consecutive groups of three, and flipping each group.)

So the answer is $n$ if $n$ is not a multiple of $3$, and $n/3$ if it is.

Answer 2

You can solve the problem via a system of eight linear equations, one per chip, with eight binary variables, one per possible movement. The order of operations doesn’t matter, and there is no reason to perform the same movement twice because the two steps would just cancel. So the number of movements required is at most 8. Because each movement changes the parity of the number of red chips, there must be an even number of movements, ruling out 9 (again) and 5. It turns out that

8 is the minimum, achieved by making each possible movement once.

Answer 3

First, we can prove that every puzzle in this setup (with any starting state, and any ending state) has a solution.

To see this, suppose that we do five flips centered at the chips marked with an x or X in one of the diagrams below:

x . x    x x .    . x x    X . x    . X .    x . X    x x .    . x x
x   x    .   x    X . .    .   x    x   x    x . .    .   X    x   .
. X .    X . x    . x x    x x .    x . x    . x x    x x .    x . X

This has the effect of toggling the chip marked with capital X, and leaving all other chips as they were. Applying several of these sequences lets us make any change we like (possibly inefficiently).

---

A solution by the strategy above can take up to 40 moves. But we can simplify any solution: the steps can be reordered without changing the result, and if we make the same flip twice, we can skip it instead. After skipping repeated flips, and sorting in some canonical order, there are only 2⁸ = 256 possible simplified sequences of moves: for each possible flip, either we did it once or we didn't do it at all.

We know that from every starting state, we can reach all 256 ending states by some sequence of moves. But there's only 256 simplified sequences of moves. Therefore, there's only one simplified sequence of moves per ending state - every simplified sequence of moves has a different effect.

In particular, there's only one simplified sequence of moves that solves the puzzle in that question. It has 8 moves. The only other solutions must be unsimplified, which means they have even more moves: simplifying makes a solution shorter, because we cancel out repeated moves.

Answer 4

RobPratt gave the correct mathematical approach. To elaborate further, let's call the eight chips $A, B, \cdots, H$:

$$ \begin{array}{ccc} A & B & C \\ H & & D \\ G & F & E \end{array} $$

If we assign 0 to yellow and 1 to pink, flipping a chip is equivalent to adding 1 modulo 2, because $0 + 1 = 1 (\operatorname{mod} 2)$ and $1 + 1 = 0 (\operatorname{mod} 2)$.

Now, let $a, b, \cdots, h$ denote the number of flip operations, such that $a$ is the number of flips on $A$ and its neighbors $H,A,B$, $b$ is for $A, B, C$, and so on. Then $A$ gets flipped $h+a+b$ times, $B$ is flipped $a+b+c$ times, and so on. Based on the initial and final states of $A,B,\cdots,H$, we can set up a system of linear equations modulo 2:

$$ 0+h+a+b=1 (\operatorname{mod} 2) \\ 1+a+b+c=0 (\operatorname{mod} 2) \\ 0+b+c+d=1 (\operatorname{mod} 2) \\ 1+c+d+e=0 (\operatorname{mod} 2) \\ 0+d+e+f=1 (\operatorname{mod} 2) \\ 1+e+f+g=0 (\operatorname{mod} 2) \\ 0+f+g+h=1 (\operatorname{mod} 2) \\ 1+g+h+a=0 (\operatorname{mod} 2) \\ $$

You can solve this just like a plain system of equations, keeping in mind that, in modulo 2 system,

$$0 + 0 = 1 + 1 = 0 - 0 = 1 - 1 = 0 \\ 0 + 1 = 1 + 0 = 0 - 1 = 1 - 0 = 1$$

So, for example, subtracting between the first two equations gives $h + c = 0(\operatorname{mod} 2)$.

If you solve it without mistakes, you should get $a=b=\cdots=h=1$ for this specific problem.

This is the general approach to standard "chip flipping" / "turn the lights on and off"-type of problems. One kind of complication is when the system is NOT uniquely solvable (many solutions or no solutions). Dealing with it is a mathematically deep subject, and Jaap's web page on this topic has a discussion on this problem. Also check out other questions tagged lights-out on Puzzling.