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.
Asked By : user1374864
Answered By : JeffE
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1803
0 comments:
Post a Comment
Let us know your responses and feedback