I was solving the puzzle for the Company interview exam. I found this puzzle, I cannot come up with the solution. How to solve it and what is the correct answer?

Determine the number of $4\times 4$ matrices having all entries 0 or 1 that have an odd number of $1$s in each row and each column.

  • $\begingroup$ What company asks these questions? $\endgroup$ – copper.hat Jul 29 '12 at 6:53

Fill the upper-left hand $3\times 3\,$ arbitrarily with $0$'s and/or $1$'s. This can be done in $2^9$ ways.

For any such choice of $0$'s and/or $1$'s, fill in the first three entries in the fourth row, and the first three entries in the fourth column, so that the number of $1$'s in each of the first three columns, and in each of the first three rows, is odd. This can be done in precisely one way.

Now put a $0$ or a $1$ in the lower right-hand corner, to make the number of $1$'s in the bottom row odd. It turns out that this makes the number of $1$'s in the rightmost column odd. To check this, work modulo $2$.

| cite | improve this answer | |
  • $\begingroup$ So,what is the final answer .Is it 2^9 ?.Also ,can i generalize this for k*k square Matrix. $\endgroup$ – Maths123 Jul 28 '12 at 22:46
  • 2
    $\begingroup$ Yes, the answer is $2^9$. And it does generalize. $\endgroup$ – André Nicolas Jul 28 '12 at 22:46
  • $\begingroup$ Thanks a lot.Also,I have doubt,is there any general formula if the matrix is n*m ,where n not equal to m. $\endgroup$ – Maths123 Jul 28 '12 at 22:50
  • 3
    $\begingroup$ In general, there are $2^{(m-1)(n-1)}$ solutions if $m-n$ is even, and no solutions if $m-n$ is odd. The basic strategy should be unchanged. $\endgroup$ – Erick Wong Jul 28 '12 at 22:59

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.