2
$\begingroup$

Given a 2n by 2n matrix of cells, if each row and each column has exactly n cells of red color and remaining n cells of blue color, prove that for each row with reds in particular positions, there is another row with only blues in those positions.

Conversely, if rows cannot be paired as described above, prove that the matrix cannot be colored with each row and each column containing equal number of reds and blues.

NOTE: What I have asked above is to prove a conjecture that is a figment of my thought process which I used as part of solving a different puzzle.

$\endgroup$
2
$\begingroup$

Your conjecture is false. Below, none of rows $1$ through $4$ have a complement.

or $$ \begin{matrix} 1&1&0&0&1&0\\ 0&1&1&0&0&1\\ 0&0&1&1&1&0\\ 1&0&0&1&0&1\\ 1&0&1&0&1&0\\ 0&1&0&1&0&1 \end{matrix} $$

$\endgroup$
  • $\begingroup$ Nice! I looked for $4 \times 4$ counterexamples, became mostly convinced that there were none, but that for larger sizes there might be...but didn't get as far as constructing one. $\endgroup$ – John Hughes May 16 '18 at 17:46
  • $\begingroup$ Thank you, @Mike Earnest, my intuition was wrong. I was led down this path of trying to find a necessary and sufficient condition was the peculiarities involved in the Coloring pattern - equal proportions of coloured and non-colored cells in each row and each column. I'd still be interested in decoding this pattern into the condition that is required to hold for the pattern to be possible. Some other time I guess! $\endgroup$ – Deepak Gupta May 18 '18 at 12:42

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.