We call a set of $k$ points bad if this set is not good (guessable definition ). Given $k$, the number of bad $k$-subsets of our initial set $S$ will be denoted by $b_k$. When the $n$ points are vertices of a convex polygon, all subsets are good, so in order to reach the conclusion we need to show that for all possible arrangements of the $n$ points, we have $\sum_{k=3}^n(-1)^kb_k=0$. We can prove this by finding a correspondence among bad sets, pairing each bad set to another bad set whose size has the opposite parity. Suppose our $n$ vertices do not form a convex $n$-gon, and let $A_1,\ldots,A_t$ be the points lying inside the convex hull of $S$. Any bad set which does not contain $A_1$ but whose strict convex hull contains $A_1$ will be paired to the set we get from it by adjoining $A_1$. This way, we have found several pairs of bad sets, and several bad sets have been left unpaired. Among these, pair the ones which do not contain $A_2$ but whose strict convex hull contains $A_2$ to the set we get by adjoining $A_2$, and so on. I hope it's Ok.

Yes, its correct. But try to find a one line proof! One of my friends solutions is just one line. I will post it if no one finds it.

Grobber's pairing seem not to be correct.. There can be a concave quadrilateral which does not contain any other points in it's convex hull except for its vertices. Maybe I'm wrong.. Can you explain why your solution works? What is the one-line solution?

Nima Ahmadi Pour wrote: Yes, its correct. But try to find a one line proof! One of my friends solutions is just one line. I will post it if no one finds it. Could you post your friend's solution :

grobber there must be a mistake in your solution let the n points be vertices of a convex quadrilateral then the answer is $ \frac{-(n-1)(n-2)}{2}$

grobber's solution seems rather correct to me. xirti didn't correctly understand the problem statement, and gauravpatil didn't correctly understand the solution. In other news: The problem is a consequence of IMO Shortlist 2006 problem C3. In fact, let $S$ be the set of our $n$ points. Using the notations of IMO Shortlist 2006 problem C3, this problem C3 says that every real $x$ satisfies $\sum_P x^{a\left(P\right)} \left(1-x\right)^{b\left(P\right)} = 1$, where the sum is taken over all convex polygons $P$ with vertices in $S$. Since two polynomials which take the same value on every real must be identic, this yields that $\sum_P X^{a\left(P\right)} \left(1-X\right)^{b\left(P\right)} = 1$ in the polynomial ring $\mathbb Z\left[X\right]$, where the sum is taken over all convex polygons $P$ with vertices in $S$. Now consider the polynomial $\sum_P X^{a\left(P\right)} \left(1-X\right)^{b\left(P\right)}$. This polynomial clearly has degree $\leq n$ (since $a\left(P\right)+b\left(P\right)\leq n$ for every $P$), and its coefficient before $X^n$ is $\sum_{\substack{P;\\ a\left(P\right)+b\left(P\right)=n}} \left(-1\right)^{b\left(P\right)} = \sum_{\substack{P;\\ a\left(P\right)+b\left(P\right)=n}} \left(-1\right)^{n-a\left(P\right)} = \left(-1\right)^n \sum_{\substack{P;\\ a\left(P\right)+b\left(P\right)=n}} \left(-1\right)^{a\left(P\right)}$. Since the polygons $P$ satisfying $a\left(P\right)+b\left(P\right)=n$ are exactly the good polygons, this means that its coefficient before $X^n$ is $\left(-1\right)^n\sum_{P\text{ is a good polygon}} \left(-1\right)^{a\left(P\right)}$. But since this polynomial equals $1$, its coefficient before $X^n$ is $0$ if $n\geq 1$ and $1$ if $n=0$. Comparing these results, we see that $\left(-1\right)^n\sum_{P\text{ is a good polygon}} \left(-1\right)^{a\left(P\right)} = 0$ if $n\geq 1$, and $\left(-1\right)^n\sum_{P\text{ is a good polygon}} \left(-1\right)^{a\left(P\right)} = 1$ if $n = 0$. In other words, $\sum_{P\text{ is a good polygon}} \left(-1\right)^{a\left(P\right)} = 0$ if $n \geq 1$, and $\sum_{P\text{ is a good polygon}} \left(-1\right)^{a\left(P\right)} = 1$ if $n = 0$. Before you blindly apply this to our problem, notice that IMO Shortlist 2006 problem C3 allows polygons to have $0$ vertices (empty set), $1$ vertices (point) or $2$ vertices (line segment). All of these polygons with $\leq 2$ vertices are convex and good, so it is clear how to remove them from the equations above.

Alternatively : We can show that $\sum_{P \subseteq S, |P| \ge 3}^{{}}(-1)^{|P|} = \sum_{i=3}^{n}(-1)^{i}c_{i} = - \binom {n-1}{2}$, where $P$ is any subset of $S$. Let $P_a$ be those subsets which form vertices of a convex polygon and there is no point inside it. (Those are the good polygons) Let $P_b$ be those subsets which don't form a convex polygon Let $P_c$ be those subsets which form a convex polygon, but there is some points inside it, that is they are convex hull of some sets in $P_b$ Take $\mathcal{P} \in P_c$, and make a set $M$ with sets in $P_b$ which has convex hull as $\mathcal{P}$. Now it is easy to see that $\sum_{P \in M \cup \mathcal{P}, |P| \ge 3}^{{}}(-1)^{|P|} = 0 $ So $ \sum_{P \subseteq S, |P| \ge 3}^{{}}(-1)^{|P|} = \sum_{P \in P_a |P| \ge 3}^{{}}(-1)^{|P|} = \sum_{i=3}^{n}(-1)^{i}c_{i}$ And it is immediate that $\sum_{P \subseteq S, |P| \ge 3}^{{}}(-1)^{|P|} = - \binom {n-1}{2}$

And this confirms darij's computation, since that offers $0 = 1 - \binom {n} {1} + \binom {n} {2} + \sum_{i=3}^{n}(-1)^{i}c_{i}$, whence $\sum_{i=3}^{n}(-1)^{i}c_{i} = -1 + \binom {n} {1} - \binom {n} {2} = -\binom {n-1} {2}$.

A direct counting approach involving (two!) inductions works. We will consider the empty set, individual points, and segments as good polygons. For a set of points $A$, write $f_A$ to denote the sum $\sum_{X \subseteq A} (-1)^{|X|}$ across all good polygons $X$ whose vertices are in $A$. Also, for points $P_1, \dots, P_m \in A$, we write $f_A(P_1, \dots, P_m)$ to restrict $X$ to those polygons containing $P_1, \dots, P_m$. So, if $S$ is our given set of $n$ points, we are interested in $f_S$. We claim that $f_S=0$, which will clearly solve the problem. The proof is by induction, with small cases (e.g. $n=1, 2, 3$) trivial. Consider the case for a general $n$ and pick a point $O$ on its convex hull. Pivoting at $O$, sweep clockwise through the remaining points and label them $A_1, \dots, A_{n-1}$ in sequence, where $\angle A_1OA_{n-1} < 180^\circ$. No polygon whose vertices belong to $A=\{A_1, \dots, A_{n-1}\}$ can contain $O$, so by hypothesis, $f_A=0$. All remaining good polygons have $O$ as a vertex, so we wish to show that $f_S(O)=0$. Let $S_i$ denote the set of points $\{O, A_1, \dots, A_i\}$. We claim that \[ f_{S_i}(O, A_i)= \begin{cases} 1 & i=1, \\ 0 & 2\le i \le n-1. \end{cases} \]This is clear when $i=1$, so suppose the claim holds for $i=1, 2, \dots, j-1$. We'll show that it holds for $i=j$, i.e. $f_{S_j}(O, A_j) = 0$. Take the ray pointing in the direction of $\overrightarrow{OA_j}$ and pivot it counterclockwise about $A_j$; we'll sweep through the points $A_1, \dots, A_{j-1}$ in some order and hit $A_L$ last. Each time we hit $A_k$, we'll add to our count all the good polygons with $O, A_j, A_k$ as consecutive vertices. There are a few cases: Suppose $\triangle OA_jA_k$ contains a point in its interior. Then there are no such good polygons. Suppose $\triangle OA_jA_k$ has no interior points and $k \neq L$. Let $S_k'$ be the set of $A_i$'s with $i \le k$ that lie between or on rays $\overrightarrow{A_jO}$ and $\overrightarrow{A_jA_k}$, excluding $A_j$. Note that every good polygon with $O, A_j, A_k$ as consecutive vertices can be built by appending $A_j$ to a unique good polygon counted by $f_{S_k'}(O, A_k)$. The key point is that $|S_k'| \ge 3$ since it contains $O, A_k, A_L$! So, by assumption that our claim holds for smaller values of $i$ (smaller configurations, really), we must have $f_{S_k'}(O, A_k) = 0$. In particular, when we append $A_j$ to those polygons, we just flip the parity of the number of sides of each one, meaning we still add $0$ to our count in this case. If $k=L$, then all we have is the triangle $OA_kA_L$, so we add $-1$ to our count. Note that the above three cases cover all good polygons counted by $f_{S_j}(O, A_j)$ except for the segment $\overline{OA_j}$ itself. Thus, we compute $f_{S_j}(O, A_j)=-1 + 1=0$, and the claim is proved. Finally, we may compute $f_S(O)$ by summing over all $f_{S_i}(O, A_i)$, and then subtracting $1$ for the good polygon consisting of just $O$. By the claim, this is just $0$, which concludes our induction.