[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2003suuri-j2.pdf~
解答（というより略解）つくりました。適当ですので、補間とか訂正、お願いします。
----
-第１問
--&imgtex($f(X)=\log({\rm det}(X)),X\succ 0$);
--(1)略。
--(2)&imgtex($\Lambda ={\rm diag}(\lambda_1,\lambda_2,\ldots,\lambda_n),(\lambda_i>0)$);
を用いて、
&imgtex($A=P\Lambda P^\top$);と対角化する。
&imgtex($B=I$);なので、~
&imgtex(\[ f(A)+f(B)=f(A)+f(I)=\log{\rm det}(A)=\log \prod_{i=1}^n\lambda_i\]);~
また、
&imgtex(\[ f\left(\frac{A+B}{2}\right) = f\left(P\left(\frac{\Lambda+I}{2}\right)P^\top\right) = f\left(\frac{A+I}{2}\right) = \log\prod_{i=1}^n\left(\frac{\lambda_i+1}{2}\right)\]);~
ここで、相加相乗平均を用いれば~
&imgtex(\[ \lambda_i \leq \left(\frac{\lambda_i+1}{2}\right)^2\]);~
従って、&imgtex($f(A)+f(B)\leq 2f((A+B)/2)$);である。
--(3)&imgtex($B\succ 0$);より、コレスキー分解して&imgtex($B=CC^\top$);。
&imgtex($\tilde A = C^{-1}A(C^\top)^{-1}$);とすれば、~
&imgtex(\[ {\rm det}(AB) = {\rm det}(C\tilde AC^\top CC^\top) =({\rm det}C)^4{\rm det}\tilde A\]);~
&imgtex(\[ {\rm det}\left(\frac{A+B}{2}\right) = {\rm det}\left(C\left(\frac{\tilde A+I}{2}\right)C^\top\right) =({\rm det}C)^2{\rm det}\left(\frac{\tilde A+I}{2}\right)\]);~
となるので、あとは(2)の結果を利用すればよい。
-第２問~
完全順列
-帽子を正しく返してもらえる客の数を&imgtex($X_n$);とし，
&imgtex($X_n=k$);となる確率を&imgtex($p_n(k)$);と表す．
--(1)&imgtex($X_n$);の期待値と分散を計算せよ．
---それぞれの人について自分の帽子が返ってくる確率は&imgtex($1/n$);なので，
&imgtex($E[X_n]=n\cdot 1/n=1$);．
また，&imgtex($E[X_n^2]=n\cdot 1/n+n(n-1)\cdot 1/(n(n-1))=2$);．
よって，&imgtex($V[X_n]=E[X_n^2]-E[X_n]^2=2-1^2=1$);．
--(2)&imgtex(\[p_n(0)=1-\left(1-1/2!+1/3!-\dots +(-1)^{n-1}1/n!\right)\]);となることを示せ．
---&imgtex($n$);番目の人が&imgtex($i(\ne n)$);番目の人の帽子を返してもらったときのことを考える．~
このとき&imgtex($i$);番目の人が&imgtex($n$);番目の人の帽子を返され，他の人も自分の帽子を返されない確率は&imgtex($p_{n-2}(0)$);．
&imgtex($i$);番目の人が&imgtex($n$);番目の人の帽子を返されずに，他の人も自分の帽子を返されない確率は&imgtex($p_{n-1}(0)$);．~
よって，&imgtex($p_n(0)=(n-1)(p_{n-1}(0)+p_{n-2}(0))$);．
よって，&imgtex($p_n(0)=\frac{n-1}{n}(p_{n-1}(0)+p_{n-2}(0))$);．
ここで，&imgtex($p_n(0)=1-\left(1-1/2!+1/3!-\dots +(-1)^{n-1}1/n!\right)$);は上の漸化式を満たし，&imgtex($p_0(0)=1, p_1(0)=0$);を満たすので正しい．
--(3)&imgtex(\[p_n(k)=\frac{1}{k!}p_{n-k}(0)\]);となることを示せ．
---&imgtex($p_{n}(k)={}_nC_k\frac{1}{{}_nP_k}p_{n-k}(0)=\frac{1}{k!}p_{n-k}(0)$);
--(4)&imgtex($p_n(k)\to\frac{1}{k!}e^{-1}\ (n\to\infty)$);となることを示せ．
---&imgtex($\lim_{n\to\infty}p_{n}=e^{-1}$);なので，
&imgtex($p_n(k)=\frac{1}{k!}p_{n-k}(0)\to\frac{1}{k!}e^{-1}$);．
-第３問
--(1)LPの標準形は~
&imgtex(\[ \begin{array}{ll} \min& c^\top x\\ {\rm s.t.}& Ax = b, x\geq 0 \end{array}\]);~
双対形は~
&imgtex(\[ \begin{array}{ll} \max& b^\top y\\ {\rm s.t.}& c \geq A^\top y \end{array}\]);~
本問は~
&imgtex(\[ \begin{array}{ll} \min& b^\top y\\ {\rm s.t.}& c \leq A^\top y \end{array}\]);~
そこで、双対形の双対は標準形であるから、本問を双対標準形と捉えて、その標準系を求めれば、~
&imgtex(\[ \begin{array}{ll} \min &c^\top x \\ {\rm s.t.} &Ax=b,x\geq 0 \end{array}\]);~
となる。~
ここで、&imgtex($c=(1,\ldots,1)^\top,b=(1,\ldots,1)^\top,$);~
&imgtex(\[A= \begin{pmatrix} k&1&\cdots&1\\ &k&\ddots&1\\ &O&\ddots&1\\ & & &k\\ \end{pmatrix}\]);~
である。
--(2)(3)帰納的に
&imgtex(\[ y_{k-m} = \frac{(k-1)^m}{k^{m+1}}\]);~
であることがわかるので、~
&imgtex(\[ \alpha_k = \sum_{m=0}^{k-1}y_{k-m} = 1 - \left(\frac{k-1}{k}\right)^k \to 1 - \mathrm e ^{-1} (k \to \infty )\]);~
単調性は&imgtex($\left(1-1/k\right)^k,\left(1-1/(k+1)\right)^{k+1}$);を二項定理を使い展開し、各係数を比較すればよい。
-第４問
--(1)&imgtex($C$);上の点&imgtex($p$);を
&imgtex($p=(x,a\cos\theta,a\sin\theta)$);
と表現すると、
&imgtex($S$);上では&imgtex($h(p)= (x,f(x)\cos\theta,f(x)\sin\theta)$);となる。
&imgtex($t_p$);を点&imgtex($p$);における接ベクトルとする。
&imgtex(\begin{align*} \frac{\partial}{\partial x}t_p& = ( 1, 0 , 0)\\ \frac{\partial}{\partial \theta}t_p & = ( 0 , -a\sin\theta , a\cos\theta)\end{align*});~
よって、
&imgtex(\[ \left| \frac{\partial}{\partial x}t_p \times \frac{\partial}{\partial \theta}t_p\right| = a\]);~
また、
&imgtex(\begin{align*} \frac{\partial}{\partial x}t_{h(p)}& = ( 1, f'(x)\cos\theta , f'(x)\sin\theta)\\ \frac{\partial}{\partial \theta}t_{h(p)} & = ( 0 , -f(x)\sin\theta , f(x)\cos\theta)\end{align*});~
よって、
&imgtex(\[ \left| \frac{\partial}{\partial x}t_{h(p)} \times \frac{\partial}{\partial \theta}t_{h(p)}\right| = f(x)\sqrt{1+f'(x)^2}\]);~
密度が等いので面素も等しい。従って
&imgtex(\[ a=f(x)\sqrt{1+f'(x)^2}\]);~
--(2)~
&imgtex(\[f' = \pm\sqrt{\frac{a^2}{f^2}-1}\]);~
&imgtex(\[ff' = \pm\sqrt{a^2-f^2}\]);と変形。~
一般解は&imgtex(\[f(x) = \sqrt{a^2-(x+C)^2}\]);~
包絡線&imgtex(\[f(x)=a\]);が特異解になっている。~
解はこれを条件にあうように繋いだもの。~
任意定数&imgtex(\[-a\leq A \leq 0 \leq B \leq a\]);を使って、~
&imgtex(\[f(x)=\left\{\begin{matrix}\sqrt{a^2-(x-A)^2}&(-a<x\leq A)\\a&(A<x<B)\\\sqrt{a^2-(x-B)^2}&(B \leq x<a)\end{matrix}\right.\]);
-第５問
--(1)まず、
&imgtex(${\rm gain}(1,k+1) \geq 0 \Longleftrightarrow {\rm gain}(1,k)+p_k-q_k \geq 0$);
であるから、&imgtex(${\rm gain}(1,k+1) \geq 0$);は1から出発してもし&imgtex($k$);に行けるとするならば、&imgtex($k+1$);にも行ける、ことの必要十分条件。~
また、&imgtex($\sum_{i=1}^Np_i = \sum_{i=1}^Nq_i$);であるから、1から出発して、&imgtex($N$);に行ければ一周できる。~
従って~
一周できる &imgtex($\Longleftrightarrow $);1から&imgtex($2,3,\ldots,N$);に到達できる &imgtex($\Longleftrightarrow \forall i=1,2,\ldots,N \ {\rm gain}(1,i) \geq 0$);
である。
--(2)示すべきは~
&imgtex($\exists i \in \{1,2,\ldots,N\} \ \forall j \in \{1,2,\ldots,N\} {\rm s.t.}\ \ {\rm gain}(i,j)\geq 0 $);~
背理法を用いる。つまり、~
&imgtex($\forall i \in \{1,2,\ldots,N\} \ \exists j \in \{1,2,\ldots,N\} {\rm s.t.} \ \ {\rm gain}(i,j) < 0 $);~
を仮定して、矛盾を導く。~
まず、&imgtex($i_0 = 1$);として、&imgtex($i_0$);に（時計回りで）一番近く&imgtex(${\rm gain}(i_0,j) < 0$);を満たす&imgtex($j$);を&imgtex($i_1 = j$);とする。
以下同様にして、&imgtex($i_k$);に一番近く&imgtex(${\rm gain}(i_k,j) <0$);を満たすものを&imgtex($i_{k+1}=j$);とする。
すると、ある&imgtex($j$);が存在して、
&imgtex($i_{j-1} \leq N,\ 1 \leq i_j$);
となる。このとき、&imgtex($i_0=1$);であるから、ある&imgtex($k$);が存在して
&imgtex($i_k \leq i_j < i_{k+1}$);
となる。以下&imgtex($i_k=i_j$);と&imgtex($i_k < i_j$);の二通りの場合に分けて考える。
---(ァ)&imgtex($i_k=i_j$);の場合
このときは&imgtex(${\rm gain}$);の和を考えると、矛盾が生じる。つまり、
&imgtex(${\rm gain}(i_k,i_{k+1}) +{\rm gain}(i_{k+1},i_{k+2}) + \cdots +{\rm gain}(i_{j-1},i_k) = \sum_{i=1}^N(p_i-q_i)$);
であるが、左辺は負であるが、右辺は問題の前提より零。これは矛盾。
---(イ)&imgtex($i_k < i_j$);の場合
ここで、&imgtex($i_j$);は&imgtex(${\rm gain}(i_{j-1},i_j) < 0$);を満たす一番近いものを選んできているので&imgtex(${\rm gain}(i_{j-1},i_k) \geq 0$);である。
よって、&imgtex(${\rm gain}(i_k,i_j) < 0$);であるが、これは&imgtex($i_j < i_{k+1}$);に反する。
（&imgtex($i_{k+1}$);は&imgtex(${\rm gain}(i_k,i_{k+1}) < 0$);を満たす一番近いもののはずである。）
したがって、矛盾。~
以上より、
&imgtex($\exists i \in \{1,2,\ldots,N\} \ \forall j \in \{1,2,\ldots,N\} {\rm s.t.}\ \ {\rm gain}(i,j)\geq 0$);
であることが分かった。
-- 別解~
&imgtex(\[\mathrm{gain}(1,k)=\min_j \mathrm{gain}(1,j)\]);と&imgtex(\[k\]);をとれば、~
&imgtex(\[\forall j.\mathrm{gain}(k,j) = \mathrm{gain}(1,j)-\mathrm{gain}(1,k) \geq 0\]);なので~
&imgtex(\[k\]);から一周できる。
----
こめんと
#comment
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
