label the light by its position (i;j) $1\leq\i\leq\ 5;1\leq\j\leq\ 5$ call (i;j) good if there is an algorithm make all lights but light(i;j) off notice that ;if (i;j) is good then the light symmetric to it through 2 diagonal is also good now we define an invariant consider set S (1;1);(1;2);(1;4);(1;5);(3;1);(3;2);(3;4);(3;5);(5;1);(5;2);(5;1);(5;3) the parity of M,the number of light on in S is invariant.A light not in S has even adjacent light in S(0 or 2);so toggle it will make M unchanged,or reduce 2 or increase 2,so parity is unchanged.A light in S has one adjacent light in S,so toggle it also make the parity of M unchanged Initially,M is 0,so a good position (i;j) cannot in S also (1;3);(2;1);(4;1);(2;5);(4;5) is not good since it is symmetric to a position in S so there are 5 possible good position and we can check that all of it works easy problem,right?

The parity in M is not invariant just operate on 2;5. However if u consider a square bound by 1;1, 1;5, 4;1, 4;5 the parity of on lights in that region is invariant and if we reflect this region we conclude that there is no light that can be on while all others are off.

My progress(yet to reach the whole solution ) Let me define "good" bulb; (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5) are good. Let me call the other "bad". Then, the number of bad bulb on will be always even. So, the group of good bulbs contains the solution. I'm not a contestant, but if I were a contestant, could I get partial credit?

peregrinefalcon88 wrote: The parity in M is not invariant just operate on 2;5. However if u consider a square bound by 1;1, 1;5, 4;1, 4;5 the parity of on lights in that region is invariant and if we reflect this region we conclude that there is no light that can be on while all others are off. Incorrect; operating on any of a lot of lights already tell that it's wrong. Try (3,3). The invariant is actually the set dhthstn said, only with a few typos there. The parity of the number of turned on lights in the set (1,1), (1,2), (1,4), (1,5), (3,1), (3,2), (3,4), (3,5), (5,1), (5,2), (5,4), (5,5) is an invariant. So the bulbs can only be in the complementary region. Reflecting through the main diagonal, we get that the set (1,1), (1,3), (1,5), (2,1), (2,3), (2,5), (4,1), (4,3), (4,5), (5,1), (5,3), (5,5) also have the same invariant. Thus the lights that are in the complement of both regions are the only candidates; these are (2,2), (2,4), (3,3), (4,2), (4,4). Now for the construction...

Another way of looking at the invariants above is to think of the lights' statuses as a collection of $25$ equations $\pmod 2$, where $a_{i,j} \equiv 1 \pmod 2$ if and only if the light at $(i,j)$ is on (otherwise it is $0$) and $a_{i,j} \equiv a_{i,j} + a_{i-1,j} + a_{i+1,j} + a_{i,j-1} + a_{i,j+1} \pmod 2$ (with some of the RHS terms missing if $(i,j)$ is an edge/corner square). Then if a collection $S$ of squares which, when all toggled (starting from no lights on), leave all lights off, then no square in $S$ can be a lone illuminated square since summing the corresponding equations $\pmod 2$ give a LHS of $0 \pmod 2$ and a RHS of $1 \pmod 2$ (a sum of $0$s along with a single $1$ corresponding to the one illuminated square). Such sets include, as partly mentioned above: $\{(1,1), (1,2), (1,4), (1,5), (3,1), (3,2), (3,4), (3,5), (5,1), (5,2), (5,4), (5,5)\}$, implying that the lone illuminated square cannot be a corner square $\{(1,2), (1,3), (1,4), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,2), (5,3), (5,4)\}$, implying that the lone illuminated square must be on a diagonal. The remaining five squares are achievable. For the center square, toggle $(1,1), (1,2), (2,3), (3,1), (3,3), (3,4), (4,1), (4,5), (5,2), (5,3), (5,5)$. To achieve only $(4,4)$ illuminated, toggle $(1,4), (2,3), (2,4), (2,5), (3,2), (4,1), (4,2), (4,4), (4,5), (5,2), (5,4)$ (rotate this set to get the other three of $(2,2), (2,4), (4,2)$).

dhthstn wrote: label the light by its position (i;j) $1\leq\i\leq\ 5;1\leq\j\leq\ 5$ call (i;j) good if there is an algorithm make all lights but light(i;j) off notice that ;if (i;j) is good then the light symmetric to it through 2 diagonal is also good now we define an invariant consider set S (1;1);(1;2);(1;4);(1;5);(3;1);(3;2);(3;4);(3;5);(5;1);(5;2);(5;1);(5;3) the parity of M,the number of light on in S is invariant.A light not in S has even adjacent light in S(0 or 2);so toggle it will make M unchanged,or reduce 2 or increase 2,so parity is unchanged.A light in S has one adjacent light in S,so toggle it also make the parity of M unchanged Initially,M is 0,so a good position (i;j) cannot in S also (1;3);(2;1);(4;1);(2;5);(4;5) is not good since it is symmetric to a position in S so there are 5 possible good position and we can check that all of it works easy problem,right? I think(if understands correctly) if (1,2),(3,2) is on, (5,2) is off, then operates on (2,2) make M alternates the parity.

Is there any other invariant? what about bigger fields?

I wonder how to determine a binary matrix(relation matrix) is invertible? Or restrict to some symmetric case like this problem. Can anyone recommend some theoretical or computational reference !

The construction took me more time than the solution itself My solution is very similar to dhthstn's, so I'll just post the construction. In the construction, black squares are the lights which we will toggle:

Solved with Pear222