3

For a $4\times 4$ grid, we have $8$ positive signs and $8$ negative signs to fill. How many ways are possible to fill the grid such that every row and every column has exactly $2$ positive signs and $2$ negative signs.

I am getting the answer as $96$, but I am unsure about the method I used. Is there any method where we don't have to take separate cases to find this?

Vinyl_cape_jawa
  • 4,794
Avinash Bhawnani
  • 769
  • what method did you used to arrive at $96$? – Vinyl_cape_jawa Nov 20 '17 at 13:10
  • There are only two possibilities in a row. ++-- or +-+-, and all others are just rotation of them. Now either the type 1's all rotations or type 2's all rotations will come in 4 rows so 4! + 4!, or 2 of type 1 and 2 of type 2. Someone told me that the correct answer will come by taking cases, but I don't want to solve it by that method. – Avinash Bhawnani Nov 20 '17 at 14:30
  • 1
    I can't find a way to do it without cases, and I'm not sure if it's possible. You shouldn't be afraid to work with cases though; there are times when you'll have to. – Kevin Long Nov 20 '17 at 16:56

1 Answers1

2

I can't do it without cases, but I think this is a clean solution.

Note that if you know the first three rows of such a grid, you know the last row. We will find all ways to construct the first three rows. There are $4\choose 2$ ways to determine the first row. We consider three cases for the second row: $(1)$ the second row is a copy of the first row, $(2)$ the second row is the complement of the first row ($-$ and $+$ are swapped), and $(3)$ the first and second row agree partially, meaning there is one column where they both have $+$ and one column where they both have $-$, but on the other two, they have different signs.

In case $(1)$, there is only one way to pick the second row. Furthermore, this determines the third and fourth row, as two columns have two $+$s so far and the other two have two $-$s, so the third and fourth row have to be the complement of the first. There is only one possibility here.

In case $(2)$, there is also only one way to pick the second row. However, the third row has multiple choices. Each column has a $+$ and a $-$, so the third row can in fact be any row with two of each sign, and that will determine the fourth row. There are $4\choose 2$ such rows, and hence $4\choose 2$ possible grids here.

In case $(3)$, there are four ways to pick the second row; if the first row has $+$ in columns $a_1$ and $a_2$ and $-$ in columns $b_1$ and $b_2$, then the second row picks one of $a_1,a_2$ to have a $+$ and one of $b_1,b_2$ to have a $-$, and they'll disagree on the other two columns. Say they agree on columns $a_1$ and $b_1$, meaning they both have $+$ on $a_1$ and $-$ on $b_1$. Then the third row must have $-$ on $a_1$ and $+$ on $b_1$. However, on $a_2$ and $b_2$, there is a $+$ and $-$, so the third row can have $+$ on $a_2$ and $-$ on $b_2$, or vice versa. Then there are $2$ choices for the third row, which then determines the fourth row, so there are $8$ possibilities for this case total.

Then the total number of possibilities is ${4\choose 2}(1+{4\choose 2}+8)=90$.

Kevin Long
  • 5,159