Maths Olympiad Prep

Library / /22 of 48

Number theory Difficulty 8.5 Shortlist Prove it China

Given a prime number pp and an infinite set AZA \subset \mathbb{Z}. Show that one can always find a subset BB of AA, BB contains 2p22p-2 elements, and for any pp distinct elements of BB, their arithmetic mean does not belong to AA.

(Contributed by Fu Yunhao)

Solutions — 2

Solution 1

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

Lemma For any nonnegative integer kk, there is at most one residue class modulo pkp^k that contains infinitely many elements of AA.

Proof of lemma Suppose the lemma is untrue and kk is the smallest nonnegative integer such that two residue classes modulo pkp^k contain infinitely many elements of AA, say with residues rkr_k and rkr'_k. Then there exists a positive integer NN such that all elements of AN:={aAaN}A_{\ge N} := \{a \in A \mid a \ge N\} are congruent to rk1r_{k-1} modulo pk1p^{k-1}. Furthermore, in ANA_{\ge N}, those congruent to rkr_k and rkr'_k modulo pkp^k are both infinite. Take p1p-1 elements of ANA_{\ge N} that are congruent to rkr_k, and the same number of elements congruent to rkr'_k (mod pkp^k). Evidently, the arithmetic mean of any pp elements of BB is not congruent to rk1r_{k-1} modulo pk1p^{k-1}. This contradicts the assumption, and the lemma is verified.

Return to the original problem. For nonnegative integer kk, assume the only residue class modulo pkp^k that contains infinitely many elements of AA is rk(modpk)r_k \pmod{p^k} (0rkpk10 \le r_k \le p^k - 1); then rkrk1(modpk1)r_k \equiv r_{k-1} \pmod{p^{k-1}}. Now we use induction to select a sequence b1,b2,b_1, b_2, \dots, of elements of AA, and verify that 2p22p-2 of them constitute the desired subset BB. Denote N0=0N_0 = 0. Let k1k_1 be the smallest nonnegative integer such that some element a1Aa_1 \in A satisfies a1≢rk1(modpk1)a_1 \not\equiv r_{k_1} \pmod{p^{k_1}}. Then all elements of AA are congruent to rk11r_{k_1-1} modulo pk11p^{k_1-1}. According to the lemma, there exists a positive integer N1N_1 such that all elements of AN1={aAaN1}A_{\ge N_1} = \{a \in A \mid a \ge N_1\} are congruent to rk1r_{k_1} modulo pk1p^{k_1}. Let k2k_2 be the smallest nonnegative integer such that some element a2Aa_2 \in A satisfies a2≢rk2(modpk2)a_2 \not\equiv r_{k_2} \pmod{p^{k_2}}. Analogously, all elements of AN1A_{\ge N_1} are congruent to rk21r_{k_2-1} modulo pk21p^{k_2-1}. By the lemma, we can further find N2N_2 such that all elements of AN2={aAaN2}A_{\ge N_2} = \{a \in A \mid a \ge N_2\} are congruent to rk2r_{k_2} modulo pk2p^{k_2}, and so on. So, we obtain N1<N2<<N2p2N_1 < N_2 < \dots < N_{2p-2} satisfying pk11(airki)(1i2p2)p^{k_1-1} \le (a_i - r_{k_i}) \le (1 \le i \le 2p-2).

For convenience, subtract rk2p2r_{k_{2p-2}} from every element of AA and from every NiN_i. Now pki1aip^{k_i-1}a_i (1i2p21 \le i \le 2p-2), and every element of ANiA_{\ge N_i} is a multiple of pki+11p^{k_{i+1}-1}. Take the (2p2)(2p-2)-element subset B={b1,b2,,b2p2}B = \{b_1, b_2, \dots, b_{2p-2}\}. For a pp-element subset {bi1,,bip}\{b_{i_1}, \dots, b_{i_p}\} (i1<i2<<ipi_1 < i_2 < \dots < i_p) of BB, the arithmetic mean is divisible by pki12p^{k_{i_1}-2} and greater than bi1Ni11b_{i_1} \ge N_{i_1-1}. Hence it does not belong to AA. This completes the proof. \square

Solution 2

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

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

If two subsets BjB_j and BkB_k are infinite, take p1p-1 elements from each subset to constitute BB. Clearly, the arithmetic mean of any pp distinct elements of BB is non-integral, BB satisfies the problem condition.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.