# Tiling of a Four by Four Checkerboard Combinatorics Problem

We are playing a Halloween game in which we place either an orange piece or a black piece at each of the squares of a four by four chessboard. How many ways can we do this so that every pair of rows has matching squares at exactly two of the four positions within the rows? I have determined one way to be:

O B B O
B B O O
O O O O
O B O B

Where each O is an orange piece and each B is a black piece

And one can verify that this indeed satisfies the conditions.

But in how many total ways can we do this? Thank you!!!

-

First, count all the ways you can do it when the top row is all orange. Then each additional row must have exactly two oranges. There are $6$ ways of choosing two columns for each of these rows, but you cannot pick the same pair of columns for each row, and you cannot pick two rows with exact complements. If you pair a set with its omplement, then that means you need to pick one row from each of the pairs.

The pairs are:

$$\{\{1,2\},\{3,4\}\}$$ $$\{\{1,3\},\{2,4\}\}$$ $$\{\{1,4\},\{2,3\}\}$$

So, $\{1,2\}$ corresponds to a row with orange on the columns $1$ and $2$.

There are $8$ ways of picking a row from each pair (and it turns out you can do so arbitrarily, although you have to show that,) and then $6$ ways to order them, so the total, when the top row is all orange, is $48.$

The more general solution is $48*16$, because you show that, for any top row, you get the same number of possible corresponding rows.

If you want to treat solutions the same if you can re-order the rows in one to get the other, then you have $32=48*16/24$ solutions.

-

There are $2^4=16$ ways to choose the first row. There are then $\binom42=6$ ways to choose the two columns in which the second row agrees with it; those completely determine the second row, so there are $16\cdot6=96$ ways to choose the first two rows. Suppose that the first two rows agree in columns $c_1$ and $c_2$. If the third row agreed with the first and second in those two columns, it would have to agree in at least one more column with at least one of the first two rows, so it must differ from the first two rows in at least one of columns $c_1$ and $c_2$. On the other hand, it cannot differ from the first two rows in both of these columns, as it would then be unable to agree with both of them in the other two columns. Thus, it must agree with the first two rows in one of columns $c_1$ and $c_2$ and disagree with them in the other.

Assume now that the third row agrees with the first two in column $c_1$ and disagrees with them in columns $c_2$. Let the other two columns be $c_3$ and $c_4$. The first two rows disagree with each other in both $c_3$ and $c_4$, so in order to get a second column of agreement with both of them, the third row must have different colors in columns $c_3$ and $c_4$. This can be accomplished in two ways. The fourth row, like the third, must agree with the first two in one of columns $c_1$ and $c_2$ and disagree in the other. If it matches the third row in these two columns, it must disagree with the third row in columns $c_3$ and $c_4$; if it disagrees with the third row in columns $c_1$ and $c_2$, it must agree with the third row in columns $c_3$ and $c_4$. Thus, once the third row has been filled in, there are just two ways to fill in the fourth row. This produces a total of $96\cdot2\cdot2=384$ squares.

The case in which the third row agrees with the first two in column $c_2$ and disagrees with them in column $c_1$ is exactly similar, so the final total is $2\cdot384=768$ squares.

-