5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Suppose you choose a permutation $\pi$ uniformly at random. The set $P = \{ a_{i, \pi(i)} \mid i\in [n]\}$ contains exactly one cell in each row and in each column. What is the probability that $P$ contains both cells with value $1$? $\endgroup$ – JeffE May 12 '12 at 11:41
  • 1
    $\begingroup$ I removed probabilistic related tags, cause this can be done just by combinatorial stuffs, any probabilistic way for this should be drive from some combinatorics, so it's better to prove it directly. $\endgroup$ – user742 May 12 '12 at 11:57
  • $\begingroup$ Can this problem be mapped into a problem on latin squares? $\endgroup$ – Виталий Олегович May 12 '12 at 12:02
  • 3
    $\begingroup$ @SaeedAmiri: Huh? "Better"? Just because something can be done combinatorially doesn't mean that it can't be done more easily via probability. $\endgroup$ – JeffE May 12 '12 at 15:23
  • $\begingroup$ @JeffE, Yes IMO, it's better to use combinatorics directly, if you have a pure probabilistic way, I'll be thankful to know it. $\endgroup$ – user742 May 12 '12 at 18:19
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes so simple :) $\endgroup$ – user742 May 13 '12 at 7:45
  • 1
    $\begingroup$ This technique is known as probabilistic method. $\endgroup$ – Raphael May 14 '12 at 15:36
  • 2
    $\begingroup$ @SaeedAmiri Raphael's comment was about JeffE, it wasn't addressed to you. There is nothing offensive about it. You may be misunderstanding. $\endgroup$ – Gilles May 14 '12 at 19:47
  • $\begingroup$ @Gilles, May be, I hope to be so. I said this because of two reasons: 1. Me and Jeff discussion in comments (finally is obvious that I accepted Jeffe is right, at least with my comment on his answer and I thought there is no need to tell this) 2. Me and Raphael had a discussion (may be argue) before, and I'm biased with this prejudice :) $\endgroup$ – user742 May 14 '12 at 20:12
4
$\begingroup$

There are $n!$ ways to choose cells. The number of different possible ways of choosing cells such that we have at least two cells with the same content is at most $n \cdot (n-2)!$. For $n\ge 4$, this number always satisfies $n! \gt n\cdot (n-2)!$, so by the pigeonhole principle there are always some selections with distinct numbers.


Why?

First $n!$ is obvious, all permutations.But $n\cdot(n-2)!$: take one of a items from the first column, assume you want have a duplicate of this item, you can select it in at most $n$ different way (prove why at most). Find another column which has a same item, (if there is a column with this item in different row), fix that column, all other columns having $(n-2)!$ possible permutations, also this two fixed column will have at most $n$ permutation, so total possible ways is $n \cdot (n-2)!$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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