patternMinor
Coin flipping problem on an $n \times m$ grid
Viewed 0 times
coinproblemgridflippingtimes
Problem
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:
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:
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!
- Flipping a row of coins;
- Flipping a colomn of coins;
- Flipping a diagonal line of coins;
- Flipping a counter-diagonal line of coins.
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:
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!
Solution
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$.
Context
StackExchange Computer Science Q#98946, answer score: 2
Revisions (0)
No revisions yet.