Problem

Source: 2023 Taiwan Round 1 Mock Exam P4

Tags: combinatorics, Permutation cycles, Taiwan, function



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