2
$\begingroup$

Given a $4\times4$ binary matrix as following,

$\left( \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{matrix} \right)$

if you choose $a_{ij}$ in this matrix, then all the number in i th row and j th column will be changed( from 0 to 1 or from 1 to 0).

If all number in matrix turns to $0$, you win the game.

the steps may described like $a_{11}-a_{12}-a_{32}$.

Can any given $0-1$ matrix turn to a 0 matrix?

What is the strategy?

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Is this a one-person game? where you can make any move you like? and as many moves as you like? If it is, just change each 1 to a 0, one at a time. $\endgroup$ – Gerry Myerson Jul 27 '13 at 8:50
  • $\begingroup$ I don't understand half a thing of this "game": just choose $\,a_{11}\;,\;a_{32}\;,\;a_{43}\;$ and voila: the matrix is now all zeros! I'm sure some other rather important rules must exist that the OP didn't mention...or else this is a rather dull, uninspiring game.... $\endgroup$ – DonAntonio Jul 27 '13 at 9:03
  • $\begingroup$ The OP means, if you choose a position $(i,j)$, all entries in the same row or the same column of the 0-1 matrix will be switched to a different parity. This is yet another variant (which I have not seen before) of the Lights Out puzzle. $\endgroup$ – user1551 Jul 27 '13 at 9:17
  • $\begingroup$ @GerryMyerson sorry, i have explained in the post now. $\endgroup$ – Charles Bao Jul 27 '13 at 9:17
  • $\begingroup$ How do you know that, @user1551? Wizard! $\endgroup$ – DonAntonio Jul 27 '13 at 9:17
4
$\begingroup$

This can be done for all even-ordered games (including the OP's special case for order $n = 4$).

First, some analysis. Let $M$ be a given matrix and let

$$M_{xy} := \begin{bmatrix} m_{ij}^{(xy)} \end{bmatrix}, \quad m_{ij}^{(xy)} = \begin{cases} 1, & x = i,\ y = j, \\ 0, & \text{otherwise} \end{cases}$$

denote a matrix of all zeroes except on the position $(x,y)$, where it has $1$. Then

$$M = \sum_{(x,y) \in S} M_{xy}, \quad \text{for some $S \subseteq \mathbb{N} \times \mathbb{N}$}.$$

The game obviously has a solution if and only if each $M_{xy}$ can be solved (we just combine these solution, possibly eliminating duplicate moves). However, each $M_{xy}$ is a circular row- and column-shift of matrix $M_{11}$, so each of them has a solution if and only if $M_{11}$ has one.

We now turn to programming. Here is a PERL script I've made to find a solution (not necessarily an optimal one) for $M_{11}$, depending on order $n$ which is provided as a command-line argument for the script:

#!/usr/bin/perl 

use strict;
use warnings;

my $n = int($ARGV[0]);
my $M;
my $moves = [];

sub init {
  $M = [ map { [ map { 0 } (1..$n) ] } (1..$n) ];
  $M->[0]->[0] = 1;
}

sub printM {
  print map {
    ("    ", @{$M->[$_]}, "\n");
  } (0..$#$M);
}

sub check {
  return !grep { $_ } map { @$_ } @$M;
}

sub setField {
  my ($x, $y) = @_;
  for (my $i = 0; $i < $n; $i++) {
    $M->[$i]->[$y] ^= 1;
    $M->[$x]->[$i] ^= 1 unless $y == $i;
  }
}

sub nextField {
  my ($x, $y) = @_;
  $x++;
  if ($x >= $n) {
    $y++;
    return () if $y >= $n;
    $x = 0;
  }
  return ($x, $y);
}

sub tryField {
  my ($x, $y) = @_;
  if (check()) {
    print "Doable:\n";
    init();
    map {
      print "  Move: (@$_)\n";
      setField(@$_);
      printM();
    } @$moves;
    exit;
  }
  return unless ($x, $y) = nextField($x, $y);
  push @$moves, [$x,$y];
  setField($x, $y);
  tryField($x, $y);
  pop @$moves;
  setField($x, $y);
  tryField($x, $y);
}

init();
print "Starting matrix:\n"; printM();
tryField(-1,0);

This is a simple, unoptimized brute-force algorithm, with the complexity $O(2^{n^2})$. Hence, it is very slow, but suffices to test up to $n = 4$. It finds strategies for $n = 2$ (invoke by ./filename 2) and for $n = 4$ (invoke by ./filename 4), but not for $n = 3$.

For $n = 4$, we get:

Starting matrix:
    1000
    0000
    0000
    0000
Doable:
  Move: (0 0)
    0111
    1000
    1000
    1000
  Move: (1 0)
    1111
    0111
    0000
    0000
  Move: (2 0)
    0111
    1111
    1111
    1000
  Move: (3 0)
    1111
    0111
    0111
    0111
  Move: (0 1)
    0000
    0011
    0011
    0011
  Move: (0 2)
    1111
    0001
    0001
    0001
  Move: (0 3)
    0000
    0000
    0000
    0000

What we can see right now is that the strategy discovered above for the case $n = 4$ (click on all the elements in row $x$ and in column $y$, clicking on $(x,y)$ only once) can be mimicked for any even $n$, so each of these will have a solution. The strategy does not work for odd $n$, but this is no proof that odd-ordered games don't have a solution, as there might be a different strategy for them ($n = 1$ being the obvious example of an odd-ordered game that has a solution). However, some odd-ordered games certainly do not have a solution, as the above script finds for $n = 3$.

Further analysis would probably involve writing a far better algorithm, to test this further and possibly finding a pattern for which odd $n$ the game has a solution (if any), before proving it mathematically.

Edit: Just finished the script for $n = 5$ and it also has no solution, so I'm guessing that games of odd order greater than $1$ are unsolvable. Unfortunately, $n = 7$ would take $2^{7^2-5^2} = 2^{24} \approx 16\cdot10^{6}$ times longer (and this took few minutes), so we've hit the limit of the above script.

Odd orders beyond $1$ (observed by Alex Ravsky in comments)

Let the game be of order $n$ for some odd $n > 1$. We define $$S := \mathop{\sum_{i,j}}_{i+j \text{ is odd}} a_{ij}.$$ Then $S \% 2$ (the remainder when dividing $S$ by $2$) is invariant under the allowed changes.

To see this, observe how many elements change when we click on the position $(x,y)$. Let us define

$$f(p) := \begin{cases} \frac{n-1}{2}, & \text{$p$ is odd}, \\ \frac{n+1}{2}, & \text{$p$ is even}. \end{cases}$$

Then, when clicking on the position $(x,y)$, we change

  • $f(x)$ elements of the sum $S$ in the $x$-th row,
  • $f(y)$ elements of the sum $S$ in the $y$-th row,
  • we considered $(x,y)$ twice, which is relevant for $S$ if $x+y$ is odd (and has to be subtracted in that case).

The total change of $S$ is now:

  • If both $x$ and $y$ are odd (so, $x+y$ is even): $$ch(x,y) := f(x) + f(y) = \frac{n-1}{2} + \frac{n-1}{2} = n - 1,$$
  • If $x$ is odd and $y$ is even (so, $x+y$ is odd): $$ch(x,y) := f(x) + f(y) - 1 = \frac{n-1}{2} + \frac{n+1}{2} - 1 = n - 1,$$
  • If $x$ is even and $y$ is odd (so, $x+y$ is odd): $$ch(x,y) := f(x) + f(y) - 1 = \frac{n+1}{2} + \frac{n-1}{2} - 1 = n - 1,$$
  • If both $x$ and $y$ are even (so, $x+y$ is even): $$ch(x,y) := f(x) + f(y) = \frac{n+1}{2} + \frac{n+1}{2} = n + 1.$$

We see that in each case the number of changed elements of the sum $S$, denoted $ch(x,y)$, is even. Hence, $S \% 2$ will not change, regardless of the choice of $x$ and $y$.

Conclusion

The game of order $n$ is always solvable if and only if $n$ is even or $n = 1$.

$\endgroup$
  • $\begingroup$ +1 for noticing that the solution is a linear combination of solutions for individual $M_{ij}$s. However, would you please explain why an even-ordered game is always solvable? $\endgroup$ – user1551 Jul 27 '13 at 12:43
  • 1
    $\begingroup$ Apply the strategy above (click each element of the first row and the first column exactly once). Then $(1,1)$ will change state $2n-1$ times, which is odd. Elements $(x,1)$ and $(1,y)$ will change state $n$ times (for each click in the first column/row), which is even. All other elements, at positions $(x,y)$ for $x,y>1$, will change state exactly $2$ times (once for $(x,1)$ and once for $(1,y)$), which is again even. So, the only one changed in the end is $(1,1)$ as it is the only element with odd number of changes. $\endgroup$ – Vedran Šego Jul 27 '13 at 12:47
  • 2
    $\begingroup$ The $n$-ordered game is unsolvable for all odd $n\ge 3$ because in this case the sum $\sum \{a_{ij}: i+j$ is odd$\}(\mod 2)$ is invariant under the allowed operations. $\endgroup$ – Alex Ravsky Jul 28 '13 at 5:25
  • $\begingroup$ @AlexRavsky A great observation! I've added it to the answer. Thank you. $\endgroup$ – Vedran Šego Jul 28 '13 at 10:55
  • $\begingroup$ @VedranŠego Thanks. I never before saw so detailed decompression of my idea. :-) $\endgroup$ – Alex Ravsky Jul 28 '13 at 11:02
0
$\begingroup$

This is yet another variant of the Lights Out puzzle. For each button (i,j) we define a toggle matrix $T_{ij}$ where the entry is 1 if the button in that location changes state, or if it doesn't.

For example, $T_{11}=\left(\begin{matrix}1&1&1&1&\\1&0&0&0&\\1&0&0&0\\1&0&0&0\end{matrix}\right)$

The initial matrix $A=\left( \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{matrix} \right)$

The problem turns to a solving a linear equations in {0,1} system.

$A+\sum{x_{ij}T_{ij}}=0(\mod2)$, $x_{ij}\in\{0,1\}$

which is equivalent to

$\sum{x_{ij}T_{ij}}=A(\mod2)$, $x_{ij}\in\{0,1\}$

then it becomes a linear equations as followings:

$\left(\begin{matrix} 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{matrix}\right)(x_{11},x_{12},x_{13},\cdots,x_{33})^T=(a_{11},a_{12},a_{13},\cdots,a_{33})^T$

$\endgroup$
  • $\begingroup$ How did you go from $4 \times 4$ problem to the system of $9$ equations with $9$ variables? $\endgroup$ – Vedran Šego Jul 29 '13 at 14:55
  • $\begingroup$ it should be 16 equations with 16 variables. too large to type ^_^ $\endgroup$ – Charles Bao Jul 29 '13 at 15:03
  • $\begingroup$ Ah, I understand now. So, you are using vectorization, although you do it by rows, instead of columns. Notice that the above system is not easy to solve, at least not by the usual linear algebra tools, while my approach - using the same basic idea - is a constructive one, once you find a way to solve $M_{11}$. $\endgroup$ – Vedran Šego Jul 29 '13 at 15:28
  • $\begingroup$ solve this equations, can help us find all the solutions. however i still haven't work out. $\endgroup$ – Charles Bao Jul 30 '13 at 11:38
  • $\begingroup$ Why do you think that solving these equations is easier than my algorithm? $\endgroup$ – Vedran Šego Jul 30 '13 at 14:20

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.