Chinese IMO National Team Selection Test, 2023

For a positive integer $n$, a non-empty set of integers $A$ is called an “order $n$ strong beautiful set” if $A \subset \{0, 1, \dots, 3^n - 1\}$ and for any $a \in A$ and $1 \le k \le n$, we have $\#\{b \in A \mid \lfloor 3^{-k}b \rfloor = \lfloor 3^{-k}a \rfloor \} = 2^k$. It is clear that a 2023-order strong beautiful set is a beautiful set. We will prove the following proposition by induction: For any positive integer $n$, if a set of integers $S$ has a non-empty intersection with every order $n$ strong beautiful set, then $S$ contains an order $n$ strong beautiful set. Taking $n = 2023$ in this proposition will imply the original problem.

When $n = 1$, the order 1 strong beautiful sets are the binary subsets of $\{0, 1, 2\}$. It is easy to see that the proposition holds in this case. Suppose the proposition holds for $n = m$. We will prove that it also holds for $n = m + 1$. First, note that if $A_1$ and $A_2$ are $m$-order strong beautiful sets and $\{i_1, i_2\}$ is a binary subset of $\{0, 1, 2\}$, then the set
$$\{a + i_1 3^m \mid a \in A_1\} \cup \{a + i_2 3^m \mid a \in A_2\}$$
is an $(m+1)$-order strong beautiful set. Let $S$ be a set of integers that has a non-empty intersection with every $(m+1)$-order strong beautiful set. Consider the sets
$$S_i = \{0 \le a < 3^m \mid a + i 3^m \in S\}, \quad i = 0, 1, 2.$$
We claim that there exists a binary subset $\{i_1, i_2\}$ of $\{0, 1, 2\}$ such that both $S_{i_1}$ and $S_{i_2}$ have a non-empty intersection with every $m$-order strong beautiful set. If not, then there exist a binary subset $\{j_1, j_2\}$ of $\{0, 1, 2\}$ and $m$-order strong beautiful sets $B_1$ and $B_2$ such that $S_{j_1} \cap B_2 = \emptyset$ for $s = 1, 2$. As a result, the $(m+1)$-order strong beautiful set $\{a + j_1 3^m \mid a \in B_1\} \cup \{a + j_2 3^m \mid a \in B_2\}$ does not intersect with $S$, which is a contradiction. By the induction hypothesis, $S_{i_1}$ contains an $m$-order strong beautiful set $A_1$, and $S_{i_2}$ contains an $m$-order strong beautiful set $A_2$. Therefore, $S$ contains an $(m+1)$-order strong beautiful set $\{a + i_1 3^m \mid a \in A_1\} \cup \{a + i_2 3^m \mid a \in A_2\}$. $\square$

For a positive integer $n$ and an integer $m$, a non-empty set of integers $A$ is called an “$n$-th order $m$-basic beautiful set” if $A \subset \{3^m m, 3^m m + 1, \dots, 3^n(m+1) - 1\}$ and for any $a \in A$ and $1 \le k \le n$, we have $\#\{b \in A \mid \lfloor 3^{-k}b \rfloor = \lfloor 3^{-k}a \rfloor \} = 2^k$. It is clear that for any integer $m$, any 2023-th order $m$-basic beautiful set is a beautiful set. We will prove the proposition $P_n$ by induction: for any set of integers $S$ and any integer $m$, there exists an $n$-th order $m$-basic beautiful set $A$ such that either $A \subset S$ or $A \subset \bar{S}$ (where $\bar{S} = \mathbb{Z} \setminus S$ denotes the complement of $S$). If $P_{2023}$ is true, then the set $S$ or its complement $\bar{S}$ contains a beautiful set. Since $S \cap A \ne \emptyset$ by assumption, it follows that $A \subset S$, and the original problem is solved.

When $n = 1$, by the pigeonhole principle, the set $\{3m, 3m + 1, 3m + 2\}$ contains at least two elements $a$ and $b$ that belong to either $S$ or $\bar{S}$. Then $A = \{a, b\}$ is a 1-st order $m$-basic beautiful set, and $A \subset S$ or $A \subset \bar{S}$. Thus, the proposition $P_1$ holds. Assume that the proposition $P_n$ holds. We will prove that the proposition $P_{n+1}$ also holds. For any set of integers $S$ and any integer $m$, by the induction hypothesis, there exists an $n$-th order $3m$-basic beautiful set $A_1 \subset [3^n \cdot 3m, 3^n(3m+1))$, an $n$-th order $(3m+1)$-basic beautiful set $A_2 \subset [3^n(3m+1), 3^n(3m+2))$, and an $n$-th order $(3m+2)$-basic beautiful set $A_3 \subset [3^n(3m+2), 3^n(3m+3))$, which satisfy that for any $i \in \{1, 2, 3\}$, either $A_i \subset S$ or $A_i \subset \bar{S}$. According to the pigeonhole principle, at least two sets among $A_1, A_2, A_3$, denoted as $A_{i_1}$ and $A_{i_2}$ ($1 \le i_1 < i_2 \le 3$), are both contained in $S$ or $\bar{S}$. Define $A = A_{i_1} \cup A_{i_2}$, it can be easily verified that $A$ is an $(n+1)$-th order $m$-basic beautiful set, and either $A \subset S$ or $A \subset \bar{S}$. Therefore, the proposition $P_{n+1}$ holds. $\square$