MathDB
Problems
Contests
National and Regional Contests
Moldova Contests
Moldova Team Selection Test
2001 Moldova Team Selection Test
8
8
Part of
2001 Moldova Team Selection Test
Problems
(1)
Prove that there exists an m-prefered permutation if and only if $km\leq m(k-1)$
Source: Moldova TST 2001
8/6/2023
A group of
n
n{}
n
(
n
>
1
)
(n>1)
(
n
>
1
)
people each visited
k
k{}
k
(
k
>
1
)
(k>1)
(
k
>
1
)
citites. Each person makes a list of these
k
k
k
cities in the order they want to visit them. A permutation
(
a
1
,
a
2
,
…
,
a
k
)
(a_1,a_2,\ldots,a_k)
(
a
1
,
a
2
,
…
,
a
k
)
is called
m
−
p
r
e
f
e
r
e
d
m-prefered
m
−
p
re
f
ere
d
(
m
∈
N
)
(m\in\mathbb{N})
(
m
∈
N
)
, if for every
i
=
1
,
2
,
…
,
k
i=1,2,\ldots,k
i
=
1
,
2
,
…
,
k
there are at least
m
m
m
people that would prefer to visit the city
a
i
a_i
a
i
before the city
a
i
+
1
a_{i+1}
a
i
+
1
,
(
a
k
+
1
=
a
1
)
(a_{k+1}=a_1)
(
a
k
+
1
=
a
1
)
. Prove that there exists an m-prefered permutation if and only if
k
m
≤
n
(
k
−
1
)
km\leq n(k-1)
km
≤
n
(
k
−
1
)
.
combinatorics