Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What company asks these questions? –  copper.hat Jul 29 '12 at 6:53

1 Answer 1

up vote 11 down vote accepted

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

share|improve this answer
    
So,what is the final answer .Is it 2^9 ?.Also ,can i generalize this for k*k square Matrix. –  Maths123 Jul 28 '12 at 22:46
2  
Yes, the answer is $2^9$. And it does generalize. –  André Nicolas Jul 28 '12 at 22:46
    
Thanks a lot.Also,I have doubt,is there any general formula if the matrix is n*m ,where n not equal to m. –  Maths123 Jul 28 '12 at 22:50
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. –  Erick Wong Jul 28 '12 at 22:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.