Deleting rows and columns of a matrix probability I was recently asked this question in an interview:
Let's say we are playing beer-pong with a $4$x$4$ arrangement of cups, each time you get a ball in one of the cups, the row and column containing that cup are removed. Given that the ball has to land within the $4$x$4$ arrangement and the aim is to remove all the cups, what is the probability that you win the game in the minimum number of throws?
So, the minimum number of throws is $4$, right? The idea is that if we select the $4$ elements on the diagonal, each will require a unique throw. I am not able to figure out a clean way of figuring out the number of ways in which the arrangement can be cleared in 4 moves. Seems like a simple counting problem, but I am not sure how to approach it.
 A: Edit: The following answer assumes a throw is guaranteed to land on the remaining cups. If instead the ball can land on the space of a removed cup, see the end of the answer.

You are guaranteed to win in exactly $4$ throws.
Suppose you win the game in $n$ throws. We will prove that $n = 4$.
Let $r_i \in \{1, 2, 3, 4\}$ be the integer such that the $i$-th throw land on the $r_i$-th row. Since the $r_i$-th row will be removed upon the $i$-th throw, we know that $r_1, r_2, \dots, r_n$ must be pairwise distinct. But $r_1, r_2, \dots, r_n$ only have four possible values (which are $1$, $2$, $3$, and $4$). Hence, we must have $n \leq 4$.
On the other hand, we know $n \geq 4$. This is because no two cups on the main diagonal (i.e., cups at first row first column, second row second column, third row third column, fourth row fourth column) can be removed in the same throw, as they are in different rows and columns. So, we need at least $4$ throws to remove those $4$ cups.
In conclusion, $n = 4$. Therefore, the probability to win with the least number of throws is $1$.

If instead the ball can land on the space of a removed cup, then the probability is $\frac{16}{16} \cdot \frac{9}{16} \cdot \frac{4}{16} \cdot \frac{1}{16}$. This is because we have established above that any four throws will make you win as long as every throw lands in a cup that has not been removed.
