We can find a strategy for this game using systems of linear equations. To keep our system of equations managable let's first find a solution for a 3x3 board.
|
How can linear equations be applied to this game? The answer
is surprisingly simple. To solve this puzzle we have to find out how many
times to click at each square to get the desirable effect: all squares
red. These are our unknowns .If we assign numbers for each square like
in the picture below ,we can denote xi the number of times
we have to click at the square i in order to get a solution. But what equations
can we write for these variables?
Let's write down the system of equations for a starting position on the board. We must get all squares red after we do all the clicking. So the first square that was white should become red, therefore this square should change its color the odd number of times. But exactly how many times will it change the color? Well, the first square changes color if and only if we click at squares 1,2,3,4 and 7. So the first equation is: x1+x2+x3+x4+x7=odd
The second square will change its color x1+x2+x3+x5+x8
number of times. It was red when we started and should stay red in the
end. So the second equation is:
|
If we solve this system of linear equations we will find the solution
to the above position on the board. We can find the general solution in
the same way. We denote b1,b2... b9
the right sides of our equations. If when we started a square i was white
then bi=1 , if it was red then bi=0 . We obtain the
following system of equations:
x1+x2+x3+x4+x7=b1
x1+x2+x3+x5+x8=b2
x1+x2+x3+x6+x9=b3
x1+x4+x5+x6+x7=b4
x2+x4+x5+x6+x8=b5
x3+x4+x5+x6+x9=b6
x1+x4+x7+x8+x9=b7
x2+x5+x7+x8+x9=b8
x3+x6+x7+x8+x9=b9
The augmented matrix for this system is:
1 1 1 1
0 0 1 0 0
b1
1 1 1 0 1 0 0 1 0 b2 1 1 1 0 0 1 0 0 1 b3 1 0 0 1 1 1 1 0 0 b4 0 1 0 1 1 1 0 1 0 b5 0 0 1 1 1 1 0 0 1 b6 1 0 0 1 0 0 1 1 1 b7 0 1 0 0 1 0 1 1 1 b8 0 0 1 0 0 1 1 1 1 b9 |
(1) |
But we can make few conclusions immediately without solving this complicated
system. We know that a system of equations Ax=b
has a solution for every right side b if
and only if a homogeneous system of equations Ax=0
only has the trivial solution. (Theorem 1.6.4 H.Anton, Elementary
Linear Algebra) .
The question about non-trivial solutions of the homogeneous system is equivalent to the following question about our game: is it possible starting from the board below to click at some squares(odd number of times) and get again all squares red. You can check that if you click at all squares in the first row and then at all squares in the second you will obtain the original position . Thus we found a non-trivial solutions for the homogeneous system . (You can check , if you want, that x1=x2=x3=x4=x5=x6=1 and x7=x8=x9=0 is a solution for the homogeneous system.). It means that for some right sides the system doesn't have any solutions and therefore it is sometimes impossible to solve the puzzle |
We use the fact that 1+1=even=0. We can continue the elimination procedure
,but it will take some time .If you want to look at the whole procedure
and the general solution use the following links:
Gauss -Jordan elimination for 3x3 board.
Gauss -Jordan elimination for 5x5 board.
We can also say a lot about our game if we work a little bit with our equations. Let's add the first 3 rows to obtain the following row:
1 1 1 1 1 1 1 1 1 b1+ b2+ b3
Now let's add equations 4,5 and 6, then 7,8 and 9. The result is:
1 1 1 1
1 1 1 1 1
b4+ b5+
b6
1 1 1 1
1 1 1 1 1
b7+ b8+
b9
It means that the numbers b1+ b2+ b3, b4+ b5+ b6 and b7+ b8+ b9 are all equal ( in our case this means that either they are all odd or they are all even).
We also can add equations 1,4,7 and 2,5,8 and 3,6,9. The result is :
1 1 1 1
1 1 1 1 1
b1+ b4+
b7
1 1 1 1
1 1 1 1 1
b1+ b4+
b7
1 1 1 1
1 1 1 1 1
b1+ b4+
b7
So we see that if we can find a solution for our system then
the number of white squares in each row and column is odd or in each row
and column is even. If this condition is satisfied
then we can check that xi=bi
is a solution . It means that if we click at white squares then
we will get one of the solutions. Check it!
Sometimes you can find shorter solutions. Think how you could do it (Hint: use nontrivial solutions for the homogeneous system).