Given a prime number and an infinite set . Show that one can always find a subset of , contains elements, and for any distinct elements of , their arithmetic mean does not belong to .
(Contributed by Fu Yunhao)
Given a prime number and an infinite set . Show that one can always find a subset of , contains elements, and for any distinct elements of , their arithmetic mean does not belong to .
(Contributed by Fu Yunhao)
Assume that, on the contrary, for some infinite set , one cannot find a -element subset satisfying the problem conditions. Without loss of generality, assume that contains infinitely many positive integers; otherwise take instead. Notice that the arithmetic mean of any distinct elements of must fall into the interval between the smallest and the largest elements of . Thus, removing all elements smaller than some integer from , the set is still a counterexample to the problem. In particular, we take and thereby assume all elements of are positive. We may also add a constant integer to all elements of if necessary.
Lemma For any nonnegative integer , there is at most one residue class modulo that contains infinitely many elements of .
Proof of lemma Suppose the lemma is untrue and is the smallest nonnegative integer such that two residue classes modulo contain infinitely many elements of , say with residues and . Then there exists a positive integer such that all elements of are congruent to modulo . Furthermore, in , those congruent to and modulo are both infinite. Take elements of that are congruent to , and the same number of elements congruent to (mod ). Evidently, the arithmetic mean of any elements of is not congruent to modulo . This contradicts the assumption, and the lemma is verified.
Return to the original problem. For nonnegative integer , assume the only residue class modulo that contains infinitely many elements of is (); then . Now we use induction to select a sequence , of elements of , and verify that of them constitute the desired subset . Denote . Let be the smallest nonnegative integer such that some element satisfies . Then all elements of are congruent to modulo . According to the lemma, there exists a positive integer such that all elements of are congruent to modulo . Let be the smallest nonnegative integer such that some element satisfies . Analogously, all elements of are congruent to modulo . By the lemma, we can further find such that all elements of are congruent to modulo , and so on. So, we obtain satisfying .
For convenience, subtract from every element of and from every . Now (), and every element of is a multiple of . Take the -element subset . For a -element subset () of , the arithmetic mean is divisible by and greater than . Hence it does not belong to . This completes the proof.
(by Feng Chenxu) We assert that for , one can always find a -element subset , such that for any distinct elements of , their arithmetic mean does not belong to . Apply induction to : the assertion is trivially true when ; assume the trueness when and consider .
For , let be the residue class modulo , . If for some , then subtract from every element of and divide by . This treatment will not affect the conclusion. Continue this process until at least two subsets are nonempty.
If two subsets and are infinite, take elements from each subset to constitute . Clearly, the arithmetic mean of any distinct elements of is non-integral, satisfies the problem condition.
If only one subset, say is infinite, let . Let be the set of all elements of that are larger than ; be the set of all elements of that are smaller than . Then is infinite. Assume is infinite. By the induction hypothesis, one can find a satisfactory subset , . Since every number in is larger than every number in , we can infer that any distinct numbers in have an arithmetic mean larger than that in , and thus the mean is not in . Take , and assume . For and elements of , their sum is . Thus, the mean is not an integer, nor in . It follows that satisfies the problem condition. This completes the induction and the proof of the assertion.