设集合 $X=\{1,2, \cdots, 100\}$，函数 $f : X \rightarrow X$ 同时满足
（1）对任意的 $x\in X$，均有 $f(x)\ne x$；
（2）对集合 $X$ 的任意一个 $40$ 元子集 $A$，均有 $A\bigcap f(A)\ne \varnothing$．
求最小的正整数 $k$，使得对任意满足上述条件的函数 $f$，均存在集合 $X$ 的 $k$ 元子集 $B$，使得 $B \cup f(B)=X$．
注：对集合 $X$ 的子集 $T$，定义 $f(T)=\{f(t) | t \in T\}$．
（1）对任意的 $x\in X$，均有 $f(x)\ne x$；
（2）对集合 $X$ 的任意一个 $40$ 元子集 $A$，均有 $A\bigcap f(A)\ne \varnothing$．
求最小的正整数 $k$，使得对任意满足上述条件的函数 $f$，均存在集合 $X$ 的 $k$ 元子集 $B$，使得 $B \cup f(B)=X$．
注：对集合 $X$ 的子集 $T$，定义 $f(T)=\{f(t) | t \in T\}$．
【难度】
【出处】
2013第29届CMO试题
【标注】
【答案】
略
【解析】
首先考虑如下定义的 $f : X \rightarrow X$：
对于 $i=1,2, \cdots, 30, j=91,92, \cdots, 99$ 定义 $f(3 i-2)=3 i-1, f(3 i-1)=3 i$，$f(3 i)=3 i-2, f(j)=100, f(100)=99$
显然，函数 $f $ 满足条件（1）．
对任意集合 $X$ 的 $40$ 元子集 $A$，要么存在整数 $i(1 \leqslant i \leqslant 30)$，使得 $|A \bigcap| 3 i-2,3 i-1,3 i | \geqslant 2$．
此时，$A \bigcap f(A) \neq \varnothing$，要么 $91,92, \cdots, 100 \in A$，此时，也有 $A \cap f(A) \neq \varnothing$，即函数 $f$ 也满足条件（2）．
若集合 $X$ 的子集 $B$ 满足 $f(B) \bigcup B=X$，则 $|B \bigcap| 3 i-2,3 i-1,3 i| | \geqslant 2(1 \leqslant i \leqslant 30)$．
且 $91,92, \cdots, 98 \in B, 99,100$ 中至少有一个属于集合 $B$，于是，$|B| \geqslant 69$．
只需证明：对任意满足题目条件的函数 $f$，总存在一个不超过 $69$ 元的子算 $ B$，使得 $f(B) \bigcup B=X$．
考虑所有满足 $U\bigcap f(u)=\varnothing$ 的子集 $U \subseteq X$（由条件（l）知 $\{x\} \cap f(|x|)=\varnothing$，故这样的子集 $U$ 存在）．在这些子集中，取一个子集 $U$ 使得 $|U|$ 最大，如有多个子集 $U$ 满足要求．再在其中选取使 $|f(U)|$ 最大的子集 $U$．
设 $V=f(U), W=X \backslash(U \cup V)$，$U,V,W$ 丙两不相交，且并集为 $X$．
由条件（2）知 $|U|\leqslant 39$．
从而，$|V|\leqslant 39, | W|\geqslant 22$．
（i）对任意的 $w \in W$，必有 $f(w) \in U$．
否则，设 $U^{\prime}=U \cup\{w \}$．
由于 $f(U)=V, f(w) \notin U$，且 $f(w)\ne w$，故 $U^{\prime} \cap f\left(U^{\prime}\right)=\varnothing$，与 $|U|$ 的最大性矛盾．
（ii）若 $w_{1}, w_{2} \in W\left(w_1\neq w_{2}\right)$，则 $f\left(w_{1}\right) \neq f\left(w_{2}\right)$．
否则，设 $u=f\left(w_{1}\right)=f\left(w_{2}\right)$．
由结论（i）知 $u\in U$．设 $U^{\prime}=(U \backslash\{u\}) \bigcup\left\{w_{1}, w_{2}\right\}$．
由 $f\left(U^{\prime}\right) \subseteq V \cup\{u\}, U^{\prime} \cap\left(V \cup \{u\}\right)=\varnothing$，故 $U^{\prime} \cap f\left(U^{\prime}\right)=\varnothing$，与 $|U|$ 的最大性矛盾．
记 $W=\left\{w_{1}, w_{2}, \cdots, w_{m}\right\}$，设 $u_{i}=f\left(w_{i}\right)(1 \leqslant i \leqslant m)$．
由（i）、（ii）知 $u_{1}, u_{2}, \cdots, u_{m}$ 是子集 $U$ 中两两不同的元素．
（iii）对 $1 \leqslant i<j \leqslant m$，有 $f\left(u_{i}\right) \neq f\left(u_{j}\right)$．
否则，设 $v=f\left(u_{i}\right)=f\left(u_{j}\right) \in V$．
考虑 $U^{\prime}=\left(U \backslash \{ u_{i}\right\} ) \cup\left\{w_{i}\right\}$．则 $f\left(U^{\prime}\right)=V \cup\left\{u_{i} \}, U^{\prime} \cap f\left({U}^{\prime}\right)=\varnothing\right.$．
但 $\left|f\left(U^{\prime}\right)\right|>\left|f(U)\right|$，与 $| f(U) |$ 的最大性矛盾．
因此，$f\left(u_{1}\right), f\left(u_{2}\right), \cdots, f\left(u_{m}\right)$ 是子集 $V$ 中两两不同的元素．
故 $|V| \geqslant|W|$．
由于 $|U| \leqslant 39$，故 $|V|+|W| \geqslant 61$．
于是，$|V| \geqslant 31$
令 $B = U\bigcup W$．则 $|B| \leqslant 69$，且 $f(B) \cup B \supseteq V \cup B=X$．
综上，所求最小的正整数 $k$ 为 $69$．
对于 $i=1,2, \cdots, 30, j=91,92, \cdots, 99$ 定义 $f(3 i-2)=3 i-1, f(3 i-1)=3 i$，$f(3 i)=3 i-2, f(j)=100, f(100)=99$
显然，函数 $f $ 满足条件（1）．
对任意集合 $X$ 的 $40$ 元子集 $A$，要么存在整数 $i(1 \leqslant i \leqslant 30)$，使得 $|A \bigcap| 3 i-2,3 i-1,3 i | \geqslant 2$．
此时，$A \bigcap f(A) \neq \varnothing$，要么 $91,92, \cdots, 100 \in A$，此时，也有 $A \cap f(A) \neq \varnothing$，即函数 $f$ 也满足条件（2）．
若集合 $X$ 的子集 $B$ 满足 $f(B) \bigcup B=X$，则 $|B \bigcap| 3 i-2,3 i-1,3 i| | \geqslant 2(1 \leqslant i \leqslant 30)$．
且 $91,92, \cdots, 98 \in B, 99,100$ 中至少有一个属于集合 $B$，于是，$|B| \geqslant 69$．
只需证明：对任意满足题目条件的函数 $f$，总存在一个不超过 $69$ 元的子算 $ B$，使得 $f(B) \bigcup B=X$．
考虑所有满足 $U\bigcap f(u)=\varnothing$ 的子集 $U \subseteq X$（由条件（l）知 $\{x\} \cap f(|x|)=\varnothing$，故这样的子集 $U$ 存在）．在这些子集中，取一个子集 $U$ 使得 $|U|$ 最大，如有多个子集 $U$ 满足要求．再在其中选取使 $|f(U)|$ 最大的子集 $U$．
设 $V=f(U), W=X \backslash(U \cup V)$，$U,V,W$ 丙两不相交，且并集为 $X$．
由条件（2）知 $|U|\leqslant 39$．
从而，$|V|\leqslant 39, | W|\geqslant 22$．
（i）对任意的 $w \in W$，必有 $f(w) \in U$．
否则，设 $U^{\prime}=U \cup\{w \}$．
由于 $f(U)=V, f(w) \notin U$，且 $f(w)\ne w$，故 $U^{\prime} \cap f\left(U^{\prime}\right)=\varnothing$，与 $|U|$ 的最大性矛盾．
（ii）若 $w_{1}, w_{2} \in W\left(w_1\neq w_{2}\right)$，则 $f\left(w_{1}\right) \neq f\left(w_{2}\right)$．
否则，设 $u=f\left(w_{1}\right)=f\left(w_{2}\right)$．
由结论（i）知 $u\in U$．设 $U^{\prime}=(U \backslash\{u\}) \bigcup\left\{w_{1}, w_{2}\right\}$．
由 $f\left(U^{\prime}\right) \subseteq V \cup\{u\}, U^{\prime} \cap\left(V \cup \{u\}\right)=\varnothing$，故 $U^{\prime} \cap f\left(U^{\prime}\right)=\varnothing$，与 $|U|$ 的最大性矛盾．
记 $W=\left\{w_{1}, w_{2}, \cdots, w_{m}\right\}$，设 $u_{i}=f\left(w_{i}\right)(1 \leqslant i \leqslant m)$．
由（i）、（ii）知 $u_{1}, u_{2}, \cdots, u_{m}$ 是子集 $U$ 中两两不同的元素．
（iii）对 $1 \leqslant i<j \leqslant m$，有 $f\left(u_{i}\right) \neq f\left(u_{j}\right)$．
否则，设 $v=f\left(u_{i}\right)=f\left(u_{j}\right) \in V$．
考虑 $U^{\prime}=\left(U \backslash \{ u_{i}\right\} ) \cup\left\{w_{i}\right\}$．则 $f\left(U^{\prime}\right)=V \cup\left\{u_{i} \}, U^{\prime} \cap f\left({U}^{\prime}\right)=\varnothing\right.$．
但 $\left|f\left(U^{\prime}\right)\right|>\left|f(U)\right|$，与 $| f(U) |$ 的最大性矛盾．
因此，$f\left(u_{1}\right), f\left(u_{2}\right), \cdots, f\left(u_{m}\right)$ 是子集 $V$ 中两两不同的元素．
故 $|V| \geqslant|W|$．
由于 $|U| \leqslant 39$，故 $|V|+|W| \geqslant 61$．
于是，$|V| \geqslant 31$
令 $B = U\bigcup W$．则 $|B| \leqslant 69$，且 $f(B) \cup B \supseteq V \cup B=X$．
综上，所求最小的正整数 $k$ 为 $69$．
答案
解析
备注
