3

We have a matrix with numbers. We can add $1$ to any selected element and this action adds $1$ to elements according to some function, which I'll call the $X$-function. For instance, $1$ could be added to all elements in the same row and all elements in the same column as the selected element, or to all elements adjacent to the selected element. If any element gets bigger than a parameter $A$, it is set to $0$ (if $A=1$, elements can be $0$ or $1$; if $A=2$, they can be $0$, $1$ or $2$, etc.). Or we can decrease any element by $1$ and other elements are also decreased, according to the same $X$-function. If an element is decreased below $0$, it it set to the parameter $A$.

So, how to check for the possibility to set all matrix elements to one state (e.g., all to $1$)? How to find all $X$-functions for which this is possible?

For example: I have a square matrix of valves. When I change the state of any valve (open it or close it), this toggles the state of all valves in the same row or column (if they were open they become closed and vice versa). Goal: to open all valves. I can always win this game if the matrix has an even number of rows and columns. But if the number of rows and columns is odd, I can solve this puzzle only sometimes. So, if we change valves adjacent to the selected element instead of those in the same row or column, can we solve this puzzle in that case? How to calculate this?

joriki
  • 238,052
Robotex
  • 189
  • 3
    Maybe it's just me, but I find your description very unclear. Maybe you could add some example so we can see what you're asking exactly. – Dolma Apr 22 '13 at 23:22
  • I improved question – Robotex May 15 '13 at 21:09
  • I made a major edit to try to resolve some of the language issues. Please check whether the question now means what you intended it to mean. – joriki May 15 '13 at 21:56
  • I guess this is describing a typical mini game in RPGs. Reachability to the solution state from the initial state must be tested. I am inclined to use computer for enumerating such problems...unless you have a more specific X-function in mind. – Memming May 15 '13 at 22:00
  • @Memming: If $A+1$ is a prime power, this is a problem of linear independence that doesn't require enumeration, just standard linear dependence tests. – joriki May 15 '13 at 22:03
  • @joriki Word. Then one can show that every state is reachable. – Memming May 15 '13 at 22:27

0 Answers0