Return to Answer

The procedure I described can switch on all the lights, as long as you produce an even number of dominos. The parity argument that Gareth McCaughan gave can predict which starting positions produce an odd number of dominos. Count the number of adjacent pairs of wrong lights. Every move changes this by an even amount, so this number remains even or odd throughout. If it is odd, then the solving procedure must produce an odd number of dominoes. This means the position is unsolvable and we can only reduce it to exactly one remaining domino but no further. If this number of adjacent pairs of wrong lights is even, then we must get an even number of dominoes and be able to solve it.

The procedure I described can switch on all the lights, as long as you produce an even number of dominos. The parity argument that Gareth McCaughan gave can predict which starting positions produce an odd number of dominos. Count the number of adjacent pairs of wrong lights. Every move changes this by an even amount, so this number remains even or odd throughout. If it is odd, then the position is unsolvable because the fully solved grid is even. If you use the solving procedure, it must then produce an odd number of dominoes, and in that case we can only reduce it to exactly one remaining domino but no further. If this number of adjacent pairs of wrong lights is even, then we must get an even number of dominoes, and therefore be able to solve it.

Firstly, if any of the wrong lights can be switched, do so. This means all remaining wrong lights are odd (have an odd number of wrong neightbours).

Firstly, if any of the wrong lights can be switched, do so. This means all remaining wrong lights are odd (have an odd number of wrong neighbours).

The procedure I described can switch on all the lights, as long as you produce an even number of dominos. The parity argument that Gareth McCaughan gave can predict which starting positions produce an odd number of dominos. Count the number of adjacent pairs of wrong lights. Every move changes this by an even amount, so this number remains even or odd throughout. If it is odd, then the solving procedure must produce an odd number of dominoes. This means the position is unsolvable and we will can reduce it to exactly one remaining domino but no further. If this number of adjacent pairs of wrong lights is even, then we must get an even number of dominoes and be able to solve it.

The procedure I described can switch on all the lights, as long as you produce an even number of dominos. The parity argument that Gareth McCaughan gave can predict which starting positions produce an odd number of dominos. Count the number of adjacent pairs of wrong lights. Every move changes this by an even amount, so this number remains even or odd throughout. If it is odd, then the solving procedure must produce an odd number of dominoes. This means the position is unsolvable and we can only reduce it to exactly one remaining domino but no further. If this number of adjacent pairs of wrong lights is even, then we must get an even number of dominoes and be able to solve it.