MathDB

Let

k

be a positive integer, and set

n=2^k

N=\{1, 2, \cdots, n\}

. For any bijective function

f:N\rightarrow N

, if a set

A\subset N

contains an element

a\in A

such that

\{a, f(a), f(f(a)), \cdots\} = A

, then we call

A

as a cycle of

f

. Prove that: among all bijective functions

f:N\rightarrow N

, at least

\frac{n!}{2}

of them have number of cycles less than or equal to

2k-1

. Note: A function is bijective if and only if it is injective and surjective; in other words, it is 1-1 and onto.
Proposed by CSJL

Problem Statement