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
    The title suggests that you are looking for a particular kind of proof. Is this correct?2012-05-12

1 Answers 1

6

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.