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.