115年台大碩士班- 數學A詳解

國立臺灣大學 115 學年度碩士班招生考試試題

科目: 數學(A)

解答:

$$\text{total states }=1+ \sum_{k=1}^n 4k=1+4\times {n(n+1)\over 2} = \bbox[red, 2pt]{2n^2+2n+1}$$

解答:$$|A|= 6^5 =7776 \Rightarrow N=9^{|A|} =9^{7776} \\ \cases{9^{10} \equiv 1 {\mod 11} \\ 7776 \equiv 6 {\mod 10}} \Rightarrow N \equiv 9^6 {\mod 11} \Rightarrow 9^6=531441 \equiv 9 {\mod 11}\Rightarrow N \equiv \bbox[red, 2pt]9 {\mod 11}$$

解答:$$a_n= 6a_{n-1}-11 a_{n-2}+ 6 a_{n-3} \Rightarrow r^3-6r^2+11r-6=0 \Rightarrow (r-1)(r-2)(r-3)=0 \\ \Rightarrow r=1,2,3 \Rightarrow a_n= c_1 \cdot 1^n+ c_2 \cdot 2^n+ c_3 \cdot 3^n \Rightarrow \cases{a_0=c_1+c_2+c_3=1 \\ a_1= c_1+2c_2+3c_3=2\\ a_2=c_1+4c_2+9c_3=2} \Rightarrow \cases{c_1=-1\\ c_2=3\\ c_3=-1} \\ \Rightarrow \bbox[red, 2pt]{a_n=-1+3\cdot 2^n-3^n}\\ 題目:a_1=2應該是\bbox[cyan,2pt]{a_2=2}$$

解答:$$\text{Let the generating function }G(x) = \sum_{n=0}^\infty a_n x^n ={P(x) \over Q(x)} \\ \text{From the recurrence coefficients, we have }Q(x)=1-6x+11x^2-6x^3\\ P(x)\text{ is determined by the initial conditions: }P(x)=a_0+(a_1-6a_0)x+ (a_2-6a_1+11a_0)x^2 \\=1+(2-6\cdot1)x+ (2-6\cdot 2+11\cdot 1)x^2=1-4x+x^2 \\ \Rightarrow G(x)={1-4x+x^2\over 1-6x+11x^2-6x^3} ={1-4x+x^2\over (1-x)(1-2x) (1-3x)} =\bbox[red, 2pt]{{-1\over 1-x}+{3\over 1-2x}-{1\over 1-3x}}$$

解答:$$x_1+\cdots+ x_{12} \le 6 \Rightarrow x_1+ \cdots+ x_{12}+ y=6, y=0,1,\dots,6 \\ \Rightarrow N=H^{13}_6=C^{18}_6 = 18564 = 1687\times 11 +\bbox[red, 2pt]7$$

解答:$$\cases{x_1+2x_2-2x_3=0 \\ 2x_1-x_2+ \lambda x_3=0\\ 3x_1+x_2+x_3=0} \Rightarrow \begin{bmatrix}1& 2& -2\\ 2&-1& \lambda\\ 3& 1& 1 \end{bmatrix} \begin{bmatrix}x_1\\ x_2\\ x_3 \end{bmatrix} =0 \\ A=\begin{bmatrix}1& 2& -2\\ 2&-1& \lambda\\ 3& 1& 1 \end{bmatrix} \Rightarrow \det(A)=0 \Rightarrow 5\lambda-15=0\Rightarrow \lambda= \bbox[red, 2pt]3$$

解答:$$a+b+c+ d = \begin{bmatrix}1& 1 \end{bmatrix} \begin{bmatrix}a& b\\c& d \end{bmatrix} \begin{bmatrix}1\\ 1 \end{bmatrix} =\begin{bmatrix}1& 1 \end{bmatrix} A^{2004} \begin{bmatrix}1\\ 1 \end{bmatrix}  =\begin{bmatrix}1& 1 \end{bmatrix} \begin{bmatrix}4& 3\\1& 2 \end{bmatrix}A^{2003} \begin{bmatrix}1\\ 1 \end{bmatrix}  \\=5  \begin{bmatrix}1& 1 \end{bmatrix} A^{2003} \begin{bmatrix}1\\ 1 \end{bmatrix} =5^2  \begin{bmatrix}1& 1 \end{bmatrix} A^{2002} \begin{bmatrix}1\\ 1 \end{bmatrix} = \cdots =5^{2004} \begin{bmatrix}1& 1 \end{bmatrix} \begin{bmatrix} 1\\1 \end{bmatrix} =2\cdot 5^{2004} \\\Rightarrow {a+b+c+d \over 5^{2004}}= \bbox[red, 2pt]2$$

解答:$$\cases{ A^TA= \begin{bmatrix}1& 1& 0\\1& 1& 0 \end{bmatrix} \begin{bmatrix}1& 1\\1& 1\\ 0& 0 \end{bmatrix} = \begin{bmatrix}2& 2\\2& 2 \end{bmatrix} \\[1ex] A^Tb= \begin{bmatrix}1& 1& 0\\1& 1& 0 \end{bmatrix} \begin{bmatrix}1\\0\\1 \end{bmatrix} = \begin{bmatrix}1\\1 \end{bmatrix}} \Rightarrow \begin{bmatrix}2& 2\\2& 2 \end{bmatrix} \begin{bmatrix}x_1 \\x_2 \end{bmatrix} = \begin{bmatrix}1\\1 \end{bmatrix} \Rightarrow \begin{bmatrix}x_1 \\x_2 \end{bmatrix}=\bbox[red, 2pt]{ \begin{bmatrix}1/4\\ 1/4 \end{bmatrix}}$$

解答:$$A \text{ is a positive semi-definite matrix }\Rightarrow \lambda_1\gt \lambda_2 \gt \cdots \gt\lambda_n\ge 0\\\text{By von Neumann's trace inequality, }\text{ trace}(AX) \ge \sum_{i=1}^n \lambda_i(A)\lambda_{n-i+1}(X)\\ \text{We are looking for minimizing trace}(AX) \text{ subject to }\left \Vert X\right \Vert_* =\sum_{i=1}^n |\lambda_i(X)| \le c \\ \text{Given }\lambda_1\gt \cdots \gt \lambda_n, \text{ the smallest value is achieved by setting the eigenvalue associated with} \\ \lambda_1 \text{ to be }-c \text{ and all other eigenvalues to 0. To achieve the minimm, we construct }X\text{ using the }\\\text{ outer product of this principal eigenvector:  } \bbox[red, 2pt]{X= -cv_1v_1^*}$$

解答:$$g(x)=-\sum_{i=1}^n \ln(x_i) \Rightarrow \nabla g(x)=-[1/x_1,1/x_2,\dots,1/x_n]^T \\\Rightarrow \nabla^2 g(x)= \text{diag} \left( {1\over x_1^2},\dots,{1\over x_n^2} \right)=X^{-2}, \text{ where }X= \text{ diag}(x) \\f(x)=-\alpha \ln(a_1^T x)-\beta\ln(a_2^T)\Rightarrow \nabla f(x)=-{\alpha\over a_1^T x}a_1-{\beta\over a_2^T x}a_2 \\\Rightarrow \nabla^2 f(x)={\alpha\over (a_1^T x)^2}a_1a_1^T+{\beta\over (a_2^T x)^2}a_2 a_2^T \\f\text{ is }L-\text{smooth relative to }\Rightarrow L\nabla^2 g(x)\succeq \nabla^2 f(x) \Rightarrow LX^{-2 }\succeq \alpha\frac{a_1 a_1^T}{(a_1^T x)^2}  + \beta \frac{a_2 a_2^T}{(a_2^T x)^2}  \\ \Rightarrow LI \succeq \alpha\frac{Xa_1 a_1^TX}{(a_1^T x)^2}  + \beta \frac{Xa_2 a_2^TX}{(a_2^T x)^2}  \\ \text{Let }u= {Xa_1\over a_1^Tx} \text{ and }v={Xa_2\over a_2^Tx}, \text{ then }u_i= {x_i(a_{1})_i \over \sum_j x_j(a_1)_j}, v_i={x_i(a_2)_i\over \sum_jx_j(a_2)_j} \\\Rightarrow \cases{u_i\gt 0 \text{ and }\sum u_i=1\\ v_i\gt 0 \text{ and }\sum v_i=1 } \Rightarrow L \cdot I \succeq \alpha u u^T + \beta v v^T \\ \text{The smallest L is the maximum eigenvalue of the matrix }M=\alpha uu^T+ \beta v v^T \\=(\alpha+ \beta) u u^T, \text{ which has a maximum eigenvalue of }\alpha+\beta \\ \Rightarrow \text{The smallest possible }L= \bbox[red, 2pt]{\alpha+\beta} \\ \href{https://web.mit.edu/haihao/www/papers/Norm-free.pdf}{詳細過程可參考資料}$$

========================== END =========================

解題僅供參考，碩士班歷年試題及詳解