1
$\begingroup$

Does there always exists a $n \times n$ grid with $0$s and $1$s that satisfy the following conditions:

  1. there is an equal number of 1s and 0s in each row and column
  2. no more than two identical numbers next to or below each other are allowed
  3. there can be no identical rows or columns

How to construct a nxn grid that satisfy all the above conditions?

$\endgroup$
7
$\begingroup$

To meet condition 1, $n$ must be even, so let's assume that it is. Then we can automatically achieve both conditions 1 and 2 by making an $n/2\times n/2$ matrix whose entries are $2\times 2$ submatrices in one of the two patterns $$ \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right),\quad \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right), $$ as these prevent any three consecutive digits (in either direction) from being equal.

Now all you need to do is to choose which of these two $2\times 2$ matrices to use in which position of the $n/2\times n/2$ matrix. You must now avoid both equal rows and columns, and complementary rows and columns, but that's still very easy, for instance by putting the 1-0-0-1 matrices down the main diagonal and the 0-1-1-0 matrices everywhere else.

$\endgroup$

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.