3. (17 points) In a $4 \times 4$ grid, 5 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: 432

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 4 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 3 ways. Now, two rows and two columns remain unoccupied. The remaining crosses are placed at their intersections in 2 ways. Thus, there are 4.4$\cdot$3$\cdot$3$\cdot$2=288 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 3 ways. Now, only one row and one column remain unoccupied, at the intersection of which a cross needs to be placed. Thus, there are 4$\cdot$4$\cdot$3$\cdot$3=144 arrangements of the second type. In total, there are $288+144=432$ ways to arrange 5 crosses.