前言
即便寫了日文標題，這篇文章的主體並非日文。有時間的話可能會補充
題目一： https://blog.yexca.net/zh-tw/archives/183
題目二： https://blog.yexca.net/zh-tw/archives/187
題目三：本文
全部寫下來的感覺是，可能因為是多個專業共用的數學試題吧，線性代數不清楚，但微積分與機率論幾乎都是在引導考生完成某項結論的證明或理解某個概念。其中微積分是關於弧長參數化，機率論則是 37% 法則。如果原本就知道這些結論會非常好解題，若事先沒學過就能當場做出來的人真的很厲害。至少讓我從零開始思考的話，肯定會掛掉。
同時因為是已有的理論，解題答案應該是對的，至於過程嘛，就不確定了 XD
題目
來源： https://www.i.u-tokyo.ac.jp/edu/entra/examarchive.shtml
題目版權屬於東京大學所有，僅為了方便閱讀而引用，無營利行為
現有 $n$ 名打工候選人進行面試，希望能從中錄用最合適的人選。假設 $n \ge 2$。候選人預先已定有排名 $1$、排名 $2$、$\cdots$、直到排名 $n$ 的絕對排名，而對於已經面試過的候選人，可以得知他們之間的相對排名。面試依序逐一進行，但候選人出現的順序是隨機決定的，事前無法得知。在錄用過程中，將根據已面試候選人之間的相對排名來決定是否錄用，並須遵守以下條件：
- 在每位候選人面試後，必須立即決定是否錄用。
- 一旦決定錄用某位候選人，錄用過程即告結束。
- 無法錄用過去已被拒絕的候選人。
- 若到第 $n-1$ 次面試都未錄用任何人，則無條件錄用第 $n$ 位候選人。
在錄用打工人員時採取如下策略。假設 $1 < r \le n$：
- 到第 $r-1$ 次面試為止，無條件拒絕所有候選人。
- 之後的面試中，若候選人優於前 $r-1$ 人中的最佳候選人（相對排名 $1$），則予以錄用。
在此策略下，錄用絕對排名第 $1$ 之候選人的機率記為 $P_{n}(r)$。請回答以下問題：
（１）求 $P_{4}(2)$。
（２）證明 $P_{10}(3)=\frac{2}{10}(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{9})$。
（３）對於 $n$ 名候選人，求在第 $k$ 次面試錄用絕對排名第 $1$ 候選人的機率。其中 $r \le k \le n$。
（４）在以下遞迴式中，求出填入 $A, B$ 的表達式。
$$ P_{n}(r)=A+B\times P_{n}(r+1) $$其中 $A, B$ 為由 $n, r$ 及常數構成的表達式。
（５）設 $q=r/n$。說明當 $n$ 足夠大時，$P_{n}(r)$ 可以用 $-q\ln(q)$ 來近似。進而求出使 $-q\ln(q)$ 取得最大值的 $q\in (0,1]$ 之值。其中 $\ln$ 表示自然對數。
中文解答
背景翻譯：現希望在面試 $n$ 個候選人後找到最佳人選。其中 $n \ge 2$。每個候選人的能力等級是確定的（最好的、次好的、⋯、最差的）。已經面試過的候選人就可以知道這些人的相對能力等級。面試是一個人接一個人進行的，但面試順序是隨機的，事前不知道。招聘單位將根據已經面試過的人的相對能力等級來確定錄用誰，並滿足以下條件：
- 每個候選人面試後立即確定是否錄用
- 一旦決定錄用某人，則所有面試結束
- 過去未錄用的人不會再錄用
- 如果只剩一人，前面的人都不合格，則直接錄用此人
招聘單位採用以下策略，其中 $1 < r \le n$：
- 前 $r-1$ 人的面試直接拒絕
- 之後的面試中，若有人優於前 $r-1$ 人中的最優者，則錄用
在這個策略中，選中最好的候選人的機率表示為 $P_{n}(r)$，回答以下問題：
這題讀完之後就想到了畢導（畢導THU）的 那個如何科學有效脫單影片 ，和影片中的方法一樣，也就是 $37\%$ 法則。題目就是該法則的描述，最後一題就是其 求解過程 。
第一小題
題目翻譯：求 $P_{4}(2)$
$$ \begin{align} P_{4}(2) &=\frac{1}{4}+\frac{1}{4} \times \frac{1}{2} + \frac{1}{4} \times \frac{1}{3} \\ &=\frac{1}{4}+\frac{1}{8}+\frac{1}{12} \\ &=\frac{11}{24} \end{align} $$這裡的算式分別代表：最優秀的人在第二位時被選中的機率、在第三位時被選中的機率，以及在第四位時被選中的機率。為了選中最優秀的人，必須保證從第 $r$ 個人開始到最優秀的人之間，沒有人比前 $r-1$ 人更優秀。這句話有點繞，我們分情況討論：
假設最優秀的人是第一人，則直接被淘汰，選中的機率為 $0$。
假設最優秀的人是第二人，由於從第二人開始決定是否錄用，且前面的人不可能比最優秀的人更優秀，所以選中的機率是 $1$。
假設最優秀的人是第三人，這時有兩種情況：
- 如果第二個人比第一個人優秀，那麼最優秀的人（第三人）不會被錄用（因為第二人會先被錄用）。
- 如果第二個人沒有第一個人優秀，那麼最優秀的人將會被錄用。
所以該情況選中的機率是 $\frac{1}{2}$。
假設最優秀的人是第四人，這時只有在前三人中，最優秀的是出現在前 $r-1$ 位（即第一位）時，才能保證第四人被錄用。也就是說，前三個人中的相對第一名必須落在第一位，機率是 $\frac{1}{3}$。
綜合以上四種情況：$P=\frac{1}{4} \times 0+\frac{1}{4} \times 1 +\frac{1}{4} \times \frac{1}{2} + \frac{1}{4} \times \frac{1}{3}$。
第二小題
題目翻譯：證明 $P_{10}(3)=\frac{2}{10}(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{9})$
假設最優秀的人在第 $m$ 位 ($3 \le m \le 10$)。為了保證選中最優秀的人，前 $m-1$ 個人中最優秀的那個人必須出現在前兩個人中（即前 $r-1$ 人中），其機率為 $\frac{2}{m-1}$。因此，選中最優秀的人的總機率為：
$$ \begin{align} P =&\frac{1}{10} \times \frac{2}{2}+\frac{1}{10} \times \frac{2}{3}+\frac{1}{10} \times \frac{2}{4}+\frac{1}{10} \times \frac{2}{5}+\\ &\frac{1}{10} \times \frac{2}{6}+\frac{1}{10} \times \frac{2}{7}+\frac{1}{10} \times \frac{2}{8}+\frac{1}{10} \times \frac{2}{9} \\ =&\frac{1}{10}(\frac{2}{2}+\frac{2}{3}+\frac{2}{4}+\frac{2}{5}+\frac{2}{6}+\frac{2}{7}+\frac{2}{8}+\frac{2}{9}) \\ =&\frac{2}{10}(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}) \end{align} $$當最優秀的人在前兩位時，根據策略無法選中他，所以：
$$ \begin{align} P_{10}(3) &=\frac{1}{10} \times 0 + \frac{1}{10} \times 0 + P \\ &=P \end{align} $$原命題得證。
第三小題
題目翻譯：對於 $n$ 個候選人，求在第 $k$ 次面試中錄用最優候選人的機率，其中 $r \le k \le n$。
若要在第 $k$ 次面試錄取最優秀的人，首先最優秀的人必須在第 $k$ 位（機率 $\frac{1}{n}$）。其次，為了保證能進行到第 $k$ 次面試且選中他，前 $k-1$ 個人中的相對第一名必須出現在前 $r-1$ 人中，其機率為 $\frac{r-1}{k-1}$。因此：
$$ P=\frac{1}{n} \times \frac{r-1}{k-1} $$第四小題
題目翻譯：對於以下的遞迴式（公式略），求 $A$ 和 $B$。其中 $A, B$ 是以 $n, r$ 和常數表示的算式。
$$ \begin{align} P_{n}(r) &= \frac{1}{n}(\frac{r-1}{r-1}+\frac{r-1}{r}+\frac{r-1}{r+1}+\cdots+\frac{r-1}{n-1}) \\ &=\frac{1}{n} \sum_{i=r-1}^{n-1} \frac{r-1}{i} \\ &= \frac{r-1}{n}\sum_{i=r-1}^{n-1}\frac{1}{i} \end{align} $$同理：
$$ P_{n}(r+1)=\frac{r}{n}\sum_{i=r}^{n-1}\frac{1}{i} $$首先計算 $B$：
$$ \frac{r}{n} \times B = \frac{r-1}{n} \\ B = \frac{r-1}{r} $$接著計算 $A$，因為 $P_{n}(r)$ 比 $B \times P_{n}(r+1)$ 多了 $i=r-1$ 這一項： $\frac{r-1}{n} \times \frac{1}{r-1} = \frac{1}{n}$
所以 $A = \frac{1}{n}$。
第五小題
題目翻譯：設 $q=r/n$，當 $n$ 足夠大時，解釋 $P_{n}(r)$ 可以用 $-q\ln(q)$ 近似。進而求出 $-q\ln(q)$ 的極大值所對應的 $q\in (0,1]$。其中 $\ln$ 表示自然對數。
上方已經給出了 $P_{n}(r)$ 的公式，當 $n$ 足夠大時：
$$ \sum_{i=r-1}^{n-1}\frac{1}{i} \approx \int_{r}^{n} \frac{1}{x} dx = \ln(n)-\ln(r)= \ln(\frac{n}{r}) $$所以：
$$ P_{n}(r) \approx \frac{r}{n}\ln(\frac{n}{r}) = q\ln(\frac{1}{q}) = -q\ln(q) $$令 $y=-q\ln(q)$，則 $\frac{\mathrm{d} y}{\mathrm{d} q} = -\ln(q)-1$。令 $\frac{\mathrm{d} y}{\mathrm{d} q}=0$，得 $q=\frac{1}{e}$。
也就是當 $q=\frac{1}{e}$ 時，$-q\ln(q)$ 取最大值。
這題我也不完全理解其嚴密性，反正近似就對了，具體和 畢導影片中的公式 也有一點點出入，不想深究了。
Wrote with ChatGPT