2020

Problem 1

Square matrices $A$ and $B$ are given by

$$A=\left(\begin{array}{ccc}1& \sqrt{2}& 0\\ \sqrt{2}& 1& \sqrt{2}\\ 0& \sqrt{2}& 1\end{array}\right),B=\left(\begin{array}{ccc}0& -\frac{2}{3}& \frac{1}{3}\\ \frac{2}{3}& 0& -\frac{2}{3}\\ \frac{1}{3}& \frac{2}{3}& 0\end{array}\right).$$

For a real square matrix $X$, $\exp (X)$ is defined as follows:

$$\exp (X)=\sum _{k=0}^{\infty }\left(\frac{1}{k!}{X}^k\right)=I+X+\frac{1}{2!}{X}^2+\frac{1}{3!}{X}^3+\cdots ,$$

where $I$ is a unit matrix. Answer the following questions.

1. Calculate all eigenvalues of $A$ and the corresponding eigenvectors whose norm is one and whose first element is a nonnegative real.
2. Calculate $A^n$, where $n$ is a nonnegative integer.
3. Calculate $\exp (A)$.
4. Show that $\exp (\alpha B)$ is represented by the following equation:

$$\exp (\alpha B)=I+(\sin \alpha )B+(1-\cos \alpha )B^2,$$

where $\alpha$ is a real number. You may use the Cayley-Hamilton theorem.

5. A function $f$ of 3-dimensional real vector $x$ is given as follows:

$$f(x)=\sum _{k=1}^n{\Vert \exp \left(\frac{2\pi k}{n}B\right)a-x\Vert }^2,$$

where $a$ is a 3-dimensional real vector, and $n\ge 2$. Show that $f$ takes the minimum value at $x=(I+B^2)a$.

---

方阵 $A$ 和 $B$ 如下所示：

$$A=\left(\begin{array}{ccc}1& \sqrt{2}& 0\\ \sqrt{2}& 1& \sqrt{2}\\ 0& \sqrt{2}& 1\end{array}\right),B=\left(\begin{array}{ccc}0& -\frac{2}{3}& \frac{1}{3}\\ \frac{2}{3}& 0& -\frac{2}{3}\\ \frac{1}{3}& \frac{2}{3}& 0\end{array}\right).$$

对于一个实方阵 $X$，$\exp (X)$ 定义如下：

$$\exp (X)=\sum _{k=0}^{\infty }\left(\frac{1}{k!}{X}^k\right)=I+X+\frac{1}{2!}{X}^2+\frac{1}{3!}{X}^3+\cdots ,$$

其中 $I$ 是单位矩阵。回答以下问题。

1. 计算 $A$ 的所有特征值及对应的特征向量，要求特征向量的范数为 1 且其第一个元素为非负实数。
2. 计算 $A^n$，其中 $n$ 是非负整数。
3. 计算 $\exp (A)$。
4. 证明 $\exp (\alpha B)$ 可表示为以下公式：

$$\exp (\alpha B)=I+(\sin \alpha )B+(1-\cos \alpha )B^2,$$

其中 $\alpha$ 是实数。你可以使用 Cayley-Hamilton 定理。

5. 三维实向量 $x$ 的一个函数 $f$ 如下所示：

$$f(x)=\sum _{k=1}^n{\Vert \exp \left(\frac{2\pi k}{n}B\right)a-x\Vert }^2,$$

其中 $a$ 是一个三维实向量，且 $n\ge 2$。证明 $f$ 在 $x=(I+B^2)a$ 处取得最小值。

---

Problem 2

Let $p=(p(t),q(t))(t\in [a,b])$ be a smooth curve in the $xy$-plane. The length ${\ell }_{a^{\prime },b^{\prime }}$ of $p$ from time $t=a^{\prime }$ to $b^{\prime }$ is defined by

$${\ell }_{a^{\prime },b^{\prime }}={\int }_{a^{\prime }}^{b^{\prime }}\sqrt{{\left(\frac{dp}{dt}\right)}^2+{\left(\frac{dq}{dt}\right)}^2}dt,$$

and the total length ${\ell }_{a,b}$ of $p$ is denoted by $L$. Suppose that $\frac{dp}{dt}=(0,0)$ never holds. Let variable $s=s(t)$ be defined as the length ${\ell }_{a,t}$ of $p$ from time $a$ to $t$. Then the curve $p$ is parametrized by the variable $s\in [0,L]$, where $s$ is also referred to as time. Answer the following questions.

1. Show that the following equation holds:

$$\sqrt{{\left(\frac{dp}{ds}\right)}^2+{\left(\frac{dq}{ds}\right)}^2}=1.$$

2. Let $\theta =\theta (s)$ be the angle between the tangent vector $\frac{dp}{ds}=\left(\frac{dp}{ds},\frac{dq}{ds}\right)$ of $p$ at time $s$ and the $x$-axis. Show that the following equation holds:

$$\frac{dp}{ds}\frac{d^{2}q}{d{s}^2}-\frac{dq}{ds}\frac{d^{2}p}{d{s}^2}=\frac{d\theta }{ds}.$$

In the following, suppose that $p$ is a smooth closed curve and is the boundary of a convex set $K$, where $p$ rounds around $K$ in the counterclockwise direction.

3. Explain that $\frac{d\theta }{ds}\ge 0$ holds for any time $s$.

4. A point $x=(x,y)$ that is not contained in $K$ is uniquely represented as

$$x=p(s)+ru(s)$$

by time $s\in [0,L]$ and the distance $r$ between $x$ and $K$, where $u(s)$ is the unit normal vector of $p$ at the time $s$ with direction toward the outside of $K$. Show that the following equation holds for such an $x=(x,y)$:

$$\left|\det \left(\begin{array}{cc}\frac{\partial x}{\partial s}& \frac{\partial x}{\partial r}\\ \frac{\partial y}{\partial s}& \frac{\partial y}{\partial r}\end{array}\right)\right|=1+r\frac{d\theta }{ds}.$$

5. For a nonnegative real number $D$, let $K_D$ be the set of points whose distance from $K$ is at most $D$. Show that the area $A_D={\iint }_{K_D}dxdy$ of $K_D$ is represented as

$$A_D=A+LD+\pi D^2$$

by the area $A$ of $K$ and the total length $L$ of $p$.

---

令 $p=(p(t),q(t))(t\in [a,b])$ 为 $xy$-平面内的一条光滑曲线。$p$ 从时间 $t=a^{\prime }$ 到 $b^{\prime }$ 的长度 ${\ell }_{a^{\prime },b^{\prime }}$ 定义为：

$${\ell }_{a^{\prime },b^{\prime }}={\int }_{a^{\prime }}^{b^{\prime }}\sqrt{{\left(\frac{dp}{dt}\right)}^2+{\left(\frac{dq}{dt}\right)}^2}dt,$$

并且 $p$ 的总长度 ${\ell }_{a,b}$ 记为 $L$。假设 $\frac{dp}{dt}=(0,0)$ 从未成立。令变量 $s=s(t)$ 定义为 $p$ 从时间 $a$ 到 $t$ 的长度 ${\ell }_{a,t}$。然后曲线 $p$ 由变量 $s\in [0,L]$ 参数化，其中 $s$ 也被称为时间。回答以下问题。

1. 证明以下等式成立：

$$\sqrt{{\left(\frac{dp}{ds}\right)}^2+{\left(\frac{dq}{ds}\right)}^2}=1。$$

2. 令 $\theta =\theta (s)$ 为切向量 $\frac{dp}{ds}=\left(\frac{dp}{ds},\frac{dq}{ds}\right)$ 在时间 $s$ 处与 $x$ 轴之间的角度。证明以下等式成立：

$$\frac{dp}{ds}\frac{d^{2}q}{d{s}^2}-\frac{dq}{ds}\frac{d^{2}p}{d{s}^2}=\frac{d\theta }{ds}。$$

在以下部分中，假设 $p$ 是一条光滑的闭合曲线，并且是凸集 $K$ 的边界，其中 $p$ 以逆时针方向绕 $K$。

3. 解释对于任何时间 $s$，$\frac{d\theta }{ds}\ge 0$ 成立。

4. 一个不包含在 $K$ 内的点 $x=(x,y)$ 唯一地表示为

$$x=p(s)+ru(s)$$

其中时间 $s\in [0,L]$ ， $x$ 与 $K$ 之间的距离 $r$， $u(s)$ 是时间 $s$ 处指向 $K$ 外部的 $p$ 的单位法向量。证明对于这样的 $x=(x,y)$，以下等式成立：

$$\left|\det \left(\begin{array}{cc}\frac{\partial x}{\partial s}& \frac{\partial x}{\partial r}\\ \frac{\partial y}{\partial s}& \frac{\partial y}{\partial r}\end{array}\right)\right|=1+r\frac{d\theta }{ds}。$$

5. 对于一个非负实数 $D$，令 $K_D$ 为距离 $K$ 不超过 $D$ 的点集。证明 $K_D$ 的面积 $A_D={\iint }_{K_D}dxdy$ 表示为：

$$A_D=A+LD+\pi D^2$$

其中 $A$ 是 $K$ 的面积，$L$ 是 $p$ 的总长度。

---

Problem 3

Consider hiring the best part-time worker by interviewing $n$ applicants, where $n\ge 2$. It is assumed that the absolute ranking (rank 1, rank 2, $\dots$, rank $n$) of the applicants is determined in advance, and that the relative ranking of the applicants already interviewed is available. The applicants are interviewed one by one, but the order of applicants is random and unknown. In the selection process, the decision to accept or reject an applicant is based on the relative ranking of the applicants already interviewed, and the following conditions are imposed:

• Immediately after an interview, the interviewed applicant is either accepted or rejected.
• Once an applicant is accepted, the selection process terminates.
• Previously rejected applicants cannot be recalled or accepted.
• If no applicants are accepted in the first $n-1$ interviews, the $n$-th applicant is accepted unconditionally.

Suppose that we use the following hiring strategy, where $1<r\le n$.

• Reject the first $r-1$ applicants unconditionally.
• Hereafter, accept the first subsequent applicant who is better than the best applicant among the above $r-1$ applicants (the applicant with the relative rank 1).

Let $P_n(r)$ be the probability of accepting the applicant with the absolute rank 1 in this strategy. Answer the following questions.

1. Calculate $P_4(2)$.
2. Show that $P_{10}(3)=\frac{2}{10}\times \left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{9}\right)$.
3. Derive the probability of accepting the applicant with the absolute rank 1 among $n$ applicants at the $k$-th interview. Note that $r\le k\le n$.
4. Consider the following recursive relation

$$P_n(r)=\left[A\right]+\left[B\right]\times P_n(r+1).$$

Express $A$ and $B$ by $n,r$ and some constants.

5. Let $q=\frac{r}{n}$. Explain that $P_n(r)$ approximately becomes $-q\ln q$ when $n$ is large enough. Moreover, calculate the value of $q\in (0,1]$ that maximizes $-q\ln q$. Note that $\ln$ stands for natural logarithm.

---

通过面试 $n$ 名申请者来招聘最好的兼职工人，其中 $n\ge 2$。假设申请者的绝对排名（排名 1、排名 2、$\dots$、排名 $n$）是预先确定的，并且已经面试的申请者的相对排名是已知的。申请者一个接一个地面试，但申请者的顺序是随机且未知的。在选择过程中，接受或拒绝申请者的决定基于已经面试的申请者的相对排名，并且施加了以下条件：

• 面试结束后立即，面试的申请者要么被接受，要么被拒绝。
• 一旦接受申请者，选择过程终止。
• 先前拒绝的申请者不能被召回或接受。
• 如果在前 $n-1$ 次面试中没有接受任何申请者，则无条件接受第 $n$ 位申请者。

假设我们使用以下招聘策略，其中 $1<r\le n$。

• 无条件拒绝前 $r-1$ 名申请者。
• 此后，接受第一个优于上述 $r-1$ 名申请者中最好的申请者（相对排名为 1 的申请者）的后续申请者。

设 $P_n(r)$ 为在此策略中接受绝对排名为 1 的申请者的概率。回答以下问题。

1. 计算 $P_4(2)$。
2. 证明 $P_{10}(3)=\frac{2}{10}\times \left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{9}\right)$。
3. 推导在第 $k$ 次面试中接受 $n$ 名申请者中绝对排名为 1 的申请者的概率。注意 $r\le k\le n$。
4. 考虑以下递归关系

$$P_n(r)=\left[A\right]+\left[B\right]\times P_n(r+1).$$

通过 $n,r$ 和一些常量表达 $A$ 和 $B$。

5. 设 $q=\frac{r}{n}$。解释当 $n$ 足够大时 $P_n(r)$ 近似变为 $-q\ln q$。此外，计算使 $-q\ln q$ 最大化的 $q\in (0,1]$ 的值。注意 $\ln$ 表示自然对数。