A probabilistic method I am trying to study for a exam and i found a assignmet, that i cant solve.
Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \{1,...,\frac{n^2}{2}\}$ is written to two cells so that each cell contains exactly one number.
How can i show that $n$ cells $c_{i, j}$ can be chosen with one cell per row and one cell per column such that no pair of cells contains the same number.
I tried it now for severel hours but i cant get it right.
I think random permutations can help here but i am not sure.

The standard probabilistic approach would be the following:
For each $i$, calculate the probability that both $i$s are in the permutation provided that they are not already in the same row/column (then the probability is zero, of course). This gives $\dfrac 1 {n(n-1)}$, since there are $n(n-1)$ possible selections from the rows containing $i$ and only one that gives the two $i$s.
Sum these probabilities for all $i$s to get an upper bound for the expected value of pairs in a randomly chosen permutation. This gives $\dfrac{n}{2(n-1)}$.
Observe that this expected value is smaller than 1 which implies that there has to be at least one permutation without a pair of the same values.
