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$

1 Answer 1

Reset to default
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$
2
  • $\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
    Commented May 16, 2018 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
    Commented May 18, 2018 at 12:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .