Problem 6.8. There are exactly 120 ways to color five cells in a $5 \times 5$ table so that each column and each row contains exactly one colored cell.

There are exactly 96 ways to color five cells in a $5 \times 5$ table without a corner cell so that each column and each row contains exactly one colored cell.

How many ways are there to color five cells in a $5 \times 5$ table without two corner cells so that each column and each row contains exactly one colored cell?
![](https://cdn.mathpix.com/cropped/2024_05_06_d4986512fdb0330805a0g-18.jpg?height=258&width=1008&top_left_y=530&top_left_x=220)
Answer: 78.

Solution. Consider the colorings of a $5 \times 5$ table described in the problem (i.e., such that in each column and each row exactly one cell is colored).

For convenience, let's introduce some notations. The top-left corner cell of the $5 \times 5$ table will be called $A$, and the bottom-right corner cell will be called $B$. Suppose that among the colorings of the first table, exactly $a$ have the cell $A$ colored, and exactly $b$ have the cell $B$ colored. Clearly, $a=b$ due to symmetry.

Notice that the number of colorings of the second table is equal to the number of colorings of the first table where the cell $A$ is not colored. The number of colorings of the third table is equal to the number of colorings of the first table where neither $A$ nor $B$ is colored. To find this, we subtract from 120 the number of colorings of the first table where $A$ or $B$ is colored. To count the number of such colorings, we add $a$ and $b$, and then subtract what has been counted twice - the ways where both $A$ and $B$ are colored.

All colorings of the first table can be divided into two types: those in which the cell $A$ is colored, and those in which it is not. This leads to the equation $120=a+96$, i.e., $a=24$. Then $b=24$ as well.

The number of colorings where both $A$ and $B$ are colored is the same as the number of ways to color the central $3 \times 3$ square. It is easy to see that there are exactly $3!=6$ such ways (to choose the colored cell in its top row, there are 3 ways, in the middle row - 2 ways, and in the bottom row - 1 way).

Thus, the answer to the problem is the number $120-(24+24-6)=78$.

## 7th grade