2
$\begingroup$

There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly:

  • Flipping a row of coins;
  • Flipping a colomn of coins;
  • Flipping a diagonal line of coins;
  • Flipping a counter-diagonal line of coins.

enter image description here

The problem is to check whether we can finally let all coins facing up.

As we can see, there are $3n+3m-2$ kinds of transformations in total ($n$ rows, $m$ colomns, $n+m-1$ diagonals, and $n+m-1$ counter-diagonals). However, these transformations are not independent. For example, flipping all rows and then all colomns except the first colomn is equivalent to flipping the first colomn.

By trying some examples $n,m\ge 3$, I find that there are $3n+3m-9$ kinds of independent transformations in total. Other 7 transformations can be done by combining the $3n+3m-9$ kinds of independent transformations. Using Xor-Gaussian elimination we can check the correctness of the proposition.

If we can prove the above proposition, we can solve the problem in this way:

enter image description here

In the following image, there are $3n+3m-9$ shaded lattices. For any state of coins of these lattices (facing up or facing down), we can always use the above transformations to face up all coins of these shaded lattices (according to the order in the image to face them up). Also, for other unshaded lattices, their state will be uniquely determined. Then we can check whether we can finally let all coins facing up in $O(nm)$ time.

But it seems difficult to prove the independent proposition. Does anybody have some ideas on it? Thank you!

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Isn't this linear independence? $\endgroup$ – John L. Oct 23 '18 at 5:09
  • $\begingroup$ Yes, it should be "A couner-diagonal" but It is difficult to modify it. I have added a lot of detail to explain "independence" now. $\endgroup$ – zbh2047 Oct 23 '18 at 7:38
  • $\begingroup$ It looks like it is not hard to prove 3n+3m-9 if it is indeed correct. Are you actually interested in that exact number? $\endgroup$ – John L. Oct 23 '18 at 8:02
  • $\begingroup$ If this isn't proved, the $O(nm)$ algorithm will not be proven correct. The algorithm is really a simple and fast solution for this problem. $\endgroup$ – zbh2047 Oct 23 '18 at 8:07
  • $\begingroup$ Not necessarily. I could mark, for example, 6n lines and 6m columns, which may be enough to determine all the coefficients. So an exact number 3n+3m-9 might not be needed. Is it enough if an answer just prove that 6n+6m? $\endgroup$ – John L. Oct 23 '18 at 8:14
1
$\begingroup$

This is just linear algebra. Let $x$ be the vector over $\mathbb{Z}_2$ representing the initial state of the board, and let $y$ be the goal state of the board. Let $v_i$ be the vectors corresponding to the allowed flips (flipping corresponds to adding some $v_i$). Then we want to check whether $x+y$ is in the span of the $v_i$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yes, it is right. We can directly check whether $x+y$ is in the span of the $v_i$ by using Gaussion elimination, but it takes $O(nm(n+m)^2)$ time. The solution in the image is an $O(nm)$-time-complexity solution by constructing. $\endgroup$ – zbh2047 Oct 23 '18 at 7:47

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.