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 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 which can be obtained as an intersection of with some half space.
Solution
[260].
First, let us explain some terminologies used in the sequel.
For sets and , we denote by the set of those elements in not in .
For a finite set , we denote by the number of elements in . For a mapping and for , we denote by the set . We call a mapping surjective if for every the set 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 be a subset of a plane consisting of points, no 3 among them lie on a same straight line. Then the number of subsets of which can be obtained as an intersection of with some half-plane is .
Proof:
Fix an -coordinate system in the plane. Then we claim that a subset of the set satisfies the condition of Lemma 1 if and only if the following condition is satisfied:
There exists a linear function of 2 variables such that
Here, we mean by the value , where are the coordinates of the point . If satisfies the property stated above, we will say that cuts off from .
Let us prove the claim made above by induction on the number of points of . Clearly, the claim holds if . So, suppose the claim is valid for and show that it holds for . Let us represent as . Denote by the set of all those subsets of which satisfy the condition of Lemma 1. Define to be the set , and define in the same way. Define a mapping by setting for . It is easy to see that holds for any .
Let and let be a linear function which cuts off from . If , then for any sufficiently small , the linear function cuts off from . Therefore, , while if , the function for sufficiently small will cut off from so that . Therefore, we can conclude that the mapping defined above is surjective, and for every we have that equals either 1 or 2.
We now prove the following:
Lemma 2. For , the following 2 conditions are mutually equivalent:
(1) There exists a linear function which cuts off from and for which .
(2) .
Proof: It follows from what we stated above that the condition (2) is equivalent to the statement . Now, if (1) is satisfied, for a sufficiently small , the function cuts off from , and the function cuts off from . Therefore, we have and (2) is satisfied.
Conversely, suppose (2) is satisfied. Let and be linear functions cutting off , , respectively, from . Let . Then the linear function takes the value 0 at the point , and cuts off from , since . Therefore, (1) is satisfied. Thus, Lemma 2 is proved.
Let us continue with the proof of Lemma 1. Since is surjective, Lemma 2 implies that the number coincides with the number of 's satisfying the condition (1) of Lemma 2. We may assume that the -coordinates of the points are all distinct, by changing the coordinate system, if necessary. Let be a real number different from the -coordinate of the point . For each , let be the point of intersection of the lines and . Then, from the assumption that no 3 points from the set are colinear it follows that numbers are all distinct. We also see that the fact satisfies the condition (1) of Lemma 2 is equivalent to the statement that
for some linear function of 1 variable. Total number of such 's is , and the induction hypothesis says that so that we have , which proves the assertion of Lemma 1.
Now, let . Then, and and we can prove the following claim:
Claim: Let be a set consisting of points in the space, no 4 among them lying on a same plane. Then the number of subsets of which can be obtained as an intersection of with some half space equals the number .
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 .