2023 Chinese IMO National Team Selection Test

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\},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=\varnothing$ 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$

---

Alternative solution.

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 \varnothing$ 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$