---
title: "東京大学大学院　情報理工入試過去問（数学）解答・２０２０年　第三問"
tags: u-tokyo, exam
---

<style>
.markdown-body h1 > span:last-child{
font-size: 18pt;
float: right;
width: 100%;
text-align: right;
border-bottom: 1pt #EEE solid;
padding-bottom: 5pt;
margin-bottom: 5pt
}

.markdown-body h1{
border: none;
}

.markdown-body h2{
padding-top: 8px;
padding-left: 5px;
color: black;
background-color: #F2D7D9;
z-index: 1;
}

.markdown-body h3{
padding: 5px 0 5px 5px;
background-color: #D3CEDF
}

.markdown-body h4{
position: relative;
line-height: 28pt;
padding-left: 5px;
color: #FFFFFF;
font-size: 13pt;
background-color: #9CB4CC;
}

/* Pallete #F2D7D9 #D3CEDF #9CB4CC #748DA6 */
</style>

<!-- Probability & Statistics Related -->
$$
\newcommand{\prob}[1]{\mathrm{P}(#1)}
\newcommand{\probsub}[2]{\mathrm{P}_{#1}(#2)}
\newcommand{\func}[2]{\mathrm{#1}(#2)}
\newcommand{\funcsub}[3]{\mathrm{#1}_{#2}(#3)}
\newcommand{\excp}[1]{\mathrm{E}(#1)}
$$

<!-- Linear Algebra Related -->
$$
\require{boldsymbol}
\newcommand{\vec}[1]{\boldsymbol{#1}}
\newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\rank}[1]{\mathrm{rank}(#1)}
\newcommand{\nobj}[3]{#1_1{#3\;} #1_2{#3} \;\ldots\; {#3} #1_#2}
\newcommand{\nobjsuf}[4]{#1_1#3{#4\;} #1_2#3{#4\;} \;\ldots\; {#4\;} #1_#2#3}
\newcommand{\norm}[1]{\| #1 \|}
\newcommand{\trps}[1]{#1^{\moveleft{1.5px}{\raise{2px}{\mathrm{T}}}}}
\newcommand{\inv}[1]{#1^{-1}}
$$

# 東京大学大学院　情報理工入試過去問（数学）<br><span style="float: right;">解答・２０２０年　第三問</span>

+ こちらの解答は非公式に作成されており、大学院側に認められたものではありません。正確性についての保証は致しかねます。
+ 問題本文は研究科のウェブサイトから見ることができます。
+ 満足出来た解答でしたらコメントしていただけると幸いです。

## ２０２０年　第三問
First we find the formula for $P_n(r)$ in question (3) *then* use it to solve (1) and (2).

### (3) Find formula to $\mathrm{P}_n(r)$.
Assume the applicant with absolute rank $1$ is at position $k$, where $k \geq r$, so that the order is like:
$$
A_1 - A_2 - \cdots - A_{r-1} - A_r - A_{r+1} - \cdots - A_{k - 1} - A_{k} - A_{k+1} - \cdots - A_{n - 1} - A_{n}
$$

Where $A_k$ is the applicant with the absolute rank $1$.

In order to pick the applicant $A_k$,
the smallest rank applicant within the range $[A_1, A_{k - 1}]$ **must** be in the range $[A_1, A_{r - 1}]$,
or the applicant (or others with higher rank) would be picked,
Deducing the probability to pick $A_k$ being $\displaystyle\frac{r - 1}{k - 1}$ for each $k$.

Since the probability of $k$ being at any position is uniformly distributed, and the restriction $k \geq r$ for the applicant not be rejected unconditionally, we result in the probability

$$
\probsub{n}{r} = \displaystyle \sum^{n}_{k = r} \frac{1}{n} \frac{r - 1}{k - 1} = \frac{r - 1}{n} \sum^{n}_{k = r} \frac{1}{k - 1}.
$$

### (1) Find $\probsub{4}{2}$.
Plug in the parameters to get:
$$
\probsub{4}{2} = \frac{2 - 1}{4} \sum^{4}_{k = 2} \frac{1}{k - 1}
= \frac{1}{4}(\frac{1}{1} + \frac{1}{2} + \frac{1}{3})
= \frac{1}{4} \cdot \frac{6 + 3 + 2}{6} = \frac{11}{24}
$$

### (2) Prove that $\probsub{10}{3} = \frac{2}{10}(\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{9})$.
Plug in the parameters to get:
$$
\probsub{10}{3} = \frac{3 - 1}{10} \sum^{10}_{k = 3} \frac{1}{k - 1}
= \frac{2}{10}(\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{9})
$$

### (4) Find the recursive relation $\probsub{n}{r} = \func{A}{n, r} + \func{B}{n, r}\probsub{n}{r + 1}$
First, we have:
$$
\begin{cases}
\probsub{n}{r} = \displaystyle\frac{r - 1}{n} \sum^{n}_{k = r} \frac{1}{k - 1} = \frac{r - 1}{n}\Big(\frac{1}{r - 1} + \sum^{n}_{k = r + 1} \frac{1}{k - 1}\Big)\\[1em]
\probsub{n}{r + 1} = \displaystyle\frac{r}{n} \sum^{n}_{k = r + 1} \frac{1}{k - 1}
\end{cases}
$$

Then, if we let $s = \displaystyle \sum^{n}_{k = r + 1} \frac{1}{k - 1}$, we get:
$$
\begin{align}
\begin{cases}
\probsub{n}{r} = \displaystyle \frac{r - 1}{n}\Big(s + \frac{1}{r - 1}\Big) \\
\probsub{n}{r + 1} = \displaystyle \frac{r}{n} \cdot s
\end{cases} &\Rightarrow
\begin{cases}
\probsub{n}{r} = \displaystyle \frac{r - 1}{n}\Big(s + \frac{1}{r - 1}\Big) \\
s = \displaystyle \frac{n}{r} \probsub{n}{r + 1}
\end{cases} \\[1em]
&\Rightarrow
\probsub{n}{r} = \displaystyle \frac{r - 1}{n}\Big( \frac{n}{r}\probsub{n}{r + 1} + \frac{1}{r - 1} \Big) \\[1em]
&\color{transparent}{\Rightarrow}\color{transparent}{\probsub{n}{r}} = \displaystyle\frac{r - 1}{r} \probsub{n}{r + 1} + \frac{1}{n}
\end{align}
$$

Resulting in:
$$
\begin{cases}
\func{A}{n, r} = \displaystyle \frac{1}{n} \\
\func{B}{n, r} = \displaystyle \frac{r - 1}{r}
\end{cases}
$$

### (5) Let $q = \frac{r}{n}$. Explain that $\probsub{n}{r} \rightarrow -q\ln(q)$ as $n \rightarrow \infty$.
First, we lay out the formula for convidence.
$$
\probsub{n}{r} = \displaystyle \frac{r - 1}{n} \sum^{n}_{k = r} \frac{1}{k - 1}
$$

----
+ When $q$ is very large, we can approximate $\displaystyle\frac{r - 1}{n} \approx \displaystyle\frac{r}{n} = q$.
+ Let $t = \frac{n}{k}$, and $\frac{1}{n} = dt$ as $n \rightarrow \infty$. Then the sum becomes a Reimman approximation to a integral,
$$
q \displaystyle\int^{1}_q \frac{1}{t}dt = -q \ln{q}
$$