Average free subset

A problem which someone posted in Google's internal GooglePlus page (yeah...).


Show that there is a subset $S$ of $\{1, 2, \dots, 3^k - 1\}$ such that, $S$ has at least $2^k$ elements and any three distinct elements $x, y, z$ of $S$ do not satisfy $x+y = 2z$

(i.e. no number is the average of some other two numbers).

Don't cross the streams!

There are $N$ red and $N$ blue points in the 2D plane, no three of which are collinear.

Show that we can pair off each red with a blue so that none of the $N$ line segments intersect.

[Solution]