Problem:
Let be a set of points on a sphere, where are nonnegative integers and no four points of are coplanar (that is, no four points lie on a plane). Determine how many planes pass through three points of and separate the remaining points into points on one side of the plane and points on the other side.
Solution
Solution:
Let be the number of oriented planes through three of the given points, such that exactly points lie above the plane (a plane divides 3D-space into two regions; an oriented plane can be thought of as a plane and a choice of one side "above" the plane). We then recover as
because each plane is counted twice when .
We begin by calculating . Consider the convex hull of our points. This is a polyhedron, so we apply Euler's formula . Since our points lie on a sphere, they are all vertices of and hence . No four of our points are coplanar, so each face of is a triangle and thus . Therefore,
But a plane through three of our points has all the other points on one side iff it does not cut through the interior of , i.e. iff it is a face of (the orientation should be such that the other points lie above the plane of this face). Hence .
Next, notice that for any , because reversing the orientations of all planes interchanges the roles of and . Moreover, if , then there are a total of oriented planes passing through three of our points, so . Some small values of can now be calculated directly:
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 |
| 1 | 4 | 8 | 12 | |
| 2 | 6 | 12 | ||
| 3 | 8 |
Based on these small cases, we conjecture that
We will prove this by induction.
Consider a fixed arrangement of points (on a sphere, with no four points coplanar) and suppose that holds for any points (the base case of is trivial). Consider with . Let denote the set of all pairs , where is one of our points, is an oriented plane through three of the other points, and precisely of the remaining points lie above . By first choosing and then , we find that
where the second equality is by the induction hypothesis. By first choosing and then , we find that
Equating these two expressions for , we have
for any such that . But if we have , then (1) gives
and thus . Thus, for any with ,
Starting with the base case (proven above) and applying another layer of induction, we see that the values all satisfy . This proves the induction hypothesis (i.e. that holds for any points) and thus concludes the proof.