Matching squares

combinatoricsgeometry

Mary has $3$ white, $4$ black and $3$ gray tokens, all the same shape and different only in relation to the color. She places chips on the next board, made up of matching squares, at most one chip per little square. How many different ways can she put on the board

$a)$ exactly three tokens, one white, one black and one gray only in the first row
horizontal?

$b)$ exactly three black chips on the second horizontal line only?

$c)$ exactly three chips of different colors?

$d)$ all ten tokens, so that in two squares with one common side there are not two black tokens?

enter image description here

Attemp: A.) $6$. We need one black, one white, and one gray which can be ordered $3!=6$ ways.

B.) $4$. There are $4$ ways to leave out one square and we don’t need to worry about ordering as they are all black pieces

C.) $720$. $\binom{10}{3}$ ways to pick squares, $3!$ ways to order, $120 \cdot 6 = 720$.

Best Answer

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

Related Question