Japan Mathematical Olympiad First Round

[260].
First, let us explain some terminologies used in the sequel.
For sets $A$ and $B$, we denote by $A \setminus B$ the set of those elements in $A$ not in $B$.
For a finite set $A$, we denote by $|A|$ the number of elements in $A$. For a mapping $F: A \to B$ and for $b \in B$, we denote by $F^{-1}(b)$ the set $\{a \in A \mid F(a) = b\}$. We call a mapping $F: A \to B$ surjective if for every $b \in B$ the set $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 $S$ be a subset of a plane consisting of $n$ points, no 3 among them lie on a same straight line. Then the number of subsets of $S$ which can be obtained as an intersection of $S$ with some half-plane is $n^2 - n + 2$.

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

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

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

We now prove the following:

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

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

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

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

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

Claim: Let $S$ be a set consisting of $n$ points in the space, no 4 among them lying on a same plane. Then the number of subsets of $S$ which can be obtained as an intersection of $S$ with some half space equals the number $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) = 260$.