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.

Consider a binary grid of size 4*4, each of cell can either have 0 or 1. Among all possible 2^16 arrangement how many arrangement of such grid exist in which each row and column contains even number of 1s.

Solution which I thought

There will be 2 possibilities for the answer of this question 1st all ones in the 4*4 grid that will count up to 1 possible arrangement and 2nd possibility will be 2 1 in each row and column so how can i find the possible arrangement which will have 2 1 in each row and column.

Am I right?

share|improve this question
    
Why is it not possible that some rows contain four 1s and some rows contain two 1s? –  TMM Jul 6 '12 at 21:38

2 Answers 2

up vote 5 down vote accepted

Let the positions be $a_{i,j}$, where $1\le i,j\le 4$. You can fill the $3\times 3$ square in the upper lefthand corner, i.e., positions $a_{i,j}$ with $1\le i,j\le 3$, any way you like. Once those $9$ positions are filled, there is exactly one way to fill the remaining $7$ positions to get an even number of $1$’s in each row and column. Can you see why? (HINT: Fill $a_{4,4}$ last.)

share|improve this answer

Hint: how many choices are there for the first column, ignoring the question of rows? You can put each of these in the first three columns, any way you want. Then each row forces the element in the fourth column. You then have to prove that the fourth column will have an even number of ones.

share|improve this answer

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.