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.

-
Are you familiar with Hall's Marriage Theorem? – Gerry Myerson May 12 '12 at 12:28
Not yet. I try to find something. Can the Problem be solved with it. – user1374864 May 12 '12 at 13:02
The title suggests that you are looking for a particular kind of proof. Is this correct? – Phira May 12 '12 at 13:59

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)}$.