MathDB

Permutation

Source: Iranian National Olympiad (3rd Round) 2002

October 2, 2006

graph theorycombinatorics proposedcombinatorics

Problem Statement

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.

Back to Problems View on AoPS