院試過去問 2003年度専門科目数理のバックアップ(No.4)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
院試過去問 2003年度専門科目数理へ行く。
- 1 (2008-08-13 (水) 17:33:49)
- 2 (2008-08-13 (水) 18:44:41)
- 3 (2008-08-18 (月) 17:50:42)
- 4 (2008-08-18 (月) 23:12:12)

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
解答（というより略解）つくりました。適当ですので、補間とか訂正、お願いします。

第１問
- $f(X)=\log({\rm det}(X)),X\succ 0$

(1)略。

(2) $\Lambda ={\rm diag}(\lambda_1,\lambda_2,\ldots,\lambda_n),(\lambda_i>0)$ を用いて、 $A=P\Lambda P^\top$ と対角化する。なので、
$f(A)+f(B)=f(A)+f(I)=\log{\rm det}(A)=\log \prod_{i=1}^n\lambda_i$
また、 $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)$
ここで、相加相乗平均を用いれば
$\lambda_i \leq \left(\frac{\lambda_i+1}{2}\right)^2$
従って、 $f(A)+f(B)\leq 2f((A+B)/2)$ である。

(3) $B\succ 0$ より、コレスキー分解して $B=CC^\top$ 。 $\tilde A = C^{-1}A(C^\top)^{-1}$ とすれば、
${\rm det}(AB) = {\rm det}(C\tilde AC^\top CC^\top) =({\rm det}C)^4{\rm det}\tilde A$
${\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)の結果を利用すればよい。

第２問
完全順列
帽子を正しく返してもらえる客の数をとし，となる確率をと表す．
- (1)の期待値と分散を計算せよ．
  - それぞれの人について自分の帽子が返ってくる確率はなので， $E[X_n]=n\cdot 1/n=1$ ．また， $E[X_n^2]=n\cdot 1/n+n(n-1)\cdot 1/(n(n-1))=2$ ．よって，．
- (2)となることを示せ．
  - 番目の人が $i(\ne n)$ 番目の人の帽子を返してもらったときのことを考える．
    このとき番目の人が番目の人の帽子を返され，他の人も自分の帽子を返されない確率は $p_{n-2}(0)$ ．番目の人が番目の人の帽子を返されずに，他の人も自分の帽子を返されない確率は $p_{n-1}(0)$ ．
    よって， $p_n(0)=(n-1)(p_{n-1}(0)+p_{n-2}(0))$ ．ここで， $p_n(0)=1-\left(1-1/2!+1/3!-\dots +(-1)^{n-1}1/n!\right)$ は上の漸化式を満たし，を満たすので正しい．
- (3)となることを示せ．
  - $p_{n}(k)={}_nC_k\frac{1}{{}_nP_k}p_{n-k}(0)=\frac{1}{k!}p_{n-k}(0)$
- (4)となることを示せ．
  - $\lim_{n\to\infty}p_{n}=e^{-1}$ なので， $p_n(k)=\frac{1}{k!}p_{n-k}(0)\to\frac{1}{k!}e^{-1}$ ．

第３問
- (1)LPの標準形は
  $\begin{array}{ll} \min& c^\top x\\ {\rm s.t.}& Ax = b, x\geq 0 \end{array}$
  双対形は
  $\begin{array}{ll} \max& b^\top y\\ {\rm s.t.}& c \geq A^\top y \end{array}$
  本問は
  $\begin{array}{ll} \min& b^\top y\\ {\rm s.t.}& c \leq A^\top y \end{array}$
  そこで、双対形の双対は標準形であるから、本問を双対標準形と捉えて、その標準系を求めれば、
  $\begin{array}{ll} \min &c^\top x \\ {\rm s.t.} &Ax=b,x\geq 0 \end{array}$
  となる。
  ここで、 $c=(1,\ldots,1)^\top,b=(1,\ldots,1)^\top,$
  $A= \begin{pmatrix} k&1&\cdots&1\\ &k&\ddots&1\\ &O&\ddots&1\\ & & &k\\ \end{pmatrix}$
  である。

(2)(3)帰納的に $y_{k-m} = \frac{(k-1)^m}{k^{m+1}}$
であることがわかるので、
$\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 )$
単調性は $\left(1-1/k\right)^k,\left(1-1/(k+1)\right)^{k+1}$ を二項定理を使い展開し、各係数を比較すればよい。

第４問
- (1)上の点を $p=(x,a\cos\theta,a\sin\theta)$ と表現すると、上では $h(p)= (x,f(x)\cos\theta,f(x)\sin\theta)$ となる。を点における接ベクトルとする。 $\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*}$
  よって、 $\left| \frac{\partial}{\partial x}t_p \times \frac{\partial}{\partial \theta}t_p\right| = a$
  また、 $\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*}$
  よって、 $\left| \frac{\partial}{\partial x}t_{h(p)} \times \frac{\partial}{\partial \theta}t_{h(p)}\right| = f(x)\sqrt{1+f'(x)^2}$
  密度が等いので面素も等しい。従って $a=f(x)\sqrt{1+f'(x)^2}$
- (2)
  $f' = \pm\sqrt{\frac{a^2}{f^2}-1}$
  $ff' = \pm\sqrt{a^2-f^2}$ と変形。
  一般解は $f(x) = \sqrt{a^2-(x+C)^2}$
  包絡線が特異解になっている。
  解はこれを条件にあうように繋いだもの。
  任意定数 $-a\leq A \leq 0 \leq B \leq a$ を使って、
  $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)まず、 ${\rm gain}(1,k+1) \geq 0 \Longleftrightarrow {\rm gain}(1,k)+p_k-q_k \geq 0$ であるから、 ${\rm gain}(1,k+1) \geq 0$ は1から出発してもしに行けるとするならば、にも行ける、ことの必要十分条件。
  また、 $\sum_{i=1}^Np_i = \sum_{i=1}^Nq_i$ であるから、1から出発して、に行ければ一周できる。
  従って
  一周できる $\Longleftrightarrow$ 1から $2,3,\ldots,N$ に到達できる $\Longleftrightarrow \forall i=1,2,\ldots,N \ {\rm gain}(1,i) \geq 0$ である。
- (2)示すべきは
  
  背理法を用いる。つまり、
  
  を仮定して、矛盾を導く。
  まず、として、に（時計回りで）一番近くを満たすをとする。以下同様にして、に一番近くを満たすものをとする。すると、あるが存在して、となる。このとき、であるから、あるが存在してとなる。以下との二通りの場合に分けて考える。
  - (ァ)の場合このときは ${\rm gain}$ の和を考えると、矛盾が生じる。つまり、 ${\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)$ であるが、左辺は負であるが、右辺は問題の前提より零。これは矛盾。
  - (イ)の場合ここで、は ${\rm gain}(i_{j-1},i_j) < 0$ を満たす一番近いものを選んできているので ${\rm gain}(i_{j-1},i_k) \geq 0$ である。よって、 ${\rm gain}(i_k,i_j) < 0$ であるが、これは $i_j < i_{k+1}$ に反する。（ $i_{k+1}$ は ${\rm gain}(i_k,i_{k+1}) < 0$ を満たす一番近いもののはずである。）したがって、矛盾。
    以上より、 $\exists i \in \{1,2,\ldots,N\} \ \forall j \in \{1,2,\ldots,N\} {\rm s.t.}\ \ {\rm gain}(i,j)\geq 0$ であることが分かった。
- 別解
  $\mathrm{gain}(1,k)=\min_j \mathrm{gain}(1,j)$ とをとれば、
  $\forall j.\mathrm{gain}(k,j) = \mathrm{gain}(1,j)-\mathrm{gain}(1,k) \geq 0$ なので
  から一周できる。

こめんと

院試過去問 2003年度 専門科目 数理 のバックアップ(No.4)

院試過去問 2003年度専門科目数理のバックアップ(No.4)