Maths Olympiad Prep

Library / /5 of 5

Geometry Difficulty 5.3 AIME, harder Prove it Japan

A plane lying in the 3-dimensional space splits the space into 2 parts. We call one such part (excluding the plane) a half space. Let SS be a set consisting of 10 points in the space, no 4 among them lying on a same plane. Determine the number of subsets of SS which can be obtained as an intersection of SS with some half space.

Solution

[260].
First, let us explain some terminologies used in the sequel.
For sets AA and BB, we denote by ABA \setminus B the set of those elements in AA not in BB.
For a finite set AA, we denote by A|A| the number of elements in AA. For a mapping F:ABF: A \to B and for bBb \in B, we denote by F1(b)F^{-1}(b) the set {aAF(a)=b}\{a \in A \mid F(a) = b\}. We call a mapping F:ABF: A \to B surjective if for every bBb \in B the set F1(b)F^{-1}(b) is not empty.

In order to give the answer to the problem, we prove a couple of lemmas.

Lemma 1
A plane is partitioned into 2 parts by a straight line on it. One of the parts (excluding the line itself) is called a half-plane. Let SS be a subset of a plane consisting of nn points, no 3 among them lie on a same straight line. Then the number of subsets of SS which can be obtained as an intersection of SS with some half-plane is n2n+2n^2 - n + 2.

Proof:
Fix an xyxy-coordinate system in the plane. Then we claim that a subset TT of the set SS satisfies the condition of Lemma 1 if and only if the following condition is satisfied:
There exists a linear function f(x,y)f(x, y) of 2 variables x,yx, y such that
{f(P)>0,PTf(P)<0,PST \begin{cases} f(P) > 0, & P \in T \\ f(P) < 0, & P \in S \setminus T \end{cases}
Here, we mean by f(P)f(P) the value f(x,y)f(x, y), where (x,y)(x, y) are the coordinates of the point PP. If ff satisfies the property stated above, we will say that f(x,y)f(x, y) cuts off TT from SS.

Let us prove the claim made above by induction on the number nn of points of SS. Clearly, the claim holds if n=1n = 1. So, suppose the claim is valid for kn1k \le n - 1 and show that it holds for nn. Let us represent SS as {P1,P2,,Pn}\{P_1, P_2, \dots, P_n\}. Denote by X(S)X(S) the set of all those subsets TT of SS which satisfy the condition of Lemma 1. Define SS' to be the set S{Pn}S \setminus \{P_n\}, and define X(S)X(S') in the same way. Define a mapping F:X(S)X(S)F: X(S) \to X(S') by setting F(T)=TSF(T) = T \cap S' for TX(S)T \in X(S). It is easy to see that F1(T){T,T{Pn}}F^{-1}(T') \subset \{T, T \cup \{P_n\}\} holds for any TX(S)T \in X(S').

Let TX(S)T \in X(S') and let f(x,y)f(x, y) be a linear function which cuts off TT from SS'. If f(Pn)0f(P_n) \ge 0, then for any sufficiently small ϵ>0\epsilon > 0, the linear function f(x,y)+ϵf(x, y) + \epsilon cuts off T{Pn}T \cup \{P_n\} from SS. Therefore, T{Pn}X(S)T \cup \{P_n\} \in X(S), while if f(Pn)0f(P_n) \le 0, the function f(x,y)ϵf(x, y) - \epsilon for sufficiently small ϵ>0\epsilon > 0 will cut off TT' from SS so that TX(S)T \in X(S). Therefore, we can conclude that the mapping FF defined above is surjective, and for every TX(S)T \in X(S') we have that F1(T)|F^{-1}(T')| equals either 1 or 2.

We now prove the following:

Lemma 2. For TX(S)T \in X(S'), the following 2 conditions are mutually equivalent:
(1) There exists a linear function f(x,y)f(x, y) which cuts off TT from SS' and for which f(Pn)=0f(P_n) = 0.
(2) F1(T)=2|F^{-1}(T)| = 2.

Proof: It follows from what we stated above that the condition (2) is equivalent to the statement F1(T)={T,T{Pn}}F^{-1}(T) = \{T, T \cup \{P_n\}\}. Now, if (1) is satisfied, for a sufficiently small ϵ>0\epsilon > 0, the function f(x,y)ϵf(x, y) - \epsilon cuts off TT from SS, and the function f(x,y)+ϵf(x, y) + \epsilon cuts off T{Pn}T \cup \{P_n\} from SS. Therefore, we have T,T{Pn}X(S)T, T \cup \{P_n\} \in X(S) and (2) is satisfied.

Conversely, suppose (2) is satisfied. Let f(x,y)f(x, y) and g(x,y)g(x, y) be linear functions cutting off TT, T{Pn}T \cup \{P_n\}, respectively, from SS. Let λ=f(Pn)g(Pn)\lambda = -\frac{f(P_n)}{g(P_n)}. Then the linear function f(x,y)+λg(x,y)f(x, y) + \lambda g(x, y) takes the value 0 at the point PnP_n, and cuts off TT from SS', since λ>0\lambda > 0. Therefore, (1) is satisfied. Thus, Lemma 2 is proved.

Let us continue with the proof of Lemma 1. Since FF is surjective, Lemma 2 implies that the number X(S)X(S)|X(S)| - |X(S')| coincides with the number of TT's satisfying the condition (1) of Lemma 2. We may assume that the xx-coordinates of the points P1,,PnP_1, \dots, P_n are all distinct, by changing the coordinate system, if necessary. Let aa be a real number different from the xx-coordinate of the point PnP_n. For each PiSP_i \in S', let (a,yi)(a, y_i) be the point of intersection of the lines x=ax = a and PnPiP_n P_i. Then, from the assumption that no 3 points from the set SS are colinear it follows that numbers y1,y2,,yn1y_1, y_2, \dots, y_{n-1} are all distinct. We also see that the fact TT satisfies the condition (1) of Lemma 2 is equivalent to the statement that
T={PiSh(yi)>0} T = \{ P_i \in S' \mid h(y_i) > 0 \}
for some linear function h(y)h(y) of 1 variable. Total number of such TT's is 2(n1)2(n-1), and the induction hypothesis says that X(S)=(n1)2(n1)+2|X(S')| = (n-1)^2 - (n-1) + 2 so that we have X(S)=X(S)+2(n1)=n2n+2|X(S)| = |X(S')| + 2(n-1) = n^2 - n + 2, which proves the assertion of Lemma 1.

Now, let P(n)=n33n2+8n3P(n) = \frac{n^3 - 3n^2 + 8n}{3}. Then, P(1)=2P(1) = 2 and P(n+1)P(n)=n2n+2P(n+1) - P(n) = n^2 - n + 2 and we can prove the following claim:

Claim: Let SS be a set consisting of nn points in the space, no 4 among them lying on a same plane. Then the number of subsets of SS which can be obtained as an intersection of SS with some half space equals the number P(n)P(n).

A proof of this claim can be obtained as for the proof of Lemma 1 above by replacing the plane by the space and straight lines by planes. Thus the answer to this problem is given by P(10)=260P(10) = 260.

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.