Color elimination puzzle

Question

You have a 5x5 board with on each cell a light that can be red, green or blue. Next to each row and each column there is a button that when pressed makes all red lights in that row/column green, all green lights blue and all blue lights red.

Is it always possible to eliminate one color from the board from every starting position containing all three different colors?

Example of a move:

Answer 1

I wanted to rephrase quidam's answer in a way which didn't require a technical math background. The answer is

No, it is not always possible.

As quidam said, an equivalent problem is asking if it is possible to eliminate green from the board, because once a color is eliminated, toggling all rows changes the missing color.

There are $3^{25}$ possible states the board can be in, 3 color choices for each of the 25 squares. Some of these states are reachable from each other by pressing buttons; let's call a set of states which can reach each other but no one else an equivalence class.

The first important observation is that any state can reach at most $3^{9}$ other states. Here's why:

• The order you press the buttons doesn't affect he result, so that a sequence of moves is determined by how many times each of the buttons were pressed.

• It's also useless to press a button 3 times or more, so there are really 3 options (zero,one or two) for how many times to press each of the 10 buttons.

Based on this alone, it would seem that there are $3^{10}$ ways to press the buttons.
However,

• One of the buttons is redundant. For example, anytime you want to press the lowest row button, you can instead press every column button once, then every other row button twice, for the same effect.

This means there are effectively 9 buttons, with 3 options for how to interact with each, for a total of $3^9$ possible actions, therefore at most $3^9$ reachable states (it's possible some actions would lead to the same state, thought this turns out to not be the case, so $3^9$ is exactly correct).

Since the size of each equivalence class is at most $3^{9}$, and there are $3^{25}$ total states, there must be at least $3^{25}/3^{9}=3^{16}$ equivalence classes. However, there are only $2^{25}$ states that don't have green. Since $3^{16}>2^{25}$, not every equivalence class can contain a greenless state, so every state in those classes will be unsolvable.

Answer 2

The answer is that

no, it is not always possible.

Here is the (fairly technical, sorry) reason:

Instead of colors, consider that the elements of the grids are elements of the cyclic group $\mathbb{Z}/3 \mathbb{Z}$; say, red=$0$, green=$1$ and blue=$2$. So a grid is just a $5\times 5$ matrix with elements in $\mathbb{Z}/3\mathbb{Z}$.

Now, a "move" on a row/column, say row/column $i$, is equivalent to adding the matrix with zeroes everywhere except on row/column $i$, where it has ones.

Consider the group $G$ of $5\times 5$ matrices with coefficients in $\mathbb{Z}/3\mathbb{Z}$, together with addition. Let $H$ be the subgroup generated by the matrices with zeroes everywhere, except in one row/column where it is filled with ones. The question then becomes:

"Does every coset in the quotient $G/H$ contain a matrix whose entries avoid one of the elements of $\mathbb{Z}/3\mathbb{Z}$?"

Note that if a coset contains a matrix avoiding one the entries of $\mathbb{Z}/3\mathbb{Z}$, then is also contain a matrix with entries only $0$ and $1$. Thus we can ask an equivalent but more refined question:
"Does every coset in the quotient $G/H$ contain a matrix whose entries are all $0$ or $1$?"

We prove that the answer is no with a cardinality argument. Note first that the cardinal of $G$ is $3^{25}$. Next, we claim that the cardinal of $H$ is $3^9$. The proof is at the end of the post.

Therefore, there are $3^{16}$ cosets in $G/H$. There are only $2^{25}$ matrices with entries $0$ or $1$; since $3^{16} > 2^{25}$, by the pigeonhole principle, there exists a coset not containing a matrix with entries $0$ or $1$. Thus it is not always possible to get rid of one color.

Proof that the cardinal of $H$ is $3^9$: There is a surjection

$$ (\mathbb{Z}/3\mathbb{Z})^{5} \times (\mathbb{Z}/3\mathbb{Z})^{5} \to H $$

sending an element $(a_1, \ldots, a_5, b_1, \ldots, b_5)$ to the matrix $a_1R_1 + \ldots a_5R_5 + b_1C_1 + \ldots b_5C_5$, where $R_i$ is the matrix with ones on row $i$ and zeroes elsewhere, and $C_i$ is the matrix with ones on column $i$ and zeroes elsewhere. It is not so hard to see that the kernel of this surjection is made of tuples such that $a_1=\ldots =a_5 = -b_1 = \ldots = -b_5$, and thus has cardinal $3$. Hence $H$ has cardinal $3^{10}/3 = 3^9$.

Answer 3

I know the mathematical proof is right, but how about

A counterexample:



Or this one with only $5$ Blues (instead of the $6$, above) and $1$ Green:



Or this one with only $2$ Blues and $2$ Greens:

One can quickly

enumerate all possible reachable states to check if any have none of any colour, like so:

from itertools import product

class Board:
    def __init__(self, state):
            self.state = [r[:] for r in state]
    def r(self, i):
            self.state[i] = [(v+1)%3 for v in self.state[i]]
    def c(self, i):
            for row in self.state:
                    row[i] = (row[i]+1)%3
    def __repr__(self):
            return '\n'.join(' '.join(str(v) for v in row) for row in self.state)

def clear(board):
    b = Board(board.state)
    for presses in product((0,1,2), repeat=9):
            b.state = [r[:] for r in board.state]
            for i, p in enumerate(presses[:5]):
                    for n in range(p):
                            b.r(i)
            for i, p in enumerate(presses[5:]):
                    for n in range(p):
                            b.c(i)
            if not all(any(v in r for r in b.state) for v in (0,1,2)):
                    return presses
 
>>> board = Board([[0,0,0,0,0],[0,0,0,0,0],[1,1,0,2,0],[0,1,1,1,0],[0,0,1,0,0]])
>>>clear(board) is None
True
>>>
>>> board = Board([[0,0,0,0,0],[0,1,2,0,0],[0,0,0,0,1],[0,0,0,0,0],[1,1,1,0,0]])
>>>clear(board) is None
True
>>>
>>> board = Board([[2,0,1,0,0],[0,2,0,0,0],[0,1,0,0,0],[0,0,0,0,0],[0,0,0,0,0]])
>>>clear(board) is None
True
>>>

I have checked

All boards with $1$ of one colour and $\lt5$ of a second colour and there are no solutions there

Also

After excluding a factor of $3!$ for the colour permutations there are $75,900$ boards with $21$ of one colour (say A) and $2$ of each of the others (say B and C).

Of these $3,600$ are such that one pair of B and C share a row, the other pair share a column and no B or C shares a row or column with another of the same colour (such as the example with $2$ Blues and $2$ Greens).

All of these can be transformed to a state containing only $2$ colours, and

any other configuration of $21,2,2$ cannot.

Answer 4

To add to the existence proofs of quidam and Mike Earnest, I'll show a specific start position that can't be made two colored.

The gray circles can be any color.

Because the order of the button presses doesn't matter, we can assume that rows are cycled before columns. To get two colors overall, the row cycles must result in two or fewer colors per column, since column cycles preserve the number of colors in that column.

When cycling rows, the 3x3 blue box in the top left must remain all the same color, since if two of its rows were different colors, one of the lights in the fourth row would be the remaining color, and so its column would have three colors. But, as long as that 3x3 box is the same color, the fourth column has three different colors.

A 4x4 board suffices for this construction, so this also proves the result for 4x4 boards. The equivalence class counting argument doesn't extend to 4x4 boards because $3^9<2^{16}$.

Answer 5

My solution

No we can't always eliminate 1 colour from the board

because

My solution

Start by assigning each colour a value
red = 0
green = 1
blue = 2

Each square initial state is refered to as $S_{ij}$ (i is the column, j is the row) and the switches are refered to as $C_{i}$ (columns) and $R_{j}$ (rows)

Each squares final state $F_{ij}$ = $S_{ij}$ + $C_{i}$ + $R_{j}$ modulus 3

So right away we can say there is no point pressing any column or row button more then 2 times

To solve we want it so all $F_{ij}$ cells do not equal a certain value. I will show that we can always select 1 of 2 colours

starting at the beginning we will arbitrarily assign 0 to all values in the first equation, math works the same regardless of the intial numbers picked

$F_{11}$ = $S_{11}$ + $C_{1}$ + $R_{1}$ (all equal to 0)

$F_{12}$ = $S_{12}$ + 0 + $R_{2}$ modulus 3
$F_{21}$ = $S_{21}$ + $C_{2}$ + 0 modulus 3

Since each of F12 and F21 can have 2 possible values each of $C_{2}$ and $R_{2}$ have 2 possible values. This means we can make $C_{2}$+$R_{2}$ modulus 3 equal any possible value (0,1,2)

This means we can make the formula

$F_{22}$ = $S_{22}$ + $C_{2}$ + $R_{2}$ modulus 3

equal anything we want it too ($C_{2}$+$R_{2}$ is any value).

When we get to the next stage

$F_{13}$ = $S_{13}$ + 0 + $R_{3}$
$F_{31}$ = $S_{31}$ + $C_{3}$ + 0
Limits each of $R_{3}$ and $C_{3}$ to 2 of 3 values $F_{23}$ = $S_{13}$ + $C_{2}$ + $R_{3}$
$F_{32}$ = $S_{31}$ + $C_{3}$ + $R_{2}$
Assumes $C_{2}$ and $R_{2}$ are fixed already and Limits each of $R_{3}$ and $C_{3}$ to 2 of 3 values. Combined with the limits imposed in $F_{13}$ and $F_{31}$ formulas this could restrict $R_{3}$ + $C_{3}$ to a single option so we can't control formula

$F_{33}$ = $S_{33}$ + $C_{3}$ + $R_{3}$

Which means we can't always eliminate a single colour.