Painting a different board in a particular way

combinatorics

I would like to know if anyone of you can help me to understand the following question:

You have to paint this board

You need to paint each of those squares in a particular way:

Three cells must be white;
Three cells must be gray;
Four cells must be black;
You can not paint of black two cells that share a commum side

I tried to do it using Inclusion-exclusion principle, but I did not succeed. I would appreciate some help with this problem.

Best Answer

As there are restrictions on which cells can be painted black, let's first find all combinations of $4$ cells that can be painted black and let's call them good cells. Call columns of square with $9$ cells, $A, B, C$ from left to right and rows $1, 2, 3$ from top to bottom.

Case 1: Cell $0$ is painted black. So cell $A2$ is ruled out and we have to choose $3$ good cells from rest $8$.

a) Column $A$ has no good cells

Column $B$ can have either $1$ or $2$ good cells. Column $C$ can have either $2$ or $1$ good cells based on column $B$.

As we need $3$ good cells, number of ways $= 2$

b) Column $A$ has $1$ good cell

Number of possible ways: $2$ (cell $A1$ or $A3$)

Column $B$ can have only i) $0$ good cell or ii) $1$ good cell in $2$ possible ways for each good cell in column $A$.

Column $C$ can have only i) $2$ good cell in $1$ possible way or ii) $1$ good cell in $2$ possible ways for each good cell in column $B$.

Number of possible ways = $2 \times (1+2 \times 2) = 10$.

c) Column $A$ has $2$ good cells

Number of possible ways: $1$ (cells $A1, A3$)

Column $B$ can have only i) $0$ good cell or ii) $1$ good cell in $1$ possible way.

Column $C$ can have only i) $1$ good cell in $3$ possible ways or ii) $0$ good cell.

Number of possible ways $= 1 + 3 = 4$.

So total number of combinations for Case $1 = 16$

Case 2: cell $0$ is not painted black. So we have to choose $4$ good cells from rest $9$.

Case $2$ is more straightforward as it has more restrictions.

$1$ good cell each in column $A$ ($A1$ or $A3$) and column $B$ ($B2$) and $2$ in column $C$ ($C1, C3$): $2$ possible ways
Similarly, $2$ good cells in column $A$, $1$ each in column $B$ and $C$: $2$ possible ways
$1$ good cell in column $A$ ($A2$), $2$ in column $B$ ($B1, B3$) and $1$ in column $C$ ($C1$): $1$ possible way
$2$ good cell in column $A$ ($A1, A3$) and $2$ in column $C$ ($C1, C3$): $1$ possible way

So total number of combinations for Case $2 = 6$

Total number of valid combinations of $4$ black cells $= 22$.

Now, we can choose $3$ cells out of remaining $6$ to paint white in $^6C_3$ ways. Rest $3$ will automatically be grey.

So total number of valid ways to paint = $22 \times ^6C_3 = 440$

Related Solutions

[Math] Please explain the proof of the Mutilated Chessboard Problem

The proof with the first coloring works for this particular problem. The proof for the second doesn’t. That’s really the end of the matter.

You can try to make the argument more formal if that makes more sense to you. Assign a coordinate to each square on the chessboard, so that the top left corner is at $(1,1)$, and the bottom right corner is at $(8,8)$. The “white” squares will now correspond to the squares whose coordinates add to an even number, while the “black” squares will have coordinates that add to an odd number. It’s easy to see that when we remove both previously mentioned corners, we’re left with $32$ black squares, and $30$ white squares. However, a domino, which spans two adjacent squares, must necessarily cover both a white and a black square. Therefore, any valid covering must cover the same number of white and black squares, which means it’s impossible to cover up the whole mutilated board.

Your second coloring not working is just a consequence of the proof above not working for the corresponding modified definitions of the “white” and “black” squares. But a proof not working does not at all imply that another one is false.

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

Best Answer

Related Solutions

[Math] Please explain the proof of the Mutilated Chessboard Problem

Matching squares

Related Question