[Math] Mathematical reasoning question

combinatoricscontest-math

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?

Best Answer

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$

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

Related Solutions

Matching squares

Your answers to A, B, C are correct. Part D is substantially more complicated. Here is one way to do it.

Lets name the squares $0, 1, 2, \dots, 9$ and also color them red or green in a checkerboard pattern, as follows:

   R0
R1 G2 R3
G4 R5 G6
R7 G8 R9

We will count the ways to place the four black tokens s.t. no two of them touch on a side. The red/green coloring helps the counting.

All $4$ in red squares: There are ${6 \choose 4} = 15$ ways.
All $4$ in green squares: There is only $1$ way.
$3$ red, $1$ green: If G4, G6 or G8 is picked, that rules out $3$ red squares and the black tokens must go in the other $3$ red squares. If G2 is picked, that rules out $4$ red squares and it becomes impossible to occupy $3$ red squares. Total no. of ways $= 3$.
$3$ green, $1$ red: If G4, G6 or G8 is unused, the used green squares would eliminate all red squares. If G2 is unused, the only remaining red square is R0. So there is only $1$ way.
$2$ green, $2$ red: Further case analysis on which two green squares are used:
- G2G4 or G2G6 or G4G6 would eliminate $5$ red squares;
- G2G8 would eliminate all $6$ red squares;
- G4G8 or G6G8 would eliminate $4$ red squares, so in each case the $2$ red squares are forced;
- Total no. of ways $=2$ (G4G8 or G6G8).

Therefore in total there are $15 + 1 + 3 + 1 + 2 = 22$ ways to place the $4$ black tokens. Once the black tokens are placed, we just need to pick which $3$ of the remaining $6$ squares will have white tokens. So the final answer to part D is:

$$22 \times {6 \choose 3} = 22 \times 20 = 440 $$

In an $8×8$ table one of the square is colored black and all the others are white . Prove that one cannot make all the boxes white by recoloring the r

Your analysis for the $8 \times 8$ square amounts to saying that each operation leaves the parity of the total number of black squares unchanged. This assertion is accurate, and therefore, the analysis is valid. The assertion critically depends on the idea that $(8-1)$ has the same parity as $(1)$.

For the $3 \times 3$ square, this specific approach is invalid, because (for example) $(3-1)$ does not have the same parity as $(1)$.

At this point, it is unclear whether the same conclusion is accurate in the $3 \times 3$ square. That is, there may exist a similar but different valid argument that involves $\pmod{n}$, where $n$ is some positive integer other than $(2)$.

For what it's worth, an alternative (convoluted and therefore inferior) approach for the $8 \times 8$ square is to recognize that the computation of $(W - B)$ (i.e. # of white squares - number of black squares) is unchanged $\pmod{4}$ because (for example) $[(+6) - (-6)] \equiv 0\pmod{4}$.

This yields a similar contradiction, as your analysis of the $8 \times 8$ square, because $(63 - 1) \equiv 2\pmod{4}.$

Best Answer

Related Solutions

Matching squares

In an $8×8$ table one of the square is colored black and all the others are white . Prove that one cannot make all the boxes white by recoloring the r

Related Question