China Mathematical Olympiad

First, we define a function $f:X\to X$ with $$\begin{array}{rl}f(3i-2)& =3i-1,f(3i-1)=3i,f(3i)=3i-2,\\ i& =1,2,\dots ,30,\\ f(j)& =100,91\le j\le 99,f(100)=99.\end{array}$$ 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 \varnothing$; or (ii) $91,92,\dots ,100\in A$, then $A\cap f(A)\ne \varnothing$ 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 \varnothing$. 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)=\varnothing$, 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^{\prime }=U\cup \{w\}$, since $f(U)=V$, $f(w)\notin U$, $f(w)\ne w$, we have $U^{\prime }\cap f(U^{\prime })=\varnothing$. 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^{\prime }=(U\setminus \{u\})\cup \{w_1,w_2\}$, since $f(U^{\prime })\subseteq V\cup \{u\}$, $U^{\prime }\cap (V\cup \{u\})=\varnothing$, we have $U^{\prime }\cap f(U^{\prime })=\varnothing$. 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^{\prime }=(U\setminus \{u_i\})\cup \{w_i\}$, then $f(U^{\prime })=V\cup \{u_i\}$, $U^{\prime }\cap f(U^{\prime })=\varnothing$. However, $|f(U^{\prime })|>|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$