China Mathematical Olympiad

First, we define a function $f: X \to X$ with
$$\begin{aligned} f(3i - 2) &= 3i - 1, \quad f(3i - 1) = 3i, \quad f(3i) = 3i - 2, \\ i &= 1, 2, \dots, 30, \\ f(j) &= 100, \quad 91 \le j \le 99, \quad f(100) = 99.\end{aligned}$$
Obviously, $f$ satisfies condition (1). For any $A \subseteq X$ with $|A| = 40$, if
(i) there exists an integer $i$ with $1 \le i \le 30$ such that $|A \cap \{3i-2, 3i-1, 3i\}| \ge 2$, then $A \cap f(A) \ne \emptyset$; or
(ii) $91, 92, \dots, 100 \in A$, then $A \cap f(A) \ne \emptyset$ also holds.
In both cases, $f$ satisfies condition (2). If a subset $B$ of $X$ satisfies $f(B) \cup B = X$, then we have $|B \cap \{3i-2, 3i-1, 3i\}| \ge 2$ for all $1 \le i \le 30$, $\{91, 92, \dots, 98\} \subseteq B$, and $B \cap \{99, 100\} \ne \emptyset$. Hence, $|B| \ge 69$.

Next, we will show that, for any function $f$ satisfying the described conditions, there exists a subset $B \subseteq X$ with $|B| \le 69$ such that $f(B) \cup B = X$.

Among all the subsets $U \subseteq X$ with $U \cap f(U) = \emptyset$, choose one such that $|U|$ is maximal. If there are many $U \subseteq X$ with $|U|$ being maximal, choose one such that $|f(U)|$ is maximal. The existence of $U$ is guaranteed by condition (1). Let $V = f(U)$, $W = X \setminus (U \cup V)$. Note that $U, V, W$ are pairwise disjoint and $X = U \cup V \cup W$. From condition (2), $|U| \le 39$, $|V| \le 39$, $|W| \ge 22$.

We make the following assertions:
(i) $f(w) \in U$, for all $w \in W$. Otherwise, let $U' = U \cup \{w\}$, since $f(U) = V$, $f(w) \notin U$, $f(w) \ne w$, we have $U' \cap f(U') = \emptyset$. It is a contradiction to $|U|$ being maximal.
(ii) $f(w_1) \ne f(w_2)$ for all $w_1, w_2 \in W$, $w_1 \ne w_2$. Otherwise, let $u = f(w_1) = f(w_2)$ then by condition (1), $u \in U$. Let $U' = (U \setminus \{u\}) \cup \{w_1, w_2\}$, since $f(U') \subseteq V \cup \{u\}$, $U' \cap (V \cup \{u\}) = \emptyset$, we have $U' \cap f(U') = \emptyset$. It is a contradiction to $|U|$ being maximal.

Let $W = \{w_1, w_2, \dots, w_m\}$, $u_i = f(w_i)$, $1 \le i \le m$ then by (i) and (ii), $u_1, u_2, \dots, u_m$ are distinct elements of $U$.
(iii) $f(u_i) \ne f(u_j)$ for all $1 \le i < j \le m$. Otherwise, let $v = f(u_i) = f(u_j) \in V$, $U' = (U \setminus \{u_i\}) \cup \{w_i\}$, then $f(U') = V \cup \{u_i\}$, $U' \cap f(U') = \emptyset$. However, $|f(U')| > |f(U)|$. It is a contradiction to $|f(U)|$ being maximal.

Therefore, $f(u_1), f(u_2), \dots, f(u_m)$ are distinct elements of $V$. In particular, $|V| \ge |W|$. As $|U| \le 39$, we have $|V| + |W| \ge 61$ and $|V| \ge 31$. Let $B = U \cup W$, then $|B| \le 69$ and $f(B) \cup B \supseteq V \cup B = X$. Overall, the desired smallest integer $k$ is 69. $\square$