Extracting non-duplicate cells in a particular matrix with repeated entries

Question

Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \left\{1,...,\frac{n^2}{2}\right\}$ 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.

This was an example problem for an exam I'm studying for. I tried it now for several hours but I can't get it right. I think random permutations can help here but I am not sure.

Answer 1

Choose a permutation $\pi$ uniformly at random, and let $P = \{ a_{i, \pi(i)} \mid i\in [n]\}$. The set $P$ contains exactly one element in each row and each column of given the matrix $A$.

Now consider any pair of entries in $A$ with the same value. If those two entries lie in the same row or the same column, they cannot both be in $P$. If those two entries are in different rows and columns of $A$, then the probability that both entries lie in $P$ is exactly $1/n(n-1)$.

There are $n^2/2$ different values in the matrix. So the expected number of values with both entries in $P$ is at most $n^2/2n(n-1) = n/2(n-1)$. If $n\ge 4$, this expected value is less than $1$, which implies that the probability of choosing no matching pairs must be positive.

Answer 2

There are $n!$ ways to choose cells. The number of different possible ways of choosing cells such that we have at least two cells with the same content is at most $n \cdot (n-2)!$. For $n\ge 4$, this number always satisfies $n! \gt n\cdot (n-2)!$, so by the pigeonhole principle there are always some selections with distinct numbers.

---

Why?

First $n!$ is obvious, all permutations.But $n\cdot(n-2)!$: take one of a items from the first column, assume you want have a duplicate of this item, you can select it in at most $n$ different way (prove why at most). Find another column which has a same item, (if there is a column with this item in different row), fix that column, all other columns having $(n-2)!$ possible permutations, also this two fixed column will have at most $n$ permutation, so total possible ways is $n \cdot (n-2)!$.