15. In the $4 \times 4$ grid some cells must be painted black. The numbers to the right of the grid and those below the grid show how many cells in that row or column must be black.
In how many ways can this grid be painted?
A 1
B 2
C 3
D 5
E more than 5
SolUTION
D
The diagrams use grey shading for any cells that cannot be painted black. The left-hand column needs two black cells and this can be done in three ways:
1) Paint the bottom two cells black. Then the top left is grey, forcing the top row to have two black cells on the right. Then we can shade grey the row and column that required one black cell each. This leaves just one possible position for the last black cell.
2) Paint the top and the bottom cells black. The other cell in the column is then grey, leaving the second row up with two black cells on the right. Shade in grey the row and column requiring one black cell. This leaves one position left for a black cell.
3) Paint black the second and fourth cells from the bottom. There are then two options for the second black cell in the top row. Choosing the top right to be black leads to the solution shown on the right. However, colouring the third cell of the top row in black leaves two choices for the second black cell in the third column; each of these leads to the solutions shown.
Thus there are five ways to paint the grid.