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 giving a look at my country's mathematical olympiads, and I found this problem

If I want to color a $4\times 4$ grid with black and white squares, in how many ways can I paint it such that every row and every column has 2 squares of each color?

After thinking for a while, I decided to code a program that gave me insights about the problem by reverse-engeneering the answer.No success.Aparently, the answer is $90$, but how does the mathematical way of doing this goes?

share|improve this question
    
Do you mean at least or exactly two black squares? –  Stefan Hamcke Aug 20 '13 at 0:14
    
@StefanH. Rahul Narain read my mind –  chubakueno Aug 20 '13 at 0:20
    
"of each color", therefore two black and two white squares. –  mau Sep 13 '13 at 8:32

5 Answers 5

up vote 3 down vote accepted

This problem asks for the enumeration of a special type of frequency square. Frequency squares are a generalisation of Latin squares, which are regarded as hard to count. To count Latin squares, the best method is Sade's Algorithm, which we can use here too. The main observations are:

Lemma: Any two frequency rectangles that have the multiset of symbols in each column can be completed in the same number of ways.

Lemma: Frequency rectangles formed by permuting the rows and columns of another frequency rectangle can be completed in the same number of ways.

The above two Lemmata provide an equivalence relation on frequency rectangles, which we can exploit to find the answer.

Under this equivalence, there are $\binom{4}{2}=6$ ways of creating the first row, all of which are equivalent to:

enter image description here

This can be extended in $\binom{4}{2}=6$ ways, $3$ of which are inequivalent. After this, we could continue using Sade's Algorithm, but it's faster to just count the completions:

  • Equivalence class size 1:

    enter image description here

    1 completion.

  • Equivalence class size 4:

    enter image description here

    2 completions.

  • Equivalence class size 1:

    enter image description here

    6 completions.

So, in total we have $$6 \times (1 \times 1+4 \times 2+1 \times 6)=90$$ such squares.

share|improve this answer
    
Wow. I really did not expect to find so deep theorems about a simple problem like this(first stage of the olympiad, although the hardest problem there). Seeing your profile, I am also quite convinced that a generalistion is a bit too far. Thank you for your answer and for giving me that good feeling of doing a good blind-coding. –  chubakueno Aug 20 '13 at 1:49

Another method is to recognise that, up to permutations of the rows and columns, there are only two inequivalent squares:

$$ \begin{array}{|cccc|} \hline 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ \hline \end{array} \quad\quad\quad\text{and}\quad\quad\quad \begin{array}{|cccc|} \hline 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ \hline \end{array} $$ These are the biadjacency matrices of the vertex-coloured bipartite graphs:

enter image description here $\quad\quad\quad\text{and}\quad\quad\quad$ enter image description here

respectively. So the number of such matrices is equal to the number of (vertex-coloured, labelled) graphs isomorphic to one of the two bipartite graphs above.

By the Orbit Stabiliser Theorem, we can compute the sizes of these isomorphism classes by computing the sizes of the automorphism groups (which can be done by hand). Thus, these have isomorphism classes of size:

$$\frac{4!^2}{2^5} \quad\quad\quad\text{and}\quad\quad\quad \frac{4!^2}{8}$$ respectively. These sum to $90$.

share|improve this answer
    
How did you determined that the first two were the only inequivalent squares? And, would you mind explaining me the meaning of your graphs and where did you get the last two values? –  chubakueno Aug 20 '13 at 1:56
    
To make it formal, the matrix is the sum of two permutation matrices corresponding to permutations $\alpha$ and $\beta$ (Hall's Marriage Theorem implies this is always possible). The permutation $\alpha(i) \mapsto \beta(i)$ will be a derangement on $4$ points, so can only have cycle structure $2+2$ or $4$, corresponding to the two equivalence classes (the structure is apparent in the bipartite graph). Alternatively, in such a small case, we could make some ad hoc argument. –  Douglas S. Stones Aug 20 '13 at 2:18

This explanation is a little more wordy, but hopefully will help you with the kind of intuition you need to solve similar problems.

So there are ${{4}\choose{2}} = 6$ ways to choose the 2 black squares in the first row. Once we have chosen those two squares we know there are two columns where we must pick exactly one more black square. For example, if we choose columns 2 and 3 for row one, then we must pick 1 more black in column 2 (in either row 2, 3, or 4), and 1 for column 3. There are ${{3}\choose{1}} = 3$ ways to do this for each column, so $3^2 = 9$ ways in total for both columns.

Now, suppose we picked both choices to be on the same row, then there would be two empty rows of which we only have one possible choice for the remaining 4 blacks. For example, using notation (row,column), say we first picked (1,2) and (1,4), and then (3,2) and (3,4), then we have (2,1), (2,3), (4,1), and (4,4) left as possible choices for our 4 remaining blacks, giving ${{4}\choose{4}} = 1$ as stated. If our choices are not on the same row then there are 2 possible choices for the 4 remaining blacks as we can choose which column to put the first remaining black out of the 2 remaining columns. For example, if we first picked (1,2) and (1,4), and then (2,2) and (3,4), it is now easy to see there are only 2 sets of remaining positions that satisfy the requirements, i.e. {(2,1),(3,3),(4,1),(4,3)} and (2,3),(3,1),(4,1),(4,3)}.

There are 6 ways for the second 2 blacks to be arranged in the 2 columns such that the don't fall onto the same row. And as each of these has an additional way of arranging the 4 remaining blacks, we have a total of $9 + 6 = 15$ ways to choose the remaining 6 blacks once we choose the first 2. Thus in total we have $6 \times 15 = 90$ ways to arrange the blacks.

share|improve this answer

I have not looked at the general problem. For this $4\times 4$ problem, we can without loss of generality assume that the two black squares in the top row are the first two squares on the left. Whatever answer we get can then be multiplied by $\binom{4}{2}=6$.

We can also assume that the square immediately below the top left square is black. Whatever answer we get can then be multiplied by $\binom{4}{2}(3)$ to get the full count.

Now it is not difficult to list by hand all configurations with these specified squares black. One can even take additional advantage of symmetries to shorten the count, but in this case it is not needed.

Remark: Presumably the computer cannot be carried into the examination room. But we don't need it. Anyway, at least for me, debugging the program would take a lot longer than solving the problem.

share|improve this answer

Label the columns $\{1,2,3,4\}$. Let $S_i$ be the set of labels of the columns painted black on row $i$. Then we have two cases:

  • Some $S_i=S_j$ for $i\neq j$
  • There is not.

The counting of these two case is essentially the problem.

The first case is easy.

The second case involves permutations of the set of columns, $x_1,x_2,x_3,x_4$ with $x_1<x_2$. Then we get the first row is $\{x_1,x_2\}$ and the other rows are some permutation of $\{x_2,x_3\},\, \{x_3,x_4\},\,$ and $\{x_4,x_1\}$.

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.