8
$\begingroup$

You have a 5x5 grid filled with 25 zeros. Your objective is to convert the grid into 25 ones. You must do this by a series of special moves.

On each move, you select a single cell. All four neighbouring cells (but not the cell itself) will be replaced by their respective binary opposites (1s will be replaced by 0, 0s by 1). If you select a cell on the edge, only three cells will be changed, and if you select a corner, only two will be?

Is the task possible?

P.S. If possible, find an algorithm/proof that generalises to an n x n grid

$\endgroup$
  • 1
    $\begingroup$ This puzzle is already well-solved, on another Stack Exchange: gaming.stackexchange.com/questions/11123/… $\endgroup$ – Nij Aug 15 '16 at 2:54
  • 3
    $\begingroup$ @Nij That is a different question; there, pressing a button toggles a light and its neighbors, here it only toggles the neighbors. $\endgroup$ – Mike Earnest Aug 15 '16 at 6:16
15
$\begingroup$

Here is another simpler proof

of impossibility. Consider the 5 cells that lie on the diagonal of the square. Every move changes an even number of those cells, either 0 or 2. Therefore, the number of zeroes in those cells never changes parity, and will always contain an odd number of zeroes like it does at the start. It is impossible to make them all ones.

This generalises to all odd n.

For even n, however,

it can always be solved. Here are solutions for even n, up to 10.

X.
X.

X..X
X..X
....
.XX.

X..XX.
X.....
..X..X
..X..X
X.....
X..XX.

X..XX..X
X......X
..X..X..
..X..X..
X......X
X..XX..X
........
.XX..XX.

X..XX..XX.
X.........
..X..XX..X
..X......X
X...X..X..
X...X..X..
..X......X
..X..XX..X
X.........
X..XX..XX.

Notice that the solution for n+4 can be made from the solution for n by surrounding it by a width 2 border. In this way you can create a solution for any even n.

$\endgroup$
5
$\begingroup$

The task is

impossible.

Number the grid 1 to 25, from left to right top to bottom. Also, color the grid like a checkerboard so cell 1 is black. Pressing a white cell only changes black cells, and vice versa.

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

There are an odd number of black cells which all must be changed. Pressing an interior white cell changes an even number of black cells, while a white cell on the border changes an odd number of black cells. This means that the total number of border white cell presses must be odd.

Note that cells 2 and 6 are the only ones which affect cell 1. This means cells 2 and 6 combined are pressed an odd number of times. Same goes for the other pairs of white cells bordering the other corners, (4,10), (16,22) and (20,24). Combining these four observations, the number of times a border white cell was pressed must be odd + odd + odd + odd = even, contradicting the first paragraph. Therefore, the puzzle is unsolvable.

This method does not generalize to an n x n grid. I've written a program (using Gaussian elimination over the finite field of order 2) to determine if an n x n grid is solvable, and it appears to be solvable exactly when n is even.

$\endgroup$
  • $\begingroup$ I'm way out of my competences but this looks wrong/incomplete to me. "This means that the total number of border white cell presses must be odd." + your 2nd observation let the opportunity on 3, 11, 15 and 23.If one of this 4 is checked an odd number of time, it should be ok. Am I missing something in your response? $\endgroup$ – Kikiwa Aug 15 '16 at 7:55
  • $\begingroup$ @Kikiwa: The cells 3,11,15,23 are not white in the checkerboard colouring that Mike is using. Basically, he is looking only at what presses are needed in the white cells (which are those that have an even index number) in order to toggle all the black cells (which are those which have an odd index number). $\endgroup$ – Jaap Scherphuis Aug 15 '16 at 8:00
  • 3
    $\begingroup$ I have an extensive analysis of Lights Out and its variants on my website. jaapsch.net/puzzles/lomath.htm#facts It includes the general solution for this puzzle for even n, and proves that odd n are impossible. $\endgroup$ – Jaap Scherphuis Aug 15 '16 at 8:02
  • $\begingroup$ Thanks for clarification (really understood it after a draw to see that the center was still wrong) and for the link! $\endgroup$ – Kikiwa Aug 15 '16 at 8:13
  • $\begingroup$ Jaap, I think you should consider posting a sketch of your general solution here as an answer. $\endgroup$ – Gareth McCaughan Aug 16 '16 at 13:23

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.