China National Team Selection Test

Assume that, on the contrary, for some infinite set $A \subset \mathbb{Z}$, one cannot find a $(2p-2)$-element subset $B$ satisfying the problem conditions. Without loss of generality, assume that $A$ contains infinitely many positive integers; otherwise take $-A$ instead. Notice that the arithmetic mean of any $p$ distinct elements of $B$ must fall into the interval between the smallest and the largest elements of $B$. Thus, removing all elements smaller than some integer $N$ from $A$, the set is still a counterexample to the problem. In particular, we take $N = 1$ and thereby assume all elements of $A$ are positive. We may also add a constant integer to all elements of $A$ if necessary.

Lemma For any nonnegative integer $k$, there is at most one residue class modulo $p^k$ that contains infinitely many elements of $A$.

Proof of lemma Suppose the lemma is untrue and $k$ is the smallest nonnegative integer such that two residue classes modulo $p^k$ contain infinitely many elements of $A$, say with residues $r_k$ and $r'_k$. Then there exists a positive integer $N$ such that all elements of $A_{\ge N} := \{a \in A \mid a \ge N\}$ are congruent to $r_{k-1}$ modulo $p^{k-1}$. Furthermore, in $A_{\ge N}$, those congruent to $r_k$ and $r'_k$ modulo $p^k$ are both infinite. Take $p-1$ elements of $A_{\ge N}$ that are congruent to $r_k$, and the same number of elements congruent to $r'_k$ (mod $p^k$). Evidently, the arithmetic mean of any $p$ elements of $B$ is not congruent to $r_{k-1}$ modulo $p^{k-1}$. This contradicts the assumption, and the lemma is verified.

Return to the original problem. For nonnegative integer $k$, assume the only residue class modulo $p^k$ that contains infinitely many elements of $A$ is $r_k \pmod{p^k}$ ($0 \le r_k \le p^k - 1$); then $r_k \equiv r_{k-1} \pmod{p^{k-1}}$. Now we use induction to select a sequence $b_1, b_2, \dots$, of elements of $A$, and verify that $2p-2$ of them constitute the desired subset $B$. Denote $N_0 = 0$. Let $k_1$ be the smallest nonnegative integer such that some element $a_1 \in A$ satisfies $a_1 \not\equiv r_{k_1} \pmod{p^{k_1}}$. Then all elements of $A$ are congruent to $r_{k_1-1}$ modulo $p^{k_1-1}$. According to the lemma, there exists a positive integer $N_1$ such that all elements of $A_{\ge N_1} = \{a \in A \mid a \ge N_1\}$ are congruent to $r_{k_1}$ modulo $p^{k_1}$. Let $k_2$ be the smallest nonnegative integer such that some element $a_2 \in A$ satisfies $a_2 \not\equiv r_{k_2} \pmod{p^{k_2}}$. Analogously, all elements of $A_{\ge N_1}$ are congruent to $r_{k_2-1}$ modulo $p^{k_2-1}$. By the lemma, we can further find $N_2$ such that all elements of $A_{\ge N_2} = \{a \in A \mid a \ge N_2\}$ are congruent to $r_{k_2}$ modulo $p^{k_2}$, and so on. So, we obtain $N_1 < N_2 < \dots < N_{2p-2}$ satisfying $p^{k_1-1} \le (a_i - r_{k_i}) \le (1 \le i \le 2p-2)$.

For convenience, subtract $r_{k_{2p-2}}$ from every element of $A$ and from every $N_i$. Now $p^{k_i-1}a_i$ ($1 \le i \le 2p-2$), and every element of $A_{\ge N_i}$ is a multiple of $p^{k_{i+1}-1}$. Take the $(2p-2)$-element subset $B = \{b_1, b_2, \dots, b_{2p-2}\}$. For a $p$-element subset $\{b_{i_1}, \dots, b_{i_p}\}$ ($i_1 < i_2 < \dots < i_p$) of $B$, the arithmetic mean is divisible by $p^{k_{i_1}-2}$ and greater than $b_{i_1} \ge N_{i_1-1}$. Hence it does not belong to $A$. This completes the proof. $\square$

(by Feng Chenxu) We assert that for $1 \le t \le 2p-2$, one can always find a $t$-element subset $B$, such that for any $p$ distinct elements of $B$, their arithmetic mean does not belong to $A$. Apply induction to $t$: the assertion is trivially true when $t \le p-1$; assume the trueness when $|B| \le t-1$ and consider $t$.

For $1 \le i \le p$, let $B_i \subseteq A$ be the residue class $i$ modulo $p$, $A = \bigcup_{i=1}^p B_i$. If $A = B_j$ for some $1 \le j \le p$, then subtract $j$ from every element of $A$ and divide by $p$. This treatment will not affect the conclusion. Continue this process until at least two subsets $B_j, B_k$ are nonempty.

If two subsets $B_j$ and $B_k$ are infinite, take $p-1$ elements from each subset to constitute $B$. Clearly, the arithmetic mean of any $p$ distinct elements of $B$ is non-integral, $B$ satisfies the problem condition.

If only one subset, say $B_j$ is infinite, let $C = A \setminus B_j \ne \emptyset$. Let $D_+$ be the set of all elements of $B_j$ that are larger than $\max_{x \in C} x$; $D_-$ be the set of all elements of $B_j$ that are smaller than $\max_{x \in C} x$. Then $D_+ \cup D_-$ is infinite. Assume $D_+$ is infinite. By the induction hypothesis, one can find a satisfactory subset $B \subseteq D_+$, $|B| = t-1$. Since every number in $D_+$ is larger than every number in $A \setminus D_+$, we can infer that any $p$ distinct numbers in $B$ have an arithmetic mean larger than that in $A \setminus D_+$, and thus the mean is not in $A$. Take $x \in C$, and assume $x \in B_k, k \ne j$. For $x$ and $p-1$ elements of $B$, their sum is $S \equiv (p-1)j + k \equiv k - j \not\equiv 0 \pmod p$. Thus, the mean is not an integer, nor in $A$. It follows that $B \cup \{x\}$ satisfies the problem condition. This completes the induction and the proof of the assertion. $\square$