はじめに

日本語のタイトルを書いてるけど、この記事の内容は主に日本語じゃないんだ。時間があれば追記するかも

問題一： https://blog.yexca.net/ja/archives/183

問題二： https://blog.yexca.net/ja/archives/187

問題三：この記事

全部解いてみた感想としては、いろんな専攻共通の数学試験だからかな。線形代数はわからないけど、微積分と確率は、ある結論の証明を誘導したり、何かを理解させたりするような内容がほとんどだった。微積分は弧長パラメータ、線形代数は37%法則（秘書問題）だね。これらの結論を知っていれば解きやすいけど、知らずにゼロから解くのは本当にすごいと思う。少なくとも俺がゼロからだったら、確実に落ちてるわ。

それと、既存の理論がベースだから、答え自体は合ってるはず。過程については……まあ、どうだろうね（笑）

問題

Source: 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$ に入る式を求めよ。

ただし、$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$。各候補者の能力には絶対的な順位がある。面接した人たちの相対的な順位はわかる。面接は一人ずつで、順番はランダム。以下の条件で採用を決める：

• 面接直後に採用・不採用を決める
• 採用が決まれば終了
• 一度不採用にしたら、後から採用はできない
• $n-1$ 人目まで誰も採用しなかったら、最後の人を自動的に採用する

採用戦略（$1 < r \le n$）：

• 最初の $r-1$ 人は無条件で不採用
• それ以降は、これまでの $r-1$ 人の中の最高の人よりも優秀な人が来たら即採用

この戦略で、一番優秀な人を採用できる確率 $P_{n}(r)$ についての問題。

この問題を読んだとき、ビダオ（毕導）の あの科学的に脱単（恋人を作る）する方法の動画 を思い出したよ。動画で紹介されている「37%法則」そのものだね。問題文はそのルールの説明で、最後の設問がその 導出プロセス になってる。

第一問

問題の要約：$P_{4}(2)$ を求めよ。

この式は、一番優秀な人が2人目にいて選ばれる確率、3人目にいて選ばれる確率、4人目にいて選ばれる確率を足したもの。一番優秀な人を選ぶためには、第 $r$ 人目から一番優秀な人までの間に、最初の $r-1$ 人よりも優秀な人が現れてはいけない。ちょっとややこしいから、場合分けして考えよう。

一番優秀な人が1人目の場合：即不採用になるから、選ばれる確率は $0$。

一番優秀な人が2人目の場合：2人目から採用判断が始まる。2人目が一番優秀なんだから、当然1人目よりも優秀。だから確実に選ばれる。確率は $1$。

一番優秀な人が3人目の場合：2つのパターンがある。

1. 2人目が1人目より優秀なら、2人目が採用されてしまう。
2. 2人目が1人目より優秀でなければ、3人目の一番優秀な人が採用される。

だから、この場合に選ばれる確率は $\frac{1}{2}$。

一番優秀な人が4人目の場合：2番目に優秀な人が1人目にいる場合（他にも条件はあるけど、要はそれまでの最高が最初の $r-1$ 人の中にいる必要がある）に一番優秀な人が選ばれる。パターンを全部出すと大変だけど、確率は $\frac{1}{3}$ になる。

以上の4つのケースを合わせて：$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$ 人の中での最高責任者が、最初の2人（$r-1=2$）の中にいなければならない。その確率は $\frac{2}{m-1}$。よって、各 $m$ において一番優秀な人が選ばれる確率は：

一番優秀な人が最初の2人にいるときは選ばれないので、

となり、証明された。

第三問

問題の要約：$n$ 人の候補者に対して、第 $k$ 回目の面接で一番優秀な候補者を採用する確率を求めよ。ただし $r \le k \le n$。

第 $k$ 回目で一番優秀な人を採用するには、まず一番優秀な人が $k$ 番目にいなければならない。その確率は $1/n$。次に、その $k$ 番目の人が採用されるためには、それまでの $k-1$ 人の中の最高責任者が、最初の $r-1$ 人の中にいなければならない。その確率は $\frac{r-1}{k-1}$。したがって、

第四問

問題の要約：以下の漸化式（式は略）において $A$ と $B$ を求めよ。$A, B$ は $n, r$ と定数を用いた式。

よって

まず $B$ を計算すると：

次に $A$ を計算する。両者の違いは $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]$ を求めよ。

上で $P_{n}(r)$ の公式を出したけど、$n$ が十分大きいとき、

したがって、

$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