IMO 2006 Shortlisted Problems

For each convex polygon $P$ whose vertices are in $S$, let $c(P)$ be the number of points of $S$ which are inside $P$, so that $a(P)+b(P)+c(P)=n$, the total number of points in $S$. Denoting $1-x$ by $y$, $$\sum _P{x}^{a(P)}{y}^{b(P)}=\sum _P{x}^{a(P)}{y}^{b(P)}(x+y{)}^{c(P)}=\sum _P\sum _{i=0}^{c(P)}(\genfrac{}{}{0ex}{}{c(P)}{i})x^{a(P)+i}{y}^{b(P)+c(P)-i}.$$ View this expression as a homogeneous polynomial of degree $n$ in two independent variables $x,y$. In the expanded form, it is the sum of terms $x^r{y}^{n-r}$ ($0\le r\le n$) multiplied by some nonnegative integer coefficients. For a fixed $r$, the coefficient of $x^r{y}^{n-r}$ represents the number of ways of choosing a convex polygon $P$ and then choosing some of the points of $S$ inside $P$ so that the number of vertices of $P$ and the number of chosen points inside $P$ jointly add up to $r$. This corresponds to just choosing an $r$-element subset of $S$. The correspondence is bijective because every set $T$ of points from $S$ splits in exactly one way into the union of two disjoint subsets, of which the first is the set of vertices of a convex polygon - namely, the convex hull of $T$ - and the second consists of some points inside that polygon. So the coefficient of $x^r{y}^{n-r}$ equals $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. The desired result follows: $$\sum _P{x}^{a(P)}{y}^{b(P)}=\sum _{r=0}^n\left(\genfrac{}{}{0ex}{}{n}{r}\right)x^r{y}^{n-r}=(x+y{)}^n=1.$$

---

Alternative solution.

Apply induction on the number $n$ of points. The case $n=0$ is trivial. Let $n>0$ and assume the statement for less than $n$ points. Take a set $S$ of $n$ points. Let $C$ be the set of vertices of the convex hull of $S$, let $m=|C|$. Let $X\subset C$ be an arbitrary nonempty set. For any convex polygon $P$ with vertices in the set $S\backslash X$, we have $b(P)$ points of $S$ outside $P$. Excluding the points of $X$ - all outside $P$ - the set $S\backslash X$ contains exactly $b(P)-|X|$ of them. Writing $1-x=y$, by the induction hypothesis $$\sum _{P\subset S\backslash X}{x}^{a(P)}{y}^{b(P)-|X|}=1$$ (where $P\subset S\backslash X$ means that the vertices of $P$ belong to the set $S\backslash X$ ). Therefore $$\sum _{P\subset S\backslash X}{x}^{a(P)}{y}^{b(P)}=y^{|X|}.$$ All convex polygons appear at least once, except the convex hull $C$ itself. The convex hull adds $x^m$. We can use the inclusion-exclusion principle to compute the sum of the other terms: $$\begin{array}{c}\sum _{P\ne C}{x}^{a(P)}{y}^{b(P)}=\sum _{k=1}^m(-1{)}^{k-1}\sum _{|X|=k}\sum _{P\subset S\backslash X}{x}^{a(P)}{y}^{b(P)}=\sum _{k=1}^m(-1{)}^{k-1}\sum _{|X|=k}{y}^k\\ =\sum _{k=1}^m(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{m}{k})y^k=-\left((1-y{)}^m-1\right)=1-x^m\end{array}$$ and then $$\sum _P{x}^{a(P)}{y}^{b(P)}=\sum _{P=C}+\sum _{P\ne C}=x^m+\left(1-x^m\right)=1.$$