MathDB

Fix positive integers

n

and

k

such that

2 \le k \le n

and a set

M

consisting of

n

fruits. A permutation is a sequence

x=(x_1,x_2,\ldots,x_n)

such that

\{x_1,\ldots,x_n\}=M

. Ivan prefers some (at least one) of these permutations. He realized that for every preferred permutation

x

, there exist

k

indices

i_1 < i_2 < \ldots < i_k

with the following property: for every

1 \le j < k

, if he swaps

x_{i_j}

and

x_{i_{j+1}}

, he obtains another preferred permutation. \\ Prove that he prefers at least

k!

permutations.

Problem Statement