Sorry for reviving this dead thread, but the WOOT group unsuccessfully tried this today... More importantly, the problem should actually be as follows: Quote: Let $ n > 2$. Show that there is a set of $ 2^{n - 1}$ points in the plane, no three collinear such that no $ 2n$ form a convex $ 2n$-gon. Original post now fixed by mod.

The famous Happy Ending theorem http://en.wikipedia.org/wiki/Happy_Ending_problem conjectures that among $2^{n-2} + 1$ points in general position in the plane, there are $n$ being the vertices of a convex polygon. Erdös and Szekeres built examples with $2^{n-2}$ points for which no such convex $n$-gon exists. So transposing this for $N=2n$, examples exist with $2^{N-2} = 2^{2n-2} = (2^{n-1})^2$, much better than what was requested.

Induct on $n$. Base $n=2$ is clear. For passing from $n$ to $n+1$ take a set $M$ of $2^{n-1}$ points without convex $2n$-gons and consider $M\cup M+x$, where $x$ is a small vector and direction of $x$ is of general position. Then three pairs $(a,a+x),(b,b+x),(c,c+x)$ are already not in a convex position, so the maximal number of points in convex position in the set $M\cup (M+x)$ is at most $(2n-1)+2$.

This is also an exercise in chapter 14 of "Combinatorial exercises" by Laszlo Lovasz, Akademia Kiadó, 1979.