Olympiad Maths Prep

Track / Stage 8 / 104 of 180 #1804 of 2000

Problem 1804

IMO Shortlist mid-range; USAMO P2/P5
Combinatorics Difficulty 8.5 Prove it IMO 2006 Shortlisted Problems · IMO · 2006

Let SS be a finite set of points in the plane such that no three of them are on a line. For each convex polygon PP whose vertices are in SS, let a(P)a(P) be the number of vertices of PP, and let b(P)b(P) be the number of points of SS which are outside PP. Prove that for every real number xx
Pxa(P)(1x)b(P)=1, \sum_{P} x^{a(P)}(1-x)^{b(P)}=1,
where the sum is taken over all convex polygons with vertices in SS.

NB. A line segment, a point and the empty set are considered as convex polygons of 2, 1 and 0 vertices, respectively.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solutions — 2

Solution 1

For each convex polygon PP whose vertices are in SS, let c(P)c(P) be the number of points of SS which are inside PP, so that a(P)+b(P)+c(P)=na(P)+b(P)+c(P)=n, the total number of points in SS. Denoting 1x1-x by yy,
Pxa(P)yb(P)=Pxa(P)yb(P)(x+y)c(P)=Pi=0c(P)(c(P)i)xa(P)+iyb(P)+c(P)i. \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)}\binom{c(P)}{i} x^{a(P)+i} y^{b(P)+c(P)-i} .
View this expression as a homogeneous polynomial of degree nn in two independent variables x,yx, y. In the expanded form, it is the sum of terms xrynrx^{r} y^{n-r} (0rn0 \leq r \leq n) multiplied by some nonnegative integer coefficients.
For a fixed rr, the coefficient of xrynrx^{r} y^{n-r} represents the number of ways of choosing a convex polygon PP and then choosing some of the points of SS inside PP so that the number of vertices of PP and the number of chosen points inside PP jointly add up to rr.
This corresponds to just choosing an rr-element subset of SS. The correspondence is bijective because every set TT of points from SS 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 TT - and the second consists of some points inside that polygon.
So the coefficient of xrynrx^{r} y^{n-r} equals (nr)\binom{n}{r}. The desired result follows:
Pxa(P)yb(P)=r=0n(nr)xrynr=(x+y)n=1. \sum_{P} x^{a(P)} y^{b(P)}=\sum_{r=0}^{n}\binom{n}{r} x^{r} y^{n-r}=(x+y)^{n}=1 .

Solution 2

Apply induction on the number nn of points. The case n=0n=0 is trivial. Let n>0n>0 and assume the statement for less than nn points. Take a set SS of nn points.
Let CC be the set of vertices of the convex hull of SS, let m=Cm=|C|.
Let XCX \subset C be an arbitrary nonempty set. For any convex polygon PP with vertices in the set S\XS \backslash X, we have b(P)b(P) points of SS outside PP. Excluding the points of XX - all outside PP - the set S\XS \backslash X contains exactly b(P)Xb(P)-|X| of them. Writing 1x=y1-x=y, by the induction hypothesis
PS\Xxa(P)yb(P)X=1 \sum_{P \subset S \backslash X} x^{a(P)} y^{b(P)-|X|}=1
(where PS\XP \subset S \backslash X means that the vertices of PP belong to the set S\XS \backslash X ). Therefore
PS\Xxa(P)yb(P)=yX. \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 CC itself. The convex hull adds xmx^{m}. We can use the inclusion-exclusion principle to compute the sum of the other terms:
PCxa(P)yb(P)=k=1m(1)k1X=kPS\Xxa(P)yb(P)=k=1m(1)k1X=kyk=k=1m(1)k1(mk)yk=((1y)m1)=1xm \begin{gathered} \sum_{P \neq 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}\binom{m}{k} y^{k}=-\left((1-y)^{m}-1\right)=1-x^{m} \end{gathered}
and then
Pxa(P)yb(P)=P=C+PC=xm+(1xm)=1. \sum_{P} x^{a(P)} y^{b(P)}=\sum_{P=C}+\sum_{P \neq C}=x^{m}+\left(1-x^{m}\right)=1 .

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.