MathDB

A group of

n{}

(n>1)

people each visited

k{}

(k>1)

citites. Each person makes a list of these

k

cities in the order they want to visit them. A permutation

(a_1,a_2,\ldots,a_k)

is called

m-prefered

(m\in\mathbb{N})

, if for every

i=1,2,\ldots,k

there are at least

m

people that would prefer to visit the city

a_i

before the city

a_{i+1}

(a_{k+1}=a_1)

. Prove that there exists an m-prefered permutation if and only if

km\leq n(k-1)

Problem Statement