3. (17 points) In a $5 \times 5$ grid, 6 crosses need to be placed such that each row and each column contains at least one cross. How many ways can this be done?
# Answer: 4200

Solution. From the condition, it follows that in some row $a$ and some column $b$ there are two crosses (and in all other rows and columns - one each). Both row $a$ and column $b$ can be chosen in 5 ways. There are two possible cases.

First. At the intersection of $a$ and $b$, there is a cross. We choose one more cross from each line in 4 ways. Now, three rows and three columns remain unoccupied. The remaining crosses are placed at their intersections in $3 \cdot 2 \cdot 1=6$ ways. Thus, there are $5 \cdot 5 \cdot 4 \cdot 4 \cdot 6=2400$ arrangements of the first type.

Second. At the intersection of $a$ and $b$, there is no cross. Then, we choose two crosses from each of these two lines in $4 \cdot 3 / 2=6$ ways. Now, two rows and two columns remain unoccupied. The remaining crosses are placed at their intersections in two ways. Thus, there are $5 \cdot 5 \cdot 6 \cdot 6 \cdot 2=1800$ arrangements of the second type.

In total, there are $2400+1800=4200$ ways to arrange 6 crosses.