Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.