I_love_Saundarya's blog

By I_love_Saundarya, history, 4 years ago,

There is N x M matrix filled with 0 and 1 only, lets say a matrix is special if every 2 x 2 sub matrix in it has two 0’s and two 1’s . Find the total number of special matrices you can have for N x M.

On the hunt of an efficient solution.

• 0

 » 4 years ago, # | ← Rev. 2 →   +8 The answer is$2^n+2^m-2.$ Why?You can notice that all special matrices have very similar form: Spoiler0101010 // or 1010101 1010101 // or 0101010 1010101 // or 0101010 ... Or the same thing but rotated by 90 degrees. For example: 001 110 001 110 001 110 001 So each row/column is either 101010... or 010101...However matrices like10100101and01011010(alternating rows / columns) can be represented both ways so we subtract two.Unfortunately, I'm not able to come up with proof for this.But you can verify it using bruteforce.P.S. This problem is similar to 1099E - Nice table
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Hint for a proofkostia244's "form" that all special matrices fit is equivalent to saying "there are either adjacent equal pairs in the X-direction or the Y-direction, but not both". Assume there's an adjacent horizontal pair of the same color somewhere, and an adjacent vertical pair of the same color somewhere, and try to reach a contradiction. Further hints/the restIf you have a horizontal pair of cells of the same color, then the cells directly above them have to be the other color, and so on, so that entire pair of columns has to be alternating, like this: 00 11 00 11 00 If you also have a vertical pair of the same color, then an entire pair of adjacent rows has to be alternating. Where this vertical double-column and horizontal double-row overlap, you have a contradiction.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 Thanks! Your hint really helped me and I was able to prove it.
 » 4 years ago, # |   +3 By the way, if you are interested in a slightly similar problem, check out 1178C - Tiles.