Maths Olympiad Prep

Library / /86 of 86

Geometry Difficulty 7.8 National Olympiad, round 2 Prove it United States

Problem:
Let SS be a set of a+b+3a+b+3 points on a sphere, where a,ba, b are nonnegative integers and no four points of SS are coplanar (that is, no four points lie on a plane). Determine how many planes pass through three points of SS and separate the remaining points into aa points on one side of the plane and bb points on the other side.

Solution

Solution:
Let f(a,b)f(a, b) be the number of oriented planes through three of the given a+b+3a+b+3 points, such that exactly aa 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 gg as
g(a,b)={f(a,b),ab12f(a,b),a=b g(a, b)=\left\{\begin{array}{cc} f(a, b), & a \neq b \\ \frac{1}{2} f(a, b), & a=b \end{array}\right.
because each plane is counted twice when a=ba=b.

We begin by calculating f(a,0)f(a, 0). Consider the convex hull Σ\Sigma of our a+3a+3 points. This is a polyhedron, so we apply Euler's formula VE+F=2V-E+F=2. Since our a+3a+3 points lie on a sphere, they are all vertices of Σ\Sigma and hence V=a+3V=a+3. No four of our points are coplanar, so each face of Σ\Sigma is a triangle and thus 2E=3F2 E=3 F. Therefore,
F=3F2F=2E2(2V+E)=2(V2)=2(a+1). F=3 F-2 F=2 E-2(2-V+E)=2(V-2)=2(a+1) \text{.}
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 Σ\Sigma, i.e. iff it is a face of Σ\Sigma (the orientation should be such that the other points lie above the plane of this face). Hence f(a,0)=F=2(a+1)f(a, 0)=F=2(a+1).

Next, notice that f(a,b)=f(b,a)f(a, b)=f(b, a) for any a,b0a, b \geq 0, because reversing the orientations of all planes interchanges the roles of aa and bb. Moreover, if n=a+b+3n=a+b+3, then there are a total of 2(n3)2\left(\begin{array}{l}n \\ 3\end{array}\right) oriented planes passing through three of our points, so f(n3,0)+f(n4,1)++f(1,n4)+f(0,n3)=2(n3)f(n-3,0)+f(n-4,1)+\cdots+f(1, n-4)+f(0, n-3)=2\left(\begin{array}{l}n \\ 3\end{array}\right). Some small values of f(a,b)f(a, b) can now be calculated directly:

0123
02468
14812
2612
38

Based on these small cases, we conjecture that
f(a,b)=2(a+1)(b+1). f(a, b)=2(a+1)(b+1) .
We will prove this by induction.

Consider a fixed arrangement of n+1n+1 points (on a sphere, with no four points coplanar) and suppose that ()(*) holds for any nn points (the base case of n=3n=3 is trivial). Consider a,b0a, b \geq 0 with a+b+3=na+b+3=n. Let Sa,bS_{a, b} denote the set of all pairs (P,Π)(P, \Pi), where PP is one of our n+1n+1 points, Π\Pi is an oriented plane through three of the other points, and precisely aa of the remaining points lie above Π\Pi. By first choosing PP and then Π\Pi, we find that
Sa,b=(n+1)f(a,b)=2(n+1)(a+1)(b+1), \left|S_{a, b}\right|=(n+1) f(a, b)=2(n+1)(a+1)(b+1),
where the second equality is by the induction hypothesis. By first choosing Π\Pi and then PP, we find that
Sa,b=(a+1)f(a+1,b)+(b+1)f(a,b+1). \left|S_{a, b}\right|=(a+1) f(a+1, b)+(b+1) f(a, b+1) .
Equating these two expressions for Sa,b\left|S_{a, b}\right|, we have
(a+1)f(a+1,b)+(b+1)f(a,b+1)=2(a+b+4)(a+1)(b+1), (a+1) f(a+1, b)+(b+1) f(a, b+1)=2(a+b+4)(a+1)(b+1) \text{,}
for any a,b0a, b \geq 0 such that a+b+3=na+b+3=n. But if we have f(a+1,b)=2(a+2)(b+1)f(a+1, b)=2(a+2)(b+1), then (1) gives
(b+1)f(a,b+1)=2(a+b+4)(a+1)(b+1)(a+1)f(a+1,b)=2(a+b+4)(a+1)(b+1)2(a+1)(a+2)(b+1)=2(a+1)(b+1)((a+b+4)(b+2))=2(a+1)(b+1)(b+2), \begin{aligned} (b+1) f(a, b+1) & =2(a+b+4)(a+1)(b+1)-(a+1) f(a+1, b) \\ & =2(a+b+4)(a+1)(b+1)-2(a+1)(a+2)(b+1) \\ & =2(a+1)(b+1)((a+b+4)-(b+2))=2(a+1)(b+1)(b+2), \end{aligned}
and thus f(a,b+1)=2(a+1)(b+2)f(a, b+1)=2(a+1)(b+2). Thus, for any a,b0a, b \geq 0 with a+b+3=na+b+3=n,
f(a+1,b) satisfies ()f(a,b+1) satisfies (). f(a+1, b) \text{ satisfies }(*) \quad \Longrightarrow \quad f(a, b+1) \text{ satisfies }(*) \text{.}
Starting with the base case f(n2,0)=n1f(n-2,0)=n-1 (proven above) and applying another layer of induction, we see that the values f(n2,0),f(n3,1),f(n4,2),,f(0,n2)f(n-2,0), f(n-3,1), f(n-4,2), \ldots, f(0, n-2) all satisfy ()(*). This proves the induction hypothesis (i.e. that ()(*) holds for any n+1n+1 points) and thus concludes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.