We call a set of positive integers suitable if none of its elements is coprime to the sum of all elements of that set. Given a real number $\varepsilon \in (0,1)$, prove that, for all large enough positive integers $N$, there exists a suitable set of size at least $\varepsilon N$, each element of which is at most $N$.
Problem
Source: RMM Extralist 2021 N2
Tags: number theory, primes, Combinatorial Number Theory, RMM Shortlist
19.09.2023 15:45
Because $\prod_{p\text{ prime}} \frac{p-1}{p}=0$ we can pick some large $M$ such that $\prod_{p<M\text{ prime}} \frac{p-1}{p} \leq \frac{1-\varepsilon}{3}$. For all sufficiently large $N$, there are then at least $\frac{1+\varepsilon}{2}N$ elements in $\{1,\ldots,N\}$ which are divisible by some prime less than $M$. Place all of these elements into a set $S$. Let $P:=\prod_{p<M\text{ prime}} p$. It suffices to delete a "small number" of elements of $S$ to make its sum zero modulo $P$. If we take $N>P$, then this is possible by just deleting some powers of two, due to binary representation (we can delete some powers of two summing to any number between $1$ and $N$), and for large enough $N$ the number of powers of two deleted is at most $\frac{1-\varepsilon}{2}N$ since this quantity is bounded logarithmically in $N$, hence there will be at least $\varepsilon N$ elements in $S$ post-deletion. Since $S$ is clearly suitable, we're done. $\blacksquare$
19.09.2023 17:47
Fix a big enough $M \in \mathbb{N}$. Let $p_1 < p_2 <\cdot \cdot \cdot< p_k$ be all primes between $1,M$.Let $N$ be a large number and let $S$ be the set of all numbers between $1,N$ st any of them is divisible by at least one of $p_i$'s. Note that : $$|S| \geq \frac{N}{2} + \frac{N}{3} . \frac{1}{2} + \frac{N}{5}.\frac{1}{3} + \cdot \cdot \cdot + \frac{N}{p_k}.\frac{1}{p_{k-1}} = N - \frac{N}{p_k}$$The above equality has been followed by the following: first , half of the numbers are even. one-third are divisible by $3$ and only half of them are already counted and so on...Now we can assume that $M$ is large enough st $N - \frac{N}{p_k} > N\epsilon$ Now Let $s$ be the sum of the elements of $S$ . We shall remove some of it's elements ; though as small as possible. Let $s \equiv r_i (mod p_i)$. Consider some elements of $S$ like $a_1 , \cdot \cdot \cdot a_t$ and let $s' = \sum a_j$. we want $s' \equiv r_i (mod p_i)$ which , by CRT , has a solution satisfying $2 \leq s' \leq \prod p_j +1$.So it's enough to write $s'$ as sum of some numbers in $S$. If it's even we're done. If it's odd , write it as $(s'-3) + 3$. So we remove at most two elements of $S$ to reach some $s'' \equiv0 (mod p_i)$ which already has the desired size and clearly satisfy the condition . So we're done.