Let $p$ be a prime, $A$ is an infinite set of integers. Prove that there is a subset $B$ of $A$ with $2p-2$ elements, such that the arithmetic mean of any pairwise distinct $p$ elements in $B$ does not belong to $A$.
Problem
Source: 2022 China TST, Test 1, P2 (posting for better LaTeX)
Tags: combinatorics, number theory, prime numbers
24.03.2022 13:42
Here https://artofproblemsolving.com/community/u800085h2807854p24762139
24.03.2022 16:13
After given a hint from my classmate, I got a solution as follows.
24.03.2022 19:08
Almost trivial for China TST. I headsolved it. Case 1: there exists 0<a<b<p such that at least p-1 elements of A are a mod p and p-1 elements are b mod p. In this case, taking B to be p-1 A mod p's and b mod p's works because the arithmetic mean of any p elements in B is not an integer; I need to take x a mod p's and p-x b mod p's, so p|x(a-b) but x is in [1,p-1] Therefore, translating A to be A-r where r is the only number in [0,p) such that infinitely many elements in A are r mod p, we can see finitely many elements are not divisible by p in A-r. This means that these elements have a maximum, so we can take 2p-2 multiples of p greater than any of the finitely many elements not divisible by p. This means I can safely ignore the non-multiples of p and replace this set by A/p. Since this process is finite, we are done.
25.03.2022 02:56
@above why is the process finite?
25.03.2022 05:39
Oh so you are saying my solution breaks when there are, say $p-1$ elements that are "mainstream" mod $p^k$ but not "mainstream" mod $p^{k+1}$ for every single $k$ (because we've shown that for all but one residue $r$ mod $p^a$, there are finitely many elements in $A$ that is not $r$ mod $p^a$.) Interesting. Maybe my understanding of infinities is incorrect.
25.03.2022 09:48
You can fix this by just picking one of the elements which are not multiples of $p$ and then pick $2p-1$ multiples of $p$ and so on, this way the process is always going to end (actually there might be no non-multiples of $p$ at some point but if you keep dividing you'll end up getting one of the elements with minimal $\nu_p$). What you said just doesm't work if say the set you start with is exactly the powers of $p$.
05.04.2022 05:44
05.04.2022 17:49
Love_zim wrote: After given a hint from my classmate, I got a solution as follows.
How does $B$ work?
08.07.2022 08:27
Consider the following process: I start with a copy $A_1$ of $A$. Then, on the $i$th iteration of the process: If $A_i$ contains at least $p-1$ of any two residues $x,y$ mod $p$, then choose $p-1$ numbers from each residue to form a valid subset $B_i$ of $A_i$. This ends the process. Else, only finitely many elements belong to all but one residue mod $p$. shift the set so that infinitely many elements are multiples of $p$; then, divide every element by the GCD of everything if it isn't 1, then ignore all elements smaller than or equal to the greatest non-multiple of $p$, and divide remaining elements by $p$ to arrive at $A_{i+1}$. If this process terminates, then we can reverse-engineer $B$ from our choice of $B_i$. Else, suppose that the process does not terminate after $p-1$ steps. Then, after appropriate shifting, for some positive integer $n\ge p-1$, only finitely many elements in $A$ are not divisible by $p^n$. Let the set of these elements be $C$; we know that $|C|\ge p-1$, and moreover $|\{\nu_p(c)|c\in C\}|\ge p-1$ by considering the nonzero residues "left behind" at each iteration of the process. We are done now by picking $p-1$ arbitrary elements of $C$ with distinct $\nu_p$, and $p-1$ elements of $A\setminus C$ greater than $p$ times the supremum of $C$.
08.07.2022 21:13
Nice problem! We will denote by $\mathbb{N}$ the set of positive integers. In which follows, we will assume for simplicity that $A \cap \mathbb{N}$ is infinite, since the same argues would work anyways. It is sufficient to find a subset $B \subseteq { (A\cap\mathbb{N}) }$ and we will replace $A$ by $A\cap \mathbb{N}$. Suppose for contradiction problem statement is false, that is, among any $2p-2$ elements in $A,$ exists $p$ with arithmetic mean in $A.$ Claim 1: For all $\alpha \in \mathbb{N}$ exists some constant $N_{\alpha} \in \mathbb{N}$ and some remainder $0<k_{\alpha} < p^{\alpha}$ such that $a \equiv k_{\alpha} \pmod {p^{\alpha}}, \forall a \in A, a\ge N_{\alpha}.$ Furthermore, the $N_{\alpha}'s$ are increaisng and $k_{\alpha+1} \equiv k_{\alpha} \pmod {p^{\alpha}}.$
Now we will assume problem statement is false and get a contradiciton. Pick from $A,$ positve integers $l_{(1,1)}<l_{(1,2)}\dots <l_{(1,p-1)} < l_{(2,1)} < \dots < l_{(p,p-1)}~(*)$ and consider the sets $L_a := \{l_{(a,i)} : 1\le i \le p-1 \}$ for every $1\le a \le p.$ Now, choose some number $\alpha$ sufficiently large, and consider an set $M \subseteq A$ with $p-1$ elements and such that $M$ does not contain one of the numbers selected above and $m> pN_{\alpha}, \forall m \in M ~(**).$ Consider for every $1 \le a \le p,$ the set $L_a \cup M.$ Then, if we assume for contradiction that problem statement is false, there will be two sets $L'_a \subseteq L_a$ and $M' \subseteq M,$ such that $|L'_a| + |M'| = p$ and $$ \frac{\sum_{i \in L'_a} i + \sum_{j \in M'} j}{p} \in A.$$Note that $|L'_a|,|M'| \ge 1,$ beacause both sets has at most $p-1$ terms and the some of its cardinalities is $p.$ Then by $(**),$ it follows that the number above is at least $N_{\alpha}$. Then, $$ \sum_{i \in L'_a} i + \sum_{j \in M'} j \equiv pk_{\alpha} \pmod {p^{\alpha +1}}$$Again by $(*),$ it follows that the elements of $M$ are all equivalent to $ k_{\alpha} \pmod {p^{\alpha}}.$ Hence, looking at the above equivalence modulo $p^{\alpha},$ we will have, $$ \sum_{i \in L'_a} i \equiv (p-|M|)k_{\alpha} \pmod {p^{\alpha}}.$$That is, every set $L_a$ has a non-empty subset $L'_a$ whose some of the elements is equivalent to $r_ak_{\alpha} \pmod {p^{\alpha}}$ for some $1\le r_a \le p-1.$ But since there are $p$ of these sets, it follows by pigeonhole that $$\sum_{i \in L'_a} i \equiv \sum_{i \in L'_b} i \pmod {p^{\alpha}}$$for some $a\ne b.$ But, by the choice of the numbers (we have marked this as $(*)$) we will have by an huge bound $$ 0< \left|\sum_{i \in L'_a} i - \sum_{i \in L'_b} i\right| < l_{(1,1)}+l_{(1,2)}\dots +l_{(1,p-1)} + l_{(2,1)} + \dots + l_{(p,p-1)}$$which is a contradiction since $\alpha$ is any positive integer, and we could choose $\alpha$ such that $p^{\alpha}$ exceeds the right hand side of above. So we are done.
12.10.2022 11:57
Solution : Consider the following : Let's start with a copy $A_1$ of $A$ and then, on the $i$th iteration of the process: If $A_i$ contains at least $p-1$ of any two residues $x,y$ mod $p$, then choose $p-1$ numbers from each residue to form a valid subset $X_i$ of $A_i$. This ends the process. Else, only finitely many elements belong to all but one residue mod $p$. shift the set so that infinitely many elements are multiples of $p$; then, divide every element by the GCD of everything if it isn't 1, then ignore all elements smaller than or equal to the greatest non-multiple of $p$, and divide remaining elements by $p$ to arrive at $A_{i+1}$. If this process terminates, then we can reverse-engineer $X$ from our choice of $X_i$. Else, suppose that the process does not terminate after $p-1$ steps. Then, after appropriate shifting, for some positive integer $n\ge p-1$, only finitely many elements in $A$ are not divisible by $p^n$. Let the set of these elements be $M$; we know that $|M|\ge p-1$, and moreover $|\{\nu_p(m)|m\in M\}|\ge p-1$ by considering the nonzero residues "left behind" at each iteration of the process. Now let's pick $p-1$ arbitrary elements of $M$ with distinct $\nu_p$, and $p-1$ elements of $A\setminus M$ greater than $p$ times the supremum of $M$. Now we are done.(Also done by Mathleticguyy)
28.02.2024 12:59
We uploaded our solution https://calimath.org/pdf/ChinaTST2022-1-2.pdf on youtube https://youtu.be/fnr7Zno77Ks.
02.04.2024 05:45
We use induction on $|B|$, starting with the proof of our base case $|B|=p$ using contradiction. Considering the elements $\{a_1, \ldots,a_{p-1},u,v\}$ of $A$, we require \[\frac{a_1+\ldots+a_{p-1}+u}{p} - \frac{a_1+\ldots+a_{p-1}+v}{p} = \frac{u-v}{p} \in \mathbb{Z}\]for any $u,v \in A$. Thus all elements of $A$ are equivalent to some residue $k \pmod p$, so transforming each element $a \in A$ into $\tfrac{a-k}{p}$, we find a new set of integers with the same assumed property. However, we clearly can't continue this process indefinitely, contradiction. Suppose $|B|=q-1$ satisfies the hypothesis, and again assume by contradiction that $|B|=q$ does not hold. Note there exists a residue which appears infinitely in $A$, and we must have at most $p-2$ for each other residue, or else we can construct $B$ to not have $p$ elements which average to an integer. Considering extremes, take the largest element $m$ which is not congruent to the infinitely appearing residue and add it to our original subset $B$ with $q-1$ elements to get a desired set, contradiction. Thus the only case left is when all elements are congruent modulo, from which we get our final contradiction by infinite descent as described in our base case. $\blacksquare$
02.07.2024 20:15
If there are two residues modulo $p$ that each contain at least $p - 1$ numbers in $A$ then we can pick $p - 1$ numbers from each residue. The mean of any collection of $p$ numbers in $B$ at this point is clearly not an integer(unless $p = 2$ but this case is trivial so we can ignore it) so it is not in $A$. Now this means that there is a residue with infinitely many numbers and the rest of the residues have finitely many numbers. We can shift the residues so that infinitely many residues are divisible by $p$. Then this implies that finitely many residues are not divisible by $p$, so we take the maximum $R$ of these numbers. Then we can choose $2p - 1$ numbers that are greater than $R$. Then we can choose $R$ as the last number and the resulting mean will not be an integer, so we are done. Notice that this process is reversible and the mean from the original state will also not be an integer.
03.12.2024 05:52
If $p=2$, we can simply select the two smallest elements of $A$, and their average will not be in $A$. Henceforth assume $p \neq 2$. Note that if there are at least $p+1$ of any two residues modulo $p$, then we can take $p+1$ of each and the resulting set does not have an integer average. Hence, there must only be one residue that with an infinite amount of numbers with that residue. Let this infinite set be $X$, and shift the residues so that all the elements of $X$ are divisible by $p$. Then, denote the largest of the remaining elements as $m$. There are any infinite amount of elements in $X$ that are greater than $m$, so we ignore the ones that aren't and form a new set $Y$ with all of our desired elements from $X$. Now, we take $m$ and then $2p-3$ elements from $Y$. Obviously, if the subset contains $m$, the average will not be an integer. Moreover, if it doesn't contain $m$, the average must be in $Y$. Thus, if we divide $p$ from all the elements in $Y$, we have reduced $|B|$ from $2p-2$ to $2p-3$. We use similar logic to reduce to $|B| = p$, where we will FTSOC suppose that the arithmetic mean of any $p$ elements is in $A$. There is obviously some residue with infinite elements in it; suppose that residue is $a$. If there were any other element in $A$ with a different residue modulo $p$, we can take $p-1$ elements with residue $a$ and the element with the different residue to get a contradiction. However, if all of the elements in $A$ have the same residue, we can apply the map $x \mapsto \tfrac{x-a}{p}$ to get another set of integers satisfying the same conditions. Then, infinite descent yields a contradiction. $\blacksquare$