1
$\begingroup$

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.

  • 0
    Are you familiar with Hall's Marriage Theorem? – 2012-05-12
  • 0
    Not yet. I try to find something. Can the Problem be solved with it. – 2012-05-12
  • 0
    The title suggests that you are looking for a particular kind of proof. Is this correct? – 2012-05-12

1 Answers 1