11
$\begingroup$

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.

  • 0
    What company asks these questions?2012-07-29

1 Answers 1

11

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$.

  • 3
    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.2012-07-28