2013

Problem 1

Answer the following questions.

(1) For $\left(c_1{c}_2{c}_3{c}_4{c}_5{c}_6{c}_7\right)=\left(12-820-4492-188\right)$, there exists a pair of integer $k(\ge 1)$ and $k\times k$ constant matrix $\mathbf{M}$ satisfying

$$\left(\begin{array}{c}{c}_{i+1}\\ c_{i+2}\\ ⋮\\ c_{i+k}\end{array}\right)=\mathbf{M}\left(\begin{array}{c}{c}_i\\ c_{i+1}\\ ⋮\\ c_{i+k-1}\end{array}\right)$$

for any $i=1,2,\dots ,7-k$. Among such pairs, find a pair with the smallest $k$ by examining cases $k=1,2,\dots$ in order.

(2) The numbers $c_i(i=1,2,\dots ,7)$ in question (1) can be represented by $c_i=\mathbf{L}{\mathbf{M}}^{i-1}\mathbf{N}$, where $k$ and $\mathbf{M}$ are the pair obtained in question (1), and $\mathbf{L}(\in {\mathbb{R}}^{1\times k})$ and $\mathbf{N}(\in {\mathbb{R}}^{k\times 1})$ are real constant vectors. Find such a pair of $\mathbf{L}$ and $\mathbf{N}$.

(3) Define $c_8,c_9,\dots$ by $c_i=\mathbf{L}{\mathbf{M}}^{i-1}\mathbf{N}$, where $\mathbf{M},\mathbf{L},$ and $\mathbf{N}$ are the ones obtained in questions (1) and (2). Find the rank of the following matrix $\mathbf{C}$ together with the derivation:

$$\mathbf{C}=\left(\begin{array}{cccccccc}{c}_1& c_2& c_3& c_4& c_5& c_6& \dots & c_{10}\\ c_2& c_3& c_4& c_5& c_6& c_7& \dots & c_{11}\\ c_3& c_4& c_5& c_6& c_7& c_8& \dots & c_{12}\\ c_4& c_5& c_6& c_7& c_8& c_9& \dots & c_{13}\\ c_5& c_6& c_7& c_8& c_9& c_{10}& \dots & c_{14}\\ c_6& c_7& c_8& c_9& c_{10}& c_{11}& \dots & c_{15}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ c_{10}& c_{11}& c_{12}& c_{13}& c_{14}& c_{15}& \dots & c_{19}\end{array}\right)$$

(4) Define a function $f(x)=\mathbf{L}(I-x\mathbf{M}{)}^{-1}\mathbf{N}$, where $x$ is a scalar variable, $\mathbf{M}$, $\mathbf{L},$ and $\mathbf{N}$ are the ones obtained in questions (1) and (2), and $I$ is a $k\times k$ identity matrix. Let $f(x)=f_1+f_{2}x+f_3{x}^2+\dots$ be the Taylor series of $f(x)$ at $x=0$. Represent $f_i(\in \mathbb{R})$, $i=1,2,\dots$ by using $c_i(=\mathbf{L}{\mathbf{M}}^{i-1}\mathbf{N})$, $i=1,2,\dots$ together with the derivation. Use the following formula of diagonal matrix $\mathbf{D}$ if necessary:

$$\frac{{\mathrm{d}}^i}{\mathrm{d}{x}^i}(I-x\mathbf{D}{)}^{-1}{|}_{x=0}=i!{\mathbf{D}}^i,i=1,2,\dots$$

---

回答以下问题。

(1) 对于 $\left(c_1{c}_2{c}_3{c}_4{c}_5{c}_6{c}_7\right)=\left(12-820-4492-188\right)$，存在一对整数 $k(\ge 1)$ 和 $k\times k$ 常数矩阵 $\mathbf{M}$ 满足

$$\left(\begin{array}{c}{c}_{i+1}\\ c_{i+2}\\ ⋮\\ c_{i+k}\end{array}\right)=\mathbf{M}\left(\begin{array}{c}{c}_i\\ c_{i+1}\\ ⋮\\ c_{i+k-1}\end{array}\right)$$

对任意 $i=1,2,\dots ,7-k$。在这种情况下，按顺序依次检查 $k=1,2,\dots$，找到使 $k$ 最小的对。

(2) 问题 (1) 中的数值 $c_i(i=1,2,\dots ,7)$ 可以表示为 $c_i=\mathbf{L}{\mathbf{M}}^{i-1}\mathbf{N}$，其中 $k$ 和 $\mathbf{M}$ 是在问题 (1) 中获得的，$\mathbf{L}(\in {\mathbb{R}}^{1\times k})$ 和 $\mathbf{N}(\in {\mathbb{R}}^{k\times 1})$ 是实常数向量。找到这样的一对 $\mathbf{L}$ 和 $\mathbf{N}$。

(3) 定义 $c_8,c_9,\dots$ 为 $c_i=\mathbf{L}{\mathbf{M}}^{i-1}\mathbf{N}$，其中 $\mathbf{M},\mathbf{L},$ 和 $\mathbf{N}$ 是在问题 (1) 和 (2) 中获得的。找到下列矩阵 $\mathbf{C}$ 的秩，并给出推导过程：

$$\mathbf{C}=\left(\begin{array}{cccccccc}{c}_1& c_2& c_3& c_4& c_5& c_6& \dots & c_{10}\\ c_2& c_3& c_4& c_5& c_6& c_7& \dots & c_{11}\\ c_3& c_4& c_5& c_6& c_7& c_8& \dots & c_{12}\\ c_4& c_5& c_6& c_7& c_8& c_9& \dots & c_{13}\\ c_5& c_6& c_7& c_8& c_9& c_{10}& \dots & c_{14}\\ c_6& c_7& c_8& c_9& c_{10}& c_{11}& \dots & c_{15}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ c_{10}& c_{11}& c_{12}& c_{13}& c_{14}& c_{15}& \dots & c_{19}\end{array}\right)$$

(4) 定义函数 $f(x)=\mathbf{L}(I-x\mathbf{M}{)}^{-1}\mathbf{N}$，其中 $x$ 是一个标量变量，$\mathbf{M},\mathbf{L},$ 和 $\mathbf{N}$ 是在问题 (1) 和 (2) 中获得的，$I$ 是 $k\times k$ 单位矩阵。令 $f(x)=f_1+f_{2}x+f_3{x}^2+\dots$ 为 $f(x)$ 在 $x=0$ 处的泰勒级数。用 $c_i(=\mathbf{L}{\mathbf{M}}^{i-1}\mathbf{N})$，$i=1,2,\dots$ 表示 $f_i(\in \mathbb{R})$，$i=1,2,\dots$，并给出推导过程。如有必要，使用以下对角矩阵 $\mathbf{D}$ 的公式：

$$\frac{{\mathrm{d}}^i}{\mathrm{d}{x}^i}(I-x\mathbf{D}{)}^{-1}{|}_{x=0}=i!{\mathbf{D}}^i,i=1,2,\dots$$

---

Problem 2

Let $\mathcal{F}$ be the set of functions $f=f(x)$ on the real line with $f(0)=0$ and $f(1)=1$. For $f\in \mathcal{F}$, we define $I=I[f]$ by

$$I[f]={\int }_0^1\left\{{\left(f(x)\right)}^2+{\left(\frac{\mathrm{d}f(x)}{\mathrm{d}x}\right)}^2\right\}\mathrm{d}x.$$

We are interested in a function in $\mathcal{F}$ that minimizes $I$. Answer the following questions, where every function considered in this problem is assumed to be sufficiently smooth everywhere.

1. Show that, for any $f,g\in \mathcal{F}$ and $t\in [0,1]$,

$$I\left[(1-t)f+tg\right]\le (1-t)I[f]+tI[g]$$

holds.

2. Consider $f\in \mathcal{F}$ satisfying

$${\frac{\mathrm{d}}{\mathrm{d}t}I\left[(1-t)f+tg\right]|}_{t=0}=0$$

for any $g\in \mathcal{F}$. Derive an ordinary differential equation that $f$ should satisfy. If necessary, the following property may be used.

If function $F$ satisfies

$${\int }_0^{1}G(x)F(x)\mathrm{d}x=0$$

for any function $G$ with $G(0)=G(1)=0$, then $F(x)=0$ for $x\in [0,1]$.

3. Explain the reason why the solution of the ordinary differential equation obtained in question (2) minimizes $I$.

4. Find the solution of the ordinary differential equation obtained in question (2).

---

设 $\mathcal{F}$ 为实线上函数 $f=f(x)$ 的集合，并且满足 $f(0)=0$ 和 $f(1)=1$。对于 $f\in \mathcal{F}$，我们定义 $I=I[f]$ 如下：

$$I[f]={\int }_0^1\left\{{\left(f(x)\right)}^2+{\left(\frac{\mathrm{d}f(x)}{\mathrm{d}x}\right)}^2\right\}\mathrm{d}x.$$

我们对 $\mathcal{F}$ 中最小化 $I$ 的函数感兴趣。回答以下问题，其中每个问题中考虑的函数都假设在各处足够光滑。

1. 证明对于任意的 $f,g\in \mathcal{F}$ 和 $t\in [0,1]$，

$$I\left[(1-t)f+tg\right]\le (1-t)I[f]+tI[g]$$

成立。

2. 考虑满足下式的 $f\in \mathcal{F}$：

$${\frac{\mathrm{d}}{\mathrm{d}t}I\left[(1-t)f+tg\right]|}_{t=0}=0$$

对于任意的 $g\in \mathcal{F}$，推导 $f$ 应该满足的常微分方程。如果有必要，可以使用以下性质：

如果函数 $F$ 满足

$${\int }_0^{1}G(x)F(x)\mathrm{d}x=0$$

对于任意的函数 $G$，并且 $G(0)=G(1)=0$，那么 $F(x)=0$ 对于 $x\in [0,1]$。

3. 解释为什么在问题 (2) 中得到的常微分方程的解会最小化 $I$。

4. 求解在问题 (2) 中得到的常微分方程。

---

Problem 3

Initially, a bag contains only a black ball. Consider the repetition of the following operation.

Operation A: A ball is randomly drawn from the bag. If the color of the ball is black, put it back with a ball of a new non-black color. Otherwise, put it back with another ball of the same color.

Note that a ball is not distinguishable from the others until it is drawn from the bag. Answer the following questions.

1. Consider the case where Operation A is repeated 3 times. Find the probability that the number of colors of the balls in the bag (black is not counted) is 2 and 3, respectively.

2. Consider the case where Operation A is repeated 4 times. Find the probability that the number of colors of the balls in the bag (black is not counted) is 3.

3. Consider the case where Operation A is repeated $n$ times. Show that $\frac{1}{n}$ is the probability that the number of colors of the balls in the bag (black is not counted) is 1.

4. Consider the case where Operation A is repeated $n$ times. Find the probability $q_n(m)$ that the number of colors of the balls in the bag (black is not counted) is $m$. If necessary, use $S(n,m)$ defined by the following equation.

$$S(n,m)=\{\begin{array}{ll}S(n-1,m-1)+(n-1)S(n-1,m),& n>m>0\\ 1,& n=m\ge 0\\ 0,& \text{otherwise}\end{array}$$

5. Find the minimum number of trials of Operation A such that the probability exceeds 35% for the case where the number of colors of the balls in the bag (black is not counted) is at least 3. Explain the derivation.

6. Show that for all natural numbers $n$, $q_n(m)$ defined in question (4) satisfies the following equality.

$$\sum _{m=1}^{n}m{q}_n(m)=1+\frac{1}{2}+\cdots +\frac{1}{n}$$

---

最初，一个袋子里只有一个黑球。考虑重复以下操作。

操作 A：随机从袋子里抽出一个球。如果球的颜色是黑色的，就把它和一个新颜色（非黑色）的球一起放回去。否则，用另一个相同颜色的球放回去。

注意，球在从袋子里抽出来之前是无法区分的。回答以下问题。

1. 考虑操作 A重复 3 次的情况。求袋中球的颜色数（不计黑色）为 2 和 3 的概率。

2. 考虑操作 A重复 4 次的情况。求袋中球的颜色数（不计黑色）为 3 的概率。

3. 考虑操作 A重复 $n$ 次的情况。证明袋中球的颜色数（不计黑色）为 1 的概率为 $\frac{1}{n}$。

4. 考虑操作 A重复 $n$ 次的情况。求袋中球的颜色数（不计黑色）为 $m$ 的概率 $q_n(m)$。如果有必要，使用如下方程定义的 $S(n,m)$。

$$S(n,m)=\{\begin{array}{ll}S(n-1,m-1)+(n-1)S(n-1,m),& n>m>0\\ 1,& n=m\ge 0\\ 0,& \text{否则}\end{array}$$

5. 求出操作 A的试验次数的最小值，使得袋中球的颜色数（不计黑色）至少为 3 的概率超过 35%。解释推导过程。

6. 证明对于所有自然数 $n$，问题 (4) 中定义的 $q_n(m)$ 满足以下等式。

$$\sum _{m=1}^{n}m{q}_n(m)=1+\frac{1}{2}+\cdots +\frac{1}{n}$$