院試過去問 2006年度 専門科目 数理 の変更点

http://ap2007.nakano.net/wiki/index.php?%E9%99%A2%E8%A9%A6%E9%81%8E%E5%8E%BB%E5%95%8F%202006%E5%B9%B4%E5%BA%A6%20%E5%B0%82%E9%96%80%E7%A7%91%E7%9B%AE%20%E6%95%B0%E7%90%86

[ トップ ]   [ 編集 | 差分 | バックアップ | 添付 | リロード ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]   [ リンク元 ]

• 追加された行はこの色です。
• 削除された行はこの色です。
• 院試過去問 2006年度 専門科目 数理 へ行く。
• 院試過去問 2006年度 専門科目 数理 の差分を削除

---

[[院試勉強会]]

http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2006suuri-j.pdf~
- 第一問~
&imgtex($n\times n$);正方行列&imgtex($C_n$);を以下のように定義する．~
&imgtex(\begin{align*}C_n=\begin{pmatrix}1&1&0&\dots&0\\0&1&1&\ddots&\vdots\\\vdots&\ddots&\ddots&\ddots&0\\0&&\ddots&1&1\\1&0&\dots&0&1\end{pmatrix}\end{align*});~
--(1)&imgtex($n$);が偶数ならば，&imgtex($C_n$);は逆行列を持たないことを示せ．
---&imgtex($n$);が偶数ならば，~
&imgtex(\begin{align*}\begin{pmatrix}1&1&0&\dots&0\\0&1&1&\ddots&\vdots\\\vdots&\ddots&\ddots&\ddots&0\\0&&\ddots&1&1\\1&0&\dots&0&1\end{pmatrix}\begin{pmatrix}1\\-1\\\vdots\\1\\-1\end{pmatrix}=\begin{pmatrix}0\\0\\\vdots\\0\\0\end{pmatrix}\end{align*});~
より逆行列を持たない．
--(2)&imgtex($n$);が奇数ならば，&imgtex($C_n$);の列ベクトルの集合は線型独立であることを示せ．
---&imgtex($C_1=1$);．&imgtex($n$);が3以上の奇数のとき，~
&imgtex(\begin{align*}|C_{n}|&=\left|\begin{matrix}1&1&0&\dots&0\\0&1&1&\ddots&\vdots\\\vdots&\ddots&\ddots&\ddots&0\\0&&\ddots&1&1\\1&0&\dots&0&1\end{matrix}\right|\\&=\left|\begin{matrix}1&1&&&\\&1&1&&\\&&\ddots&\ddots&\\&&&1&1\\&&&&1\end{matrix}\right|+\left|\begin{matrix}1&&&&\\1&1&&&\\&\ddots&\ddots&&\\&&1&1&\\&&&1&1\end{matrix}\right|=2\end{align*});~
よって，線型独立である．
--(3)&imgtex($C_n$);が逆行列を持つならば,
&imgtex($2C_n^{-1}$);は整数行列であることを示せ．
---&imgtex($C_n$);は整数行列なので，余因子行列&imgtex($\tilde{C}_n$);も整数行列．(1),(2)より逆行列を持つならば&imgtex($n$);は奇数であり&imgtex($|C_n|=1,2$);であるので，逆行列の2倍&imgtex($2C_n^{-1}=2\tilde{C}_n/|C_n|$);は整数行列．
--(4)無向グラフ&imgtex($G$);の枝の部分集合で，対応する&imgtex($M(G)$);の列ベクトルの集合が&imgtex($H$);の基底となっているものをすべて挙げよ．
---(1)(2)より全域木に1本付け加えて奇数ループを一つつくればよい．
よって，~
&imgtex($\{e_1,e_2,e_3,e_4,e_5\},\{e_1,e_2,e_3,e_4,e_6\},\{e_1,e_2,e_3,e_5,e_6\},\{e_1,e_2,e_4,e_5,e_6\}$);~
の4通り．
----
-第2問~
--実数の組&imgtex($(x_i,y_i)$);からなるデータに対して&imgtex($y=\beta_1 x+\beta_2 $);を最小2乗法で当てはめることにより，
&imgtex($\beta_1,\beta_2$);の推定量&imgtex($\hat{\beta}_1,\hat{\beta}_2$);を求める．ここで，~
&imgtex(\begin{align*}\bm{y}=\begin{pmatrix}y_1\\y_2\\\vdots\\y_n\end{pmatrix},X=\begin{pmatrix}x_1&1\\x_2&1\\\vdots&\vdots\\x_n&1\end{pmatrix},\hat{\bm{\beta}}=\begin{pmatrix}\hat{\beta}_1\\\hat{\beta}_2\end{pmatrix}\end{align*});~
とおく．ただし，&imgtex($X$);の階数は2であるものとする．このとき，&imgtex($\hat{\bm{\beta}}$);を求めよ．
また，~
&imgtex(\begin{align*}X\hat{\bm{\beta}}=P\bm{y}\end{align*});~
を満たす，&imgtex($X$);により決まる&imgtex($n\times n$);行列&imgtex($P$);を求め，&imgtex($P^2=P, P^{\top}=P$);が成立することを示せ．
---&imgtex($e=(\bm{y}-X\hat{\bm{\beta}})^{\top}(\bm{y}-X\hat{\bm{\beta}})$);とおくと，&imgtex($\hat{\beta}_1,\hat{\beta}_2$);は&imgtex($e$);を最小化するようなものなので，~
&imgtex(\begin{align*}\frac{\partial e}{\partial \hat{\beta}_1}&=\sum_{i}2x_i(y_i-x_i\hat{\beta}_i-\hat{\beta}_2)=0\\\frac{\partial e}{\partial \hat{\beta}_2}&=\sum_{i}2(y_i-x_i\hat{\beta}_i-\hat{\beta}_2)=0\end{align*});~
が成立する．この連立方程式を解けば，~
&imgtex(\begin{align*}\hat{\beta}_1&=\frac{n\sum_{i=1}^n x_iy_i-(\sum_{i=1}^n x_i)(\sum_{i=1}^n y_i)}{n\sum_{i=1}^n x_i^2-(\sum_{i=1}^n x_i)^2},\\\hat{\beta_2}&=\frac{(\sum_{i=1}^nx_i^2)(\sum_{i=1}^n y_i)-(\sum_{i=1}^n x_iy_i)(\sum_{i=1}^n x_i)}{n\sum_{i=1}^n x_i^2-(\sum_{i=1}^n x_i)^2}.\end{align*});~
これより，~
&imgtex(\begin{align*}P_{ij}=\frac{nx_ix_j-(\sum_{k=1}^n x_k)(x_i+x_j)+\sum_{k=1}^n x_k^2}{n\sum_{k=1}^n x_k^2-(\sum_{k=1}^n x_k)^2}\end{align*});~
&imgtex($P_{ij}=P_{ji}$);は明らか．~
&imgtex($(P^2)_{ij}=\sum_{k=0}^n P_{ik}P_{kj}=P_{ij}$);より&imgtex($P^2=P$);．~
~
このように解くと&imgtex($P^2$);の計算で死ぬことになるので擬似逆行列を使ってきれいに解くべき．~
&imgtex($e=|\bm{y}-X\hat{\bm{\beta}}|^2$);を最小化するのは，&imgtex($\nabla e=2X^{\top}(\bm{y}-X\hat{\bm{\beta}})=0$);の時．すなわち，&imgtex($X^{\top}\bm{y}=X^{\top}X\hat{\bm{\beta}}$);，&imgtex($\hat{\bm{\beta}}=(X^{\top}X)^{-1}X^{\top}y$);．~
さらに左から&imgtex($X$);を掛けると，&imgtex($X\hat{\beta}=X(X^{\top}X)^{-1}X^{\top}\bm{y}$);となるので，&imgtex($P=X(X^{\top}X)^{-1}X^{\top}$);．~
これより，
&imgtex($P^2=X(X^{\top}X)^{-1}X^{\top}X(X^{\top}X)^{-1}X^{\top}=X(X^{\top}X)^{-1}X^{\top}=P$);，~
&imgtex($P^{\top}=\{X(X^{\top}X)^{-1}X^{\top}\}^{\top}=(X^{\top})^{\top}((X^{\top}X)^{-1})^{\top}X^{\top}=X(X^{\top}X)^{-1}X^{\top}=P$);．
--(2)(1)で考えた実数の組&imgtex($(x_i,y_i)$);からなるデータに，2次曲線&imgtex($y=\gamma_1 x^2+\gamma_2 x+\gamma_3$);を最小2乗法で当てはめることにより&imgtex($\gamma_1,\gamma_2,\gamma_3$);の推定量&imgtex($\hat{\gamma}_1,\hat{\gamma}_2,\hat{\gamma}_3$);を求める．ここで，~
&imgtex(\begin{align*}\bm{y}=\begin{pmatrix}y_1\\y_2\\\vdots\\y_n\end{pmatrix},\ Z=\begin{pmatrix}x_1^2&x_1&1\\x_2^2&x_2&1\\\vdots&\vdots&\vdots\\x_n^2&x_n&1\end{pmatrix},\ \hat{\bm{\gamma}}=\begin{pmatrix}\hat{\gamma}_1\\\hat{\gamma}_2\\\hat{\gamma}_3\end{pmatrix}\end{align*});~
とおく．ただし，&imgtex($Z$);の階数は3であるものとする．このとき，~
&imgtex(\begin{align*}Z\hat{\bm{\gamma}}=Q\bm{y}\end{align*});~
を満たす&imgtex($Z$);により決まる&imgtex($n\times n$);行列&imgtex($Q$);と(1)で求めた&imgtex($P$);に関して，~
&imgtex(\[QP=PQ=P\]);~
が成立することを示せ．
---(1)と同様の議論により，~
&imgtex(\[Q=Z(Z^{\top}Z)^{-1}Z^{\top}\]);~
である．ここで，&imgtex(\[X=Z\begin{pmatrix}0&0\\1&0\\0&1\end{pmatrix}=ZW\]);
であるから，~
&imgtex(\[P=ZW(X^{\top}X)^{-1}W^{\top}Z,Q=Z(Z^{\top}Z)^{-1}Z^{\top}\]);として計算すればよい~
//&imgtex(\begin{align*}PQ&=X(X^{top}X)^{-1}X^{\top}Z(Z^{\top}Z)^{-1}Z^{\top}//\\&=X(X^{top}X)^{-1}\begin{pmatrix}0&1&1\\0&1&1\\0&//1&1\end{pmatrix}Z^{\top}Z(Z^{\top}Z)^{-1}Z^{\top}\\&=X(X^{top}X)^{-1}//\begin{pmatrix}0&1&1\\0&1&1\\0&1&1\end{pmatrix}Z^{\top}//\\&=X(X^{top}X)^{-1}X^{\top}=P\end{align*});~
また，&imgtex($P=P^{\top}=(PQ)^{\top}=Q^{\top}P^{\top}=QP$);．
--(3) (1)で考えた実数の組&imgtex($(x_i,y_i)$);からなるデータに対して,
&imgtex($y_1,\dots,y_n$);が互いに独立で，各&imgtex($y_i$);が平均&imgtex($b_1x_i+b_2$);，分散&imgtex($\sigma^2$);の正規分布に従うモデルを仮定する．未知のパラメータ&imgtex($b_1,b_2,\sigma$);の最尤推定量を&imgtex($\hat{b}_1,\hat{b}_2,\hat{\sigma}$);とおく．このとき，&imgtex($\hat{b}_1,\hat{b}_2$);と(1)の&imgtex($\hat{\beta}_1,\hat{\beta}_2$);に関して，~
&imgtex(\[\hat{b}_1=\hat{\beta}_1,\ \hat{b}_2=\hat{\beta}_2\]);~
が成立することを示せ．
---誤差の尤度は~
&imgtex(\begin{align*}L=\prod_{i=1}^n\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{(y_i-\hat{b}_1x_i-\hat{b}_2)}{2\sigma^2}}\end{align*});~
であり，対数をとると，~
&imgtex(\begin{align*}\log L=\sum_{i=1}^n\log \frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{(y_i-\hat{b}_1x_i-\hat{b}_2)^2}{2\sigma^2}}=\frac{n}{\sqrt{2\pi\sigma^2}}-\sum_{i=1}^n\frac{(y_i-\hat{b}_1x-\hat{b}_2)^2}{2\sigma^2}\end{align*});~
&imgtex($\hat{b}_1,\hat{b}_2$);で微分すると，~
&imgtex(\begin{align*}\sum_{i=1}^n(y_i-\hat{b}_1x-\hat{b}_2)&=0\\\sum_{i=1}^n x_1(y_i-\hat{b}_1x-\hat{b}_2)&=0\end{align*});~
と(1)と同じ式が出てくるので，&imgtex($\hat{b}_1=\hat{\beta}_1,\ \hat{b}_2=\hat{\beta}_2$);が成立する．
--(4)[[応用統計学]]の復習をせよ．
----
-第3問~
xy-平面状の2点&imgtex($P_1=(0,0),\ P_2=(a,0)\ (a>0)$);から2種類の結晶が同時に成長を始めた．
&imgtex($P_1$);からの成長は速さ1，&imgtex($P_2$);からの成長は速さ&imgtex($k(>1)$);で，どちらも成長は等方的である．
二つの結晶の成長はぶつかったところで止まり，速く成長する結晶はもう一方の結晶の外側を回り込んで成長することになる．十分な時間が経った後の二つの結晶の境界の極座標表示を&imgtex($r(\theta),\theta$);とする．
--(1)&imgtex($x\ge 0$);の領域にできる境界曲線&imgtex($r(\theta),\theta$);が満たす方程式を求めよ．
---3平方の定理より~
&imgtex($kr(\theta)=\sqrt{(a-r(\theta)\cos\theta)^2+(r(\theta)\sin\theta})^2$);~
であるから，~
&imgtex(\[r(\theta)=\frac{-a\cos\theta+a\sqrt{\cos^2\theta+(k^2-1)}}{k^2-1}.\]);
--(2)極座標表示された一般の曲線&imgtex($(r(\theta),\theta)$);の&imgtex($\theta_1\le \theta\le\theta_2$);の範囲の長さを表す積分表示式を示せ．
---&imgtex(\begin{align*}\int \sqrt{dx^2+dy^2}&=\int\sqrt{(dr\cos\theta+r\sin\theta d\theta)^2+(dr\sin\theta+r\cos\theta d\theta)^2}\\&=\int \sqrt{dr^2+r^2d\theta^2}\end{align*});~
よって，&imgtex($\int_{\theta_1}^{\theta_2}\sqrt{r^2+r'(\theta)^2}d\theta$);
--(3)&imgtex($x\le 0,y\ge 0$);の領域において，&imgtex($r(\theta)$);が満たす方程式を求めよ．
---&imgtex($kr(\theta)=a\sqrt{\frac{k^2}{k^2-1}}+\int_{\pi/2}^{\theta}\sqrt{r^2(\theta)+r'(\theta)^2}d\theta$);
--(4)&imgtex($r(\theta)=\alpha e^{\beta\theta}$);の形の関数で，
(3)で求めた方程式を満たすものを求めよ．
---(3)の式に代入して~
&imgtex(\[k\alpha e^{\beta\theta}=a\sqrt{\frac{k^2}{k^2-1}}+\frac{\alpha\sqrt{1+\beta^2} e^{\beta\theta}}{\beta}-\frac{\alpha\sqrt{1+\beta^2} e^{\beta\pi/2}}{\beta}.\]);~
これを解くと~
&imgtex(\[\alpha=\frac{ak}{\sqrt{k^2-1}}e^{-\frac{\beta\pi}{2\sqrt{k^2-1}}},\ \beta=\frac{1}{\sqrt{k^2-1}}.\]);
&imgtex(\[\alpha=\frac{a}{\sqrt{k^2-1}}e^{-\frac{\pi}{2\sqrt{k^2-1}}},\ \beta=\frac{1}{\sqrt{k^2-1}}.\]);
----
-第4問~
次のようなニューロンモデルを考える．~
容量&imgtex($C$);のコンデンサ,抵抗値&imgtex($R$);の抵抗，
電流源&imgtex($I(t)$);からなる線型電気回路を考える．この回路の微分方程式は~
&imgtex(\[C\frac{dV(t)}{dt}+\frac{V(t)}{R}=I(t)\]);~
となる．時刻&imgtex($T$);で&imgtex($V_{\mathrm{th}}(>0)$);に達すると，放電装置は短絡する．&imgtex($V(0)=0$);とするとき，&imgtex($t\ge 0$);における&imgtex($V(t)$);を考える．
--(1)&imgtex($I(t)$);をステップ電流とするときの&imgtex($V(t)$);を求めよ．
また放電が生じないための&imgtex($I_0$);の条件を求めよ．
さらに，放電を生じる場合，最初の放電時刻&imgtex($T$);を&imgtex($I_0$);の関数として求め図示せよ．
---与えられた微分方程式をラプラス変換すると，~
&imgtex($(CRs+1)\mathcal{L}[V]=\frac{RI_0}{s}$);~
これより，~
&imgtex(\begin{align*}V&=\mathcal{L}^{-1}\left[\frac{RI_0}{s}\frac{1}{CRs+1}\right]\\&=RI_0\mathcal{L}^{-1}\left[\frac{1}{s}-\frac{CR}{CRs+1}\right]\\&=RI_0(1-e^{-\frac{t}{CR}}).\end{align*});~
&imgtex($V(t)\to RI_0\ (t\to\infty)$);なので，放電を生じないための条件は&imgtex($I_0R<V_{th}$);．~
また，放電を生じる場合，最初の放電時刻は&imgtex($V_{th}=I_0R(1-e^{-\frac{T}{CR}})$);であるから&imgtex($T$);について解いて~
&imgtex(\[T=CR\log\frac{I_0R}{I_0R-V_{th}}.\]);
図は&imgtex($0$);から&imgtex($V_{th}/R$);に漸近していくものを描けばよい．~
--(2)インパルス電流&imgtex($I(t)=\delta(t-T_0)$);を入れた場合の&imgtex($V(t)$);を求めよ．~
---&imgtex($t'=t-T_0$);とおきラプラス変換すると，&imgtex($(CRs+1)\mathcal{L}[V]=R$);であるから，~
&imgtex(\begin{align*}V(t'+T_0)&=\mathcal{L}^{-1}\left[\frac{R}{CRs+1}\right]\\&=\frac{1}{C}e^{-\frac{t'}{CR}}\\V(t)&=\begin{cases}0&(t<T_0)\\\frac{1}{C}e^{-\frac{t-T_0}{CR}}&(t\ge T_0)\end{cases}\end{align*});
--(3)&imgtex($I(t)=\beta\sum_{j=1}^{\infty}\delta(t-jT_0)$);~
を入力する場合を考える．十分長い時間がたった後の定常状態において，&imgtex($V(t)$);の時間波形を図示するとともに，
その最大値と最小値を求めよ．また，放電を生じるための&imgtex($\beta$);が満たすべき条件を求めよ．
さらに，放電を生じる場合，最初の放電時刻&imgtex($T$);を求めよ．
---最大値を&imgtex($M$);，最小値を&imgtex($m$);とする．すると，~
&imgtex(\begin{align*}M-m&=\frac{\beta}{C},\\m&=Me^{-\frac{T_0}{CR}}.\end{align*});~
これより，~
&imgtex(\begin{align*}M=\frac{\beta}{C(1-e^{-\frac{T_0}{CR}})},\\m=\frac{\beta e^{-\frac{T_0}{CR}}}{C(1-e^{-\frac{T_0}{CR}})}.\end{align*});~
放電を生じるのは&imgtex($M\ge V_{th}$);，すなわち，~
&imgtex(\[V_{th}\le \frac{\beta}{C(1-e^{-\frac{T_0}{CR}})}\]);のとき．~
&imgtex($n$);個目のインパルスが入ったときの電圧&imgtex($V_n$);は~
&imgtex(\begin{align*}V_n&=V_{n-1}e^{-\frac{T_0}{CR}}+\frac{\beta}{C}\\V_1&=\frac{\beta}{C}\end{align*});~
と表せるので，~
&imgtex(\[V_n=\frac{\beta}{C}\frac{1-e^{-\frac{nT_0}{CR}}}{1-e^{-\frac{T_0}{CR}}}.\]);~
これが，初めて&imgtex($V_{th}$);を超えるときなので，~
&imgtex(\begin{align*}V_{th}&\gtreqless \frac{\beta}{C}\frac{1-e^{-\frac{nT_0}{CR}}}{1-e^{-\frac{T_0}{CR}}}\\n&\gtreqless \frac{CR}{T_0}\log\frac{1}{1-\frac{CV_{th}}{\beta}(1-e^{-\frac{T_0}{CR}})}\end{align*});~
よって，最初の放電時刻は~
&imgtex(\[T_0\left\lceil\frac{CR}{T_0}\log\frac{1}{1-\frac{CV_{th}}{\beta}(1-e^{-\frac{T_0}{CR}})}\right\rceil\]);
--(4) 電流源&imgtex($I(t)$);が微分方程式~
&imgtex(\[\frac{d^2 I(t)}{dt^2}+2\gamma\frac{dI(t)}{dt}+\gamma^2I(t)=0\]);~
に従うとき，初期条件&imgtex($I(0)=0,\ \frac{dI}{dt}(0)=K$);を満たす&imgtex($I(t)$);を求め，その時間波形を図示せよ．
次に，この&imgtex($I(t)$);を入力したときの&imgtex($V(t)$);を求めよ．
---&imgtex($(D+\gamma)^2I(t)=0$);より，&imgtex($I(t)=C_1e^{-\gamma t}+C_2 te^{-\gamma t}$);と書ける．&imgtex($I(0)=C_1=0,\ \frac{dI}{dt}(0)=C_2=K$);より，~
&imgtex(\[I(t)=Kt e^{-\gamma t}.\]);~
また，&imgtex($C\frac{dV(t)}{dt}+\frac{V(t)}{R}=I(t)$);をラプラス変換すると，~
&imgtex(\begin{align*}(CRs+1)\mathcal{L}[V]&=\frac{RK}{(s+\gamma)^2}\end{align*});~
なので，&imgtex($\gamma=\frac{1}{CR}$);のときは~
&imgtex(\[V(t)=\frac{K}{C}\frac{t^2}{2}e^{-\gamma t}\]);．&imgtex(\[\gamma\ne\frac{1}{CR}\]);のときは，~
&imgtex(\[V(t)=\frac{-RKt}{1-CR\gamma}e^{-\gamma t}-\frac{CR^2K}{(1-CR\gamma)}e^{-\gamma t}+\frac{CR^2K}{(1-CR\gamma)^2}e^{-t/(CR)}\]);














----
-第5問~
コインを適当に組み合わせて，その額を支払うことを考える．~
--(1)コイン支払機に1両，2両，5両のコインが無限にあると仮定する．
任意の請求額&imgtex($N$);両に対して，貪欲アルゴリズムを適用すると，
コインの支払い枚数が最小となることを示せ．
---2両を5枚出すより5両を2枚出す方が，1両を2枚出すより2両を1枚出すほうが得なので，&imgtex($1\times 1+2\times 4=9$);両までについて貪欲にやればうまくいくことを示せばよい．実際，
| |1|2|5|合計|
|1|1|0|0|1|
|2|0|1|0|1|
|3|1|1|0|2|
|4|0|2|0|2|
|5|0|0|1|1|
|6|1|0|1|2|
|7|0|1|1|2|
|8|1|1|1|3|
|9|0|2|1|3|
のように貪欲にやればうまくいくことが分かるので，題意は示された．
--(2)コイン支払機に1両，4両，5両の3種類のコインのみがあるとき，
貪欲アルゴリズムでは，コインの支払い枚数が必ずしも最小にならないことを示せ．
--- 8両を支払う時，貪欲にやれば5両が1枚,1両が3枚と4枚も支払わなければならないことになるが，4両を2枚で払えうるので最小ではない．
--コイン支払機に1両，4両，5両の3種類のコインが無限にあると仮定する．
任意の請求額&imgtex($N$);量の支払いに要するコインの最小枚数を計算する動的計画法のアルゴリズムを与えよ．
---&imgtex($n$);両を支払うのに必要な最小枚数を&imgtex($a_n$);としてテーブルを埋めていく．~
&imgtex($a_0=0$);，&imgtex($a_n=\infty (n<0)$);として~
&imgtex(\begin{align*}a_n=\min(a_{n-1},a_{n-4},a_{n-5})+1\end{align*});~
によって，&imgtex($1$);から&imgtex($N$);までを埋めればよい．~
(1)と同様の議論により&imgtex($1\times 1+4\times 4=17$);両より多いときは&imgtex($5$);両を使うべきであるので先にその分を考慮すれば速くなる．
--(4)合計額&imgtex($N$);両のコインをコイン支払機に入れる．
支払機に入れたコインの中で一番高額のものを&imgtex($m$);両コインとし，
&imgtex($j$);両コインの枚数を&imgtex($c_j$);とする．
このとき，合計額が&imgtex($N$);両以下の&imgtex($K$);回の支払いができるためには，
&imgtex($m\le \lceil N/K\rceil$);であり，かつ~
&imgtex(\begin{align*}\sum_{j=1}^i jc_j\ge Ki\ (i=1,2,\dots,m-1)\tag{*}\end{align*});~
でなければならないことを示せ．
---&imgtex($\lfloor N/K \rfloor$);と&imgtex($\lceil N/K\rceil$);を合わせて&imgtex($K$);個組み合わせたようなものを払うためには&imgtex($m\le \lceil N/K\rceil$);であることが必要．~
また，&imgtex($i$);両を&imgtex($K$);回払うためには，&imgtex($i$);両以下のコインが&imgtex($Ki$);両以上ないといけないので，~
&imgtex(\[\sum_{j=1}^i jc_j\ge Ki.\]);~
--(5)(*)の条件が成立するときに，&imgtex($N$);両以下の任意の請求額に対して，
貪欲アルゴリズムで支払いを行う．
その直後の支払機中で最も高額なコインの額を&imgtex($l$);両として，
残っている&imgtex($j$);両のコインの枚数を&imgtex($d_j$);とする．
このとき，~
&imgtex(\[\sum_{j=1}^i jd_j\ge (K-1)i\ (i=1,2,\dots ,l-1)\]);~
となることを示せ．
このことから，(*)が成立するときに，合計額が&imgtex($N$);両以下の&imgtex($K$);回の任意の支払いができることを示せ．
---帰納法で示す．貪欲に&imgtex($l$);両まで支払ったとき，残りの支払額は&imgtex($l-1$);以下であるので,&imgtex($\sum_{j=1}^i jd_j\le l-1$);,&imgtex($\sum_{j=1}^{l-1}jd_j\ge \sum_{j=1}^{l-1}jc_j-(l-1)\ge K(l-1)-(l-1)=(K-1)(l-1)$);．
貪欲に&imgtex($s$);両まで払ったとき，&imgtex($\sum_{j=1}^{s-1} jd_j\ge (K-1)s$);が成立していると仮定する．次に&imgtex($s-1$);両を払うとき，
1枚以上払うならば残りの支払額は&imgtex($s-2$);両以下なので，&imgtex($\sum_{j=1}^{s-2} jd_j\le s-2$);,&imgtex($\sum_{j=1}^{s-2}jd_j\ge \sum_{j=1}^{s-2}jc_j-(s-2)\ge K(s-2)-(s-2)=(K-1)(s-2)$);．
&imgtex($s-1$);両を払わないとき，&imgtex($\sum_{j=1}^{s-2}jd_j=\sum_{j=1}^{s-1}jd_j\ge (K-1)(s-1)\ge (K-1)(s-2)$);より成立．~
また，(*)が成立するとき合計額が&imgtex($N$);両以下の&imgtex($K$);回の任意の支払いができることを&imgtex($K$);に対する帰納法で証明する．
上での議論のように&imgtex($K=1$);のとき，すなわち&imgtex($\sum_{j=1}^i jc_j\ge i$);が成立するとき，
任意の&imgtex($N$);両以下の請求額を支払うことができる．
さらに帰納法の仮定により，任意の&imgtex($M$);に対して，合計額が&imgtex($N-M$);両以下の&imgtex($K-1$);回の支払いが&imgtex($\sum_{j=1}^i jd_j\ge (K-1)i$);ならばできるので，題意は示された．


--[(5)別解]
&imgtex($d_j\neq0$);を満たす添え字&imgtex($j$);を大きい順に&imgtex($l_1(=l),l_2,\ldots,l_k$);とする。~
貪欲アルゴリズムの性質より~
&imgtex(\[ \sum_{j=1}^{l_i-1}j(c_j-d_j) \leq l_i-1\]);~
である。なぜなら&imgtex($d_{l_i}\neq 0$);より、&imgtex($l_{i}$);両のコインはまだあるが、
&imgtex($l_{i}$);両のコインはもう使えない状況である。つまり、残り
&imgtex($1,2,\ldots,l_{i}-1$);両のコインで支払うべき額は&imgtex($l_{i}-1$);以下であることが分かる。
上式を用いて~
&imgtex(\begin{align*} \sum_{j=1}^{l_i-1}jd_j &\geq \sum_{j=1}^{l_i-1}jc_j - (l_i-1) \\ & \geq K(l_i-1) -(l_i-1) = (K-1)(l_i-1)\end{align*});~
そして、&imgtex($l_i > l > l_{i+1}$);なる&imgtex($l$);につていは&imgtex($d_l=0$);であるから、~
&imgtex(\[ \sum_{j=1}^{l-1} jd_j = \sum_{j=1}^{l_i-1}jd_j\geq (K-1)(l_{i}-1)\geq (K-1)(l-1)\]);~
よって、&imgtex($m=l_i-1,l_i-2,\ldots,l_{i+1}$);については~
&imgtex(\[ \sum_{j=1}^{m}jd_j \geq (K-1)m\]);~
が示せた。同様の議論がどの&imgtex($i$);についても成立するので、~
&imgtex(\[ \sum_{j=1}^ijd_j \geq (K-1)i , \forall i = 1,2,\ldots,l-1\]);~
が示せた。
また、~
&imgtex(\[ K(l-1)\leq \sum_{j=1}^{l-1} jc_j< \sum_{j=1}^ljd_j + (l-1)\]);~
より~
&imgtex(\[ l\leq \left\lceil \frac{\sum_{j=1}^ljd_j}{K-1} \right\rceil\]);~
も成立。
-----------------
コメント~
-第3問の曲線の長さって、&imgtex($\int\sqrt{r^2+r'(\theta)^2}d\theta$);な気がするんだけど,如何残暑?違いますかい?
-直しました． -- [[yambi]] &new{2008-08-10 (日) 02:34:01};
- いまさら感満載ですが、第4問の&imgtex($I(t)$);が違ってる気がします。あと、&imgtex($V(t)$);をもとめるとき、&imgtex($\frac{1}{CR}=\gamma$);かどうかで分けなきゃいけない気がします。つまり、めんどくさいです -- [[muk]] &new{2008-08-22 (金) 11:12:03};
- 直しました．また計算間違いしている可能性が高いのでそのときは直してください． -- [[yambi]] &new{2008-08-22 (金) 15:06:07};
- 第３問ですが、(1)は結局余弦定理ですよね？　それで、計算したら&imgtex(\[r(\theta)=\frac{-a\cos\theta+a\sqrt{k^2-\sin ^2 \theta}}{k^2-1}\]);かなーと思いますので、確認よろしくお願いします。あと、(4)の最後も、&imgtex(\[\alpha=\frac{a}{\sqrt{k^2-1}}e^{-\frac{\pi}{2\sqrt{k^2-1}}},\ \beta=\frac{1}{\sqrt{k^2-1}}\]);かなと思いますので、これもよろしくお願いします。 -- [[うっしー]] &new{2008-08-22 (金) 20:23:08};
- (4)同じくそう思います。typoかケアレスミスかな。直しておきました。(1)はルートの中をもう少し計算したら同じになりますね。 -- [[tako]] &new{2008-08-23 (土) 17:57:58};

#comment

       

Site admin: tzik

PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji. Powered by PHP 7.4.16. HTML convert time: 0.002 sec.