2
$\begingroup$

You want to create a matrix of size MxN using only 0 & 1. But there is rule-

There must not be any submatrix with its (rows>1 & columns>1) and filled with same number.

For example-

for a 3x3 matrix-

0 1 1 1 0 0 1 1 0 

is allowed but-

1 0 0      1 0 1 0 0 0  or  0 1 1 1 1 1      1 1 1 

are not allowed. How many such matrices of size MxN are possible?

  • 1
    Does a submatrix have consecutive rows and columns, or just any? Also, isn't the condition equivalent to the simpler condition that there must not be a constant $2\times2$ submatrix?2012-11-04
  • 0
    submatrix have consecutive rows and columns. Its not similar to that, because there might be a 2x3 matrix in above example which has same number.2012-11-04
  • 0
    I don't understand. How can there be a constant $2\times3$ matrix without there being a constant $2\times2$ matrix?2012-11-04
  • 0
    Sorry I didnt get your point at that time. Yes i think problem can be reduced to 2x2 submatrix.2012-11-04
  • 0
    Do you have any approach for 2x2 submatrix?2012-11-04

1 Answers 1