$f,g$ are two permutations of set $X=\{1,\dots,n\}$. We say $f,g$ have common points iff there is a $k\in X$ that $f(k)=g(k)$. a) If $m>\frac{n}{2}$, prove that there are $m$ permutations $f_{1},f_{2},\dots,f_{m}$ from $X$ that for each permutation $f\in X$, there is an index $i$ that $f,f_{i}$ have common points. b) Prove that if $m\leq\frac{n}{2}$, we can not find permutations $f_{1},f_{2},\dots,f_{m}$ satisfying the above condition.
Problem
Source: Iranian National Olympiad (3rd Round) 2002
Tags: graph theory, combinatorics proposed, combinatorics
julien_santini
08.10.2006 17:10
a) is easy, take $f_{1}=Id$, $f_{2}=Id+1$, $f_{k}=Id+k-1$, where the equalities are understood to be modulo $n+1$. What about b) ?
julien_santini
09.10.2006 12:31
This is, indeed, very nice ! Are Iranian olympiads competitors supposed to know of such a theorem ?
Omid Hatami
09.10.2006 12:37
In that time there were supposed to know P. Hall Theorem.
mikeynot
10.10.2006 01:49
Can explain part b) more? Thanks.
julien_santini
10.10.2006 05:09
Consider the bipartite graph whose bipartitions are $\{1,\dots,n\}$. Two vertices $x$ and $y$ (one in each bipartition resp.) are connected if and only if $\forall k, y \neq f_{k}(x)$. Now since $m\leq \frac{n}{2}$, Hall's condition is satisfied and you can find a perfect matching, i.e a permutation satisfying the required properties.