There exists B subset A, |B| = log n, A \cap 2*B = \emptyset This is exercise 1.8.1 of Additive Combinatorics.
Problem
Given $A \in Z^+$ a set of $n$ different integers. Prove that there exists $B\subset A$, $|B| = \Omega ( \log n )$, s.t. $A \cap 2*B = \emptyset$.
Here, $2*B$ means $\{ a + b | a, b \in B, a \neq b \}$.
Strategies:
The dumb thing to try is $P(x \in B) = \frac{\log n}{n}$. Unfortunately, the expected value of $A \cap 2B = \Theta(\log^2 n)$, which is achievable via this example:
$A = ( N + [1 .. k]) \cup (2N + [1..k]) \cup (3M + [1 .. 2k])$
Thus, we can't just uniformly, independently, sample the elements of $B$ from $A$.
The next thing to try is to "segment" $A$ into regions of powers of to, i.e. $[1, 2), [2, 4), [4, 8), ... $. Then try to reason about how many elements to pick from each segment. Nothing interesting has happened from this yet.
Question:
What should I be looking for to solve this problem? (This problem comes from the section on Thin Bases, and the chapter on the Probabilistic Method).
 A: It seems that this was established by D.A. Klarner, although the proof has
not been published till a year 1971 paper by Choi (who credited Klarner
for it). The argument is rather straightforward and does not use the
probabilistic method; it goes as follows.
For each $b\in A$, let $S(b):=\{a\in A\setminus\{b\}\colon b+a\in A\}$; we
thus want to find a large subset $B\subset A$ so that for any $b\in B$, we
have $S(b)\cap B=\varnothing$. We choose elements for $B$ one by one,
starting with $b_1:=\max A$ and, once $b_1,\ldots,b_{m-1}$ got selected,
choosing $b_m$ to be the element of
 $A\setminus(S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\})$
with $S(b_m)$ of the smallest possible size.
For brevity, write
 $S:=S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\}$.
Observing that if $a$ is one of the $k+1$ largest elements of $A$, then
$|S(a)|\le k$, we conclude that $b_m\in A\setminus S$ can be chosen so that
$|S(b_m)|\le |S|$; hence,
  $$ |S(b_m)| \le |S(b_1)|+\dotsb+|S(b_{m-1})| + m-1. $$
A simple induction now confirms that $|S(b_m)|<2^{m-1}$ and therefore, there
is a way to choose $b_m$ as long as $2^{m-1}\le|A|$ holds. As a result, we end up
with a set $B=\{b_1,\ldots,b_m\}$ such that $m>\log_2|A|$.
A: [Edited to give more information in reply to Terry Tao's comment
and Seva's query]
I told Zach Abel of this problem, and the next day he e-mailed me that
Zach and Andrey Grinsphun (both are graduate students at MIT) obtained the
following solution:

incrementally take the largest element that doesn't violate
the condition. Each insertion at most doubles the number of elements
of $A$ that are ruled out, so it gets $\Omega(\log n)$ elements.

In later correspodence Andrey explains that the "ruled out" elements
include those of $B$ itself, and it's actually not "doubles" but
"doubles and adds 1 to", so after choosing $m$ elements there are
at most $2^m-1$ forbidden.  In more detail (translating some English
into equivalent formulas):

List $A$ in increasing order $A=\lbrace a_1,...,a_n \rbrace$.
Start with $B$ empty and note that this forbids at most
$2^m-1=0$ elements ($m=|B|$, the size of $B$).
Then if we currently have some $B$ of size $m$, when we choose the largest
element that is not forbidden, since $B$ forbids at most $2^m-1$ elements
by induction we may add $a_k$ to $B$ for some $k \geq n-2^m+1$.
Then the number of new forbidden elements is at most
$1+|(A-a_k) \cap A|$ (the $1$ comes from $a_k$ itself).  But
$|(A-a_k) \cap A| \leq |\lbrace x\in A : x > a_k \rbrace|$,
which is at most the number of elements $B$ forbids.
In particular, it's at most $2^m-1$, so the number of new forbidden elements
is at most $2^m-1+1=2^m$, and so the total number of forbidden elements is
at most $2^m+2^m-1 = 2^{m+1}-1$.

[CW because this is not my own argument.  I still wonder if
$\log n$ is anywhere near the right order; it feels surprisingly small.
It's not even obvious to me that there are sets $A$ for which the
smallest $B$ has size $o(n)$, let alone $n^{o(1)}$.
(See Terry Tao's reply: Ruzsa indeed obtained an $n^{o(1)}$ bound!)]
