[math]Tokyo Institute of Technology Entrance Exam, Math, 2019

Problem
Plan
Answer
Commentary
Related problem (in Japanese)
Related link

Problem

Let $H_1, \cdots, H_n$ be distinct $n$-planes in the space. Suppose that the space is divided by $H_1, \cdots, H_n$ into $T(H_1, \cdots, H_n)$ spatial regions. For example, if the coordinates of the space are $(x, y, z)$
$\bullet$ If the plane $x = 0$ is $H_1$, plane $y = 0$ is $H_2$, and plane $z = 0$ is $H_3$, then $T(H_1, H_2, H_3) = 8$ and
$\bullet$ If the plane $x=0$ is $H_1$, the plane $y=0$ is $H_2$ and the plane $x+y = 1$ is $H_3$ then $T(H_1, H_2, H_3) = 7$, and
$\bullet$ If the plane $x = 0$ is $H_1$, the plane $x = 1$ is $H_2$ and the plane $y = 0$ is $H_3$ then $T(H_1, H_2, H_3) = 6$, and
$\bullet$ If the plane $x = 0$ is $H_1$, the plane $y = 0$ is $H_2$, the plane $z = 0$ is $H_3$, the plane $x+y+z = 1$ is $H_4$, then $T(H_1, H_2, H_3, H_4) = 15$.
and
$(1)$ Find the largest possible value of $T(H_1, \cdots, H_n)$ for each $n$.
$(2)$ Find the second largest possible value of $T(H_1, \cdots, H_n)$ for each $n$. However, let $n\geq 2$.
$(3)$ Find the third largest possible value of $T(H_1, \cdots, H_n)$ for each $n$. However, let $n\geq 3$.

Plan

First, consider a line in $1$-dimension (a straight line). When there are $n$ distinct points on the line, the line is divided into $n + 1$ pieces. In the $1$-dimensional case, let $d(n)$ be the maximum number of regions when the number of points is $n$, then $$\begin{cases}d(0) & = & 1\\ d(n) & = & d(n-1) + 1\end{cases}$$ From this we know that $d(n) = n+1\ (n=0, 1, \cdots)$.

Suppose there are more than $2$ lines in two dimensions (planes) that are not parallel to each other, do not intersect at the same $1$ point, and have distinct $n$ lines. If we draw a new line, then $n$ new points will be created and the newly drawn line will be divided into $n+1$ pieces. In other words, each of those $n+1$ line segments divides the existing region into $2$ regions, so $n+1$ new regions are created. When the number of lines is $0$, the region will be $1$, when the number of lines is $1$, the region will be $1+1 = 2$, when the number of lines is $2$, the region will be $1+1+2 = 4$, when the number of lines is $3$, the region will be $1+1+2+3 = 7$.

Number of lines	Number of Areas
$0$	$1$
$1$	$1+1 = 2$
$2$	$1+1+2 = 4$
$3$	$1 + 1 + 2 + 3 = 7$
$4$	$1+1+2+3+4 = 11$
$\cdots$

The number of straight lines and the number of regions in two dimensions.

Let’s write this in an incremental formulation as well. When the number of lines is $n$, the maximum number of regions is $r(n)$, $$\begin{cases}r(0) & = & 1\\ r(n) & = & r(n-1) + d(n-1)\\& = & r(n-1)+n\end{cases}$$ In general, when the number of lines is $n$, the maximum number of regions is $$r(n) = 1+(1+2+3+\cdots + n) = 1+\frac{n(n+1)}{2}$$.

What would happen in $3$ dimensions? Suppose we know the maximum number of regions that can be partitioned by the $n$ planes and we want to know the number of additional regions that will be added when we add the $n+1$ planes. The $n+1$th plane collides with all of the $n$ planes, and the plane is divided into $\displaystyle 1+\frac{n(n+1)}{2}$ number of regions created by the $n$th line. Since each planar region divides the volume region into $2$, the space is divided as shown in the following table for the $3$-dimensional case.

Number of planes	Number of Areas
$0$	$1$
$1$	$1+1=2$
$2$	$1+1+2 = 4$
$3$	$1+1+2+4 = 8$
$4$	$1+1+2+4+7 = 15$
$5$	$1+1+2+4+7+11 = 26$
$6$	$1+1+2+4+7+11+16 = 42$
$\cdots$

The number of planes and the number of regions in three dimensions.

If the number of planes is $n$ and the maximum number of regions is $p(n)$, then $$\begin{cases}p(0) & = & 1\\ p(n) & = & p(n-1) + r(n-1)\\ & = & \displaystyle p(n-1)+1+\frac{n(n+1)}{2}\end{cases}$$ From the above, the maximum value of $T(H_1, \cdots, H_n)$ is $$\begin{eqnarray}p(n) & = & 1+\sum_{i=0}^{n-1}{\left(1+\frac{i(i+1)}{2}\right)} \\ & = & 1+n + \frac{1}{6}\sum_{i=0}^{n-1}{\left(i(i+1)(i+2)-(i-1)i(i+1)\right)}\\ & = & n+1+\frac{1}{6}\cdot (n-1)n(n+1)\\ & = & \frac{n^3+5n+6}{6}\end{eqnarray}$$

Answer

$(1)$ From the above description, we have $\displaystyle \underline{\frac{n^3+5n+6}{6}}$. This is also true for $n = 1$.

$(2)$ If we can divide the space from $(1)$ into $\displaystyle \frac{n^3+5n}{6}$ pieces, it will be the $2$th largest one. First consider the case when $n\geq 4$. $n-1\ \ (n\geq 4)$ planes are arranged in such a way that they are $(1)$-maximal, and consider adding the $n$th plane $H_n$ to it. The number of regions in the first space is $\displaystyle p(n-1) = \frac{(n-1)^3+5(n-1)+6}{6}$ from what is stated in the Plan. When we add $H_n$ here, $H_n$ hits $n-1$ planes, forming $n-1$ straight lines, which we denote by $l_1, l_2, \cdots, l_{n-1}$ in this order. Now we add $H_n$ so that $l_{n-2}$ and $l_{n-1}$ are parallel.

Add a plane so that $l_{n-2}$ and $l_{n-1}$ are parallel.

Then $H_n$ is first divided into $\displaystyle r(n-2) = 1+\frac{(n-2)(n-1)}{2}$ pieces by $l_1, l_2, \cdots, l_{n-2}$, and then $l_{n-1}$ is divided into $d(n-3) = n-2$ pieces by the $l_{n-2}$ other lines, which add this number of regions to $H_n$. Therefore, the number of spaces divided at this time is $$\begin{eqnarray}p(n-1)+r(n-2) + d(n-3) & = & \frac{(n-1)^3+5(n-1)+6}{6}+1+\frac{(n-2)(n-1)}{2}+n-2 \\ & = & \underline{\frac{n^3+5n}{6}}\end{eqnarray}$$, which is smaller than the answer of $(1)$ by $1$, so this is the answer of $(2)$. This value is $3$ when $n = 2$, but this is also true for $n = 2$ since it is realized by taking two parallel planes. Furthermore, when $n = 3$, this value is $7$, which is feasible as shown in the example in the problem statement, and also holds for $n = 3$.

$(3)$ First consider the case when $n\geq 5$. $n-1\ (n\geq 5)$ planes are arranged to take the second largest value of $(2)$ and consider adding the $n$ th plane $H_n$ to it. From $(2)$, the number of regions in this space at this time is $\displaystyle p(n-1)-1 = \frac{(n-1)^3+5(n-1)}{6}$. However, the $n-1$th plane $H_{n-1}$ collides with the remaining $n-2$ planes to form $n-2$-straight lines, which are in turn $l_1, l_2, \cdots, l_{n-2}$. In addition, $l_{n-3}$ and $l_{n-2}$ are assumed to be parallel. We now add $H_n$.

The way this addition is made is crucial.

$H_n$ collides with $n-1$ planes to form $n-1$ straight lines, which are in turn $m_1, m_2, \cdots, m_{n-1}$. Now we add a plane so that $m_{n-4}$ and $m_{n-3}$ are parallel. It should be noted that we do not take $m_{n-2}$ and $m_{n-1}$ to be parallel. Then $H_n$ is divided into $r(n-2)+d(n-3)$ pieces as seen in $(2)$. Therefore, the number of partitions of the space is $$\begin{eqnarray}p(n-1)-1+r(n-2)+d(n-3) & = & \frac{(n-1)^3+5(n-1)}{6}+1+\frac{(n-2)(n-1)}{2}+n-2\\ & = & \underline{\frac{n^3+5n-6}{6}}\end{eqnarray}$$ Since it is even smaller than the answer to $(2)$ by $(1)$, this is the answer to $(3)$. However, $n\geq 5$. Let’s consider $n = 3, 4$ separately. The problem statement is true that when $n = 3$ we can $\displaystyle \frac{3^3+5\cdot 3-6}{6} = 6$. Let us see if we can obtain $\displaystyle \frac{4^3+5\cdot 4-6}{6} = 13$ when $n = 4$.

The number of possible values of $T(H_1, H_2, H_3)$ when $n = 3$ is $(a)\ 4, (b)\ 5, (c)\ 6, (d)\ 8, (e)\ 7$.
When $\ (a)\ T(H_1, H_2, H_3) = 4, 5, 6$, adding $H_4$ will not result in $T(H_1, H_2, H_3, H_4) = 13$ since the number of new spaces added is at most $1+2+3 = 6$.
When $(b)\ T(H_1, H_2, H_3) = 8$, $H_4$ must be $5$ divided by $3$ lines, but the way the $3$ lines divide the plane is either $3$ (all parallel) or $6$ (Two lines are parallel or ($3$ lines intersect at the $1$ point) or only $7$ (see the figure below). Therefore, we cannot have $T(H_1, H_2, H_3, H_4) = 13$ at this time.

When $(c)\ T(H_1, H_2, H_3) = 7$, $H_4$ must be $6$ divided by $3$ straight lines, in which case $2$ straight lines among the $3$ straight lines must be parallel or $3$ straight lines must intersect at the $1$ point. However, when the $2$ lines are parallel, the remaining $1$ lines are also parallel to the other lines. Also, when the $3$ lines intersect at the $1$ point, $T(H_1, H_2, H_3) = 7$ cannot be (see also $n = 3, r = 6$ in the above figure).

From the above, $T(H_1, H_2, H_3, H_4) = 13$ is not possible, and $T(H_1, H_2, H_3, H_4) = 12$ is feasible (for example, $H_1:\ x = 0, H_2:\ y = 0, H_3:\ x+y = 0, H_4:\ z = 2$), we can find the answer; $$\underline{\begin{cases}\displaystyle \frac{n^3+5n-6}{6}\ \ (n = 3, \geq 5)\\ 12 \ (n = 4)\end{cases}}$$

$x = 0, y = 0, x+y = 0, z = 2$, then we can set $T(H_1, H_2, H_3, H_4) = 12$.

Commentary

It is considered to be an incremental problem, but $(3)$ is unusually difficult. If you can understand at least the concept of $(1)$, it will be enough as a review.

$(1)$ Actually, the answer to $$\begin{pmatrix}n \\ 0\end{pmatrix} + \begin{pmatrix}n\\ 1 \end{pmatrix} + \begin{pmatrix}n\\ 2\end{pmatrix} + \begin{pmatrix}n\\3\end{pmatrix} = \frac{n^3+5n+6}{6}$$ It might be interesting to consider various interpretations of this.

$(2)$ If $(1)$ can be solved, the answer can be predicted, but the argument is difficult to prove. The point is not to put the planes parallel but to make the lines formed by intersecting the planes parallel. This idea does not usually come up first.

$(3)$ This is a question of the level of those given in Kyoto University’s special entrance examinations, and it is difficult to solve it within the time limit of the examination room. We would like to consider using $(1), (2)$, but there is a big pitfall in $n = 4$. The question to show that $T(H_1, H_2, H_3, H_4) = 13$ is not possible would be enough to be an entrance exam question for very difficult universities.

Number of lines	Number of Areas
\(0\)	\(1\)
\(1\)	\(1+1 = 2\)
\(2\)	\(1+1+2 = 4\)
\(3\)	\(1 + 1 + 2 + 3 = 7\)
\(4\)	\(1+1+2+3+4 = 11\)
\(\cdots\)

Number of planes	Number of Areas
\(0\)	\(1\)
\(1\)	\(1+1=2\)
\(2\)	\(1+1+2 = 4\)
\(3\)	\(1+1+2+4 = 8\)
\(4\)	\(1+1+2+4+7 = 15\)
\(5\)	\(1+1+2+4+7+11 = 26\)
\(6\)	\(1+1+2+4+7+11+16 = 42\)
\(\cdots\)

Problem

Plan

Answer

Commentary

Related problem (in Japanese)

Related link

コメント