Convex Counting (2/17 – 3/2)
You are given a set \(S\) of \(2025\) non-collinear points on the plane. A subset of \(S, S’\) is a convex if the points form a convex polygon. Let \(E(S’)\) be the number of points in the exterior of the convex polygon \(S’\). In this question, the empty set, a single point, two points are a convex polygon.
Show that
\[F_S(x) = \sum_{S’ \subseteq S, S’ \text{ convex}} x^{|S’|}(1-x)^{E(S’)} = 1\]
Hint: Convex Hull.
Solution:
Color each point black with probability \(x\), white with probability \(1 – x\). Then, the summation is the expected number of convex polygons that consist of solely black points where the exterior is all white points. This is equal to \(1\) by convex hulls.