2014 CMO 第 4 题

Let $f:X\rightarrow X$ , where $X=\{1,2,\ldots ,100\}$ , be a function satisfying:

1) $f(x)\neq x$ for all $x=1,2,\ldots,100$ ;

2) for any subset $A$ of $X$ such that $|A|=40$ , we have $A\cap f(A)\neq\emptyset$ .

Find the minimum $k$ such that for any such function $f$ , there exist a subset $B$ of $X$ , where $|B|=k$ , such that $B\cup f(B)=X$ .

设 $f:X\rightarrow X$ ，其中 $X=\{1,2,\ldots ,100\}$ 是满足以下条件的函数：

1) $f(x)\neq x$ 对于所有 $x=1,2,\ldots,100$ ；

2) 对于 $X$ 的任何子集 $A$ ，使得 $|A|=40$ ，我们有 $A\cap f(A)\neq\emptyset$ 。

找到最小 $k$ ，使得对于任何此类函数 $f$ ，都存在 $X$ 的子集 $B$ ，其中 $|B|=k$ ，使得 $B\cup f(B)=X$ 。