Let S be a finite set of points in the plane such that no three of them are on a line. For each convex polygon P whose vertices are in S, let a(P) be the number of vertices of P, and let b(P) be the number of points of S which are outside P. Prove that for every real number x P∑xa(P)(1−x)b(P)=1, where the sum is taken over all convex polygons with vertices in S.
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 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, P∑xa(P)yb(P)=P∑xa(P)yb(P)(x+y)c(P)=P∑i=0∑c(P)(ic(P))xa(P)+iyb(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 xryn−r (0≤r≤n) multiplied by some nonnegative integer coefficients. For a fixed r, the coefficient of xryn−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 xryn−r equals (rn). The desired result follows: P∑xa(P)yb(P)=r=0∑n(rn)xryn−r=(x+y)n=1.
Solution 2
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⊂C be an arbitrary nonempty set. For any convex polygon P with vertices in the set S\X, we have b(P) points of S outside P. Excluding the points of X - all outside P - the set S\X contains exactly b(P)−∣X∣ of them. Writing 1−x=y, by the induction hypothesis P⊂S\X∑xa(P)yb(P)−∣X∣=1 (where P⊂S\X means that the vertices of P belong to the set S\X ). Therefore P⊂S\X∑xa(P)yb(P)=y∣X∣. All convex polygons appear at least once, except the convex hull C itself. The convex hull adds xm. We can use the inclusion-exclusion principle to compute the sum of the other terms: P=C∑xa(P)yb(P)=k=1∑m(−1)k−1∣X∣=k∑P⊂S\X∑xa(P)yb(P)=k=1∑m(−1)k−1∣X∣=k∑yk=k=1∑m(−1)k−1(km)yk=−((1−y)m−1)=1−xm and then P∑xa(P)yb(P)=P=C∑+P=C∑=xm+(1−xm)=1.
Source: MathNet,
licensed CC-BY-4.0.
Statement and solution reproduced as published; topic, difficulty and ordering added
by this site.