Also MathLinks Contest, 1st Edition, 7th Round

Btw, will the solutions to the problems from the contest be on the site? Because in the contest section, they are missing

I have a solution myself but I am wondering it is true or not.Please check it and tell me if my solution is wrong.Thanks.

Hmm...Why do you think that $ B$ is a good subset? What it has to do with that $ a_1$ is the smallest element.

iura wrote: For a set $ S$, let $ |S|$ denote the number of elements in $ S$. Let $ A$ be a set of positive integers with $ |A| = 2001$. Prove that there exists a set $ B$ such that (i) $ B \subseteq A$; (ii) $ \dsp |B| \ge 668$; (iii) for any $ u, v \in B$ (not necessarily distinct), $ u + v \not\in B$. I saw this problem in a chinese book, but with $ 2001$ changed to $ n$ and $ \ge 668$ changed to $ > \frac{n}{3}$ Here is the solution, given by a Israel mathematician N.Alon. Let the elements in $ A$ be $ a_1,a_2,...,a_n$, and choose a prime of the form $ 3k-1$ and is greater than all the elements in $ A$. Then consider $ a_i,2a_i,...,pa_i$ where $ i$ is an integer such that $ 1\le i\le n$. They form a complete set of residues of $ p$. Therefore there are $ k$ of them congruent to $ k,k+1,k+2,...2k-1$ modulo $ p$. Let $ x_j$ be the number of numbers among $ ja_1,ja_2,...,ja_n$ that congruent to $ k,k+1,k+2,...2k-1$ modulo $ p$. Now $ x_1+x_2+x_3+...+x_p=kn$ So there exists a $ x_t$ such that $ x_t\ge\frac{kn}{p}=\frac{kn}{3k-1}\ge\frac{n}{3}$ Then $ B={a\in A}$ such that $ ta$ congruent to $ k,k+1,k+2,...2k-1$ modulo ${ p}$

awesome solution

Let $ A = \{a_1,a_2,...,a_{2001}\}$.Let $ p$ be a prime number such that $ p \equiv 2 (mod 3)$ and $ p > a_i \forall i = 1,2,...,2001$. Such a prime p exists by Dirichlet's Theorem,althought the result can also be easily proven directly.There is at least 1 prime congruent to 2 modulo 3(namely,2).Suppose there were only finitely many primes congruent to 2 modulo 3,and let their product be $ P$.Then $ 3P - 1$,which is larger than $ P$ and congruent to 2 modulo 3,must have another prime divisor congruent to 2 modulo 3,contradiction.Thus,the orginal assumption was wrong,and there are infinitely many odd primes that are congruent to 2 modulo 3.Specifically,one such prime is larger than all $ a_i$. All elements of $ S$ are distinct and non-zero modulo $ p$. Call a number $ n$ "mediocre" is the least positive residue of $ n$ mod $ p$ lies in $ [ \frac {p + 1}{3},\frac {2p - 1}{3}]$.For any $ 1$≤$ i$≤$ 2001$,there are exactly $ \frac {p + 1}{3}$ integer values of $ k \in [1,p - 1]$ such that $ ka_i$ is mediocre.Thus,there are $ \frac {2001(p + 1)}{3} = 667(p + 1)$ pairs of $ (k,i)$ such that $ ka_i$ is mediocre. By Pigeonhole Principle,there exists some $ k$ for which the set $ B = \{a_i|ka_i$ is medicre$ \}$ has it least $ 668$ elements. We now claim that this $ B$ satisfies the desired properties.It suffices to show that $ k$ times the sum of any 2 elements of $ B$ cannot be mediocre and hence connot equal $ k$ times any elements of $ B$.To that end,note that $ k$ times the sum of any 2 elements of $ B$ cannot be medicre because it is congruent mod $ p$ to some number in $ [\frac{2(p+1)}{3},\frac{2(2p-1)}{3}]$ or, eqivalently,to some number in $ [0,\frac{(p-1)}{3}] \cup [\frac{(2p+2)}{3},p-1]$,which is a set containing no mediocre numbers.Thus,the set $ B$ satisfies the desired properties.

It is a special case of a theorem due to Paul.Erdos about sum-free set ( not have elements $u$ and $v$ such that $u+v$ belong also to it.) every set of positive integers A always have a sub set S with $|S|>|A|/3$ which is sum free.you can see it in many combinatoric book. The same as VMO 2006 pro 5 . and probabilistic method will work properly.

This solution seems different from everyone else's (though it uses the same $(\tfrac{1}{3},\tfrac{2}{3})$ interval modulo $1$ idea). Let $n=2001$, and note that $668=\tfrac{n}{3}+1$. For a positive real number $r$, define $S_r=\{rx \colon x \in \mathbb{R}_{>0},\tfrac{1}{3}<x-\lfloor x \rfloor<\tfrac{2}{3}\}$. Notice that $a,b \in S_r$ implies $a+b \notin S_r$. Let $m$ be the largest element of $A$, and let $N$ be an arbitrarily large number. We claim that \[\int_\frac{m}{(N+1)m-\frac{1}{3}}^\frac{m}{Nm+\frac{1}{3}} |S_r \cap A| \,\mathrm{d}r>\frac{n}{3}\left(\frac{m}{Nm+\frac{1}{3}}-\frac{m}{(N+1)m-\frac{1}{3}}\right),\]which shows that there exists a real number $r \in [\tfrac{m}{(N+1)m-\frac{1}{3}},\tfrac{m}{Nm+\frac{1}{3}}]$ such that if $B=S_r \cap A$, then $|B|>\tfrac{n}{3}$. It suffices to prove that \[\int_\frac{m}{(N+1)m-\frac{1}{3}}^\frac{m}{Nm+\frac{1}{3}} |S_r \cap \{k\}| \,\mathrm{d}r>\frac{1}{3}\left(\frac{m}{Nm+\frac{1}{3}}-\frac{m}{(N+1)m-\frac{1}{3}}\right)\]for all $k \in A$. But we have \begin{align*} \int_\frac{m}{(N+1)m-\frac{1}{3}}^\frac{m}{Nm+\frac{1}{3}} |S_r \cap \{k\}| \,\mathrm{d}r&=\frac{k}{Nk+\frac{1}{3}}-\frac{k}{Nk+\frac{2}{3}}+\frac{k}{Nk+\frac{4}{3}}-\frac{k}{Nk+\frac{5}{3}}+\cdots+\frac{k}{(N+1)k-\frac{2}{3}}-\frac{k}{(N+1)k-\frac{1}{3}} \\ &\ge \frac{1}{3}\left(\frac{k}{Nk+\frac{1}{3}}-\frac{k}{Nk+\frac{2}{3}}+\frac{k}{Nk+\frac{2}{3}}-\frac{k}{Nk+\frac{3}{3}}+\cdots+\frac{k}{(N+1)k}-\frac{k}{(N+1)k+\frac{1}{3}}\right) \\ &=\frac{1}{3}\left(\frac{k}{Nk+\frac{1}{3}}-\frac{k}{(N+1)k+\frac{1}{3}}\right). \end{align*}Thus, it suffices to prove that \begin{align*} \frac{k}{Nk+\frac{1}{3}}-\frac{k}{(N+1)k+\frac{1}{3}}&>\frac{m}{Nm+\frac{1}{3}}-\frac{m}{(N+1)m-\frac{1}{3}} \\ \Longleftrightarrow \frac{k^2}{(Nk+\frac{1}{3})((N+1)k+\frac{1}{3})}&>\frac{m^2-\frac{2}{3}m}{(Nm+\frac{1}{3})((N+1)m-\frac{1}{3})}. \end{align*}Indeed, notice that the left-hand side tends to $\tfrac{1}{N(N+1)}$ while the right-hand side tends to $\tfrac{1-\frac{2}{3m}}{N(N+1)}$ as $N$ goes to infinity, as desired. $\square$ Remark: This solution can be motivated, despite having a bunch of random constructions that appear seemingly out of nowhere. At first, I tried to make an argument using $\nu_2$: if there are more than $\tfrac{n}{3}$ odd numbers in $A$, choose those; otherwise, look at the subset of even numbers and try to choose something. This argument isn't strong enough, but it uses a prototypical version of $S_r$: the set $\{rx \colon x \in \mathbb{N},x \equiv 1 \pmod{2}\}$ where $r$ is a power of $2$. Eventually, I realized two things: we could set $r$ to be any real number, and we could relax $x \equiv 1 \pmod{2}$ to $x \approx 1 \pmod{2}$. This gave me the version of $S_r$, the set of all positive real numbers less than $\tfrac{1}{3}r$ away from the nearest odd multiple of $r$, which I used to solve the problem. I later scaled the definition of $S_r$ by $2$ for writeup purposes. The biggest conceptual jump in this problem for me was seriously thinking about using small $r$, as you might not expect small $r$ to give anything useful, and indeed, most of the solutions in this thread use a large prime $p$, which can be thought of as a large $r$ except you can transform $A$ modulo $p$ with multiplication. My first try was with $r \in [\tfrac{1}{N+1},\tfrac{1}{N}]$ (using the definition of $S_r$ used in this writeup), but this wasn't quite enough because it gave a density slightly less than $\tfrac{1}{3}$. After flailing with different constructions, I realized that you could cut off very small bits of the interval $[\tfrac{1}{N+1},\tfrac{1}{N}]$ to create $[\tfrac{m}{(N+1)m-\frac{1}{3}},\tfrac{m}{Nm+\frac{1}{3}}]$ while not changing the sum. I was reluctant to try this because I thought it would almost certainly be insufficient, but it turned out to be enough.