1. (10%) Please check if the following statement is true and explain the reason.

“During the first 49 days after John graduates from NCKU, he sends his resume out to different companies. If he sends out at least one resume every day, but no more than 70 resumes in total. Then, there is a period of consecutive days during which he sends out exactly 27 resumes.”

2. (20%) For $x,y$ belonging to the set of positive real numbers, consider the determinant $D_n$ of the $n$ by $n$ matrix $A_{n \times n}.$

(a) Find the recurrence relation for the value of $D_n.$
(b) Find the value of $D_n$ as a function of $n,$ when $y = x.$
(c) Find the value of $D_n$ as a function of $n,$ when $y = 2x.$

$A_{n \times n} = \begin{bmatrix} y & x & 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & \cdot & 0 & 0 & 0 & 0 & 0\\ x & y & x & 0 & 0 & 0 & \cdot & \cdot & \cdot & \cdot & 0 & 0 & 0 & 0 & 0\\ 0 & x & y & x & 0 & 0 & \cdot & \cdot & \cdot & \cdot & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & x & y & x & 0 & \cdot & \cdot & \cdot & \cdot & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & x & y & x & \cdot & \cdot & \cdot & \cdot & 0 & 0 & 0 & 0 & 0\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\ 0 & 0 & 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & \cdot & x & y & z & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & \cdot & 0 & x & y & z & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & \cdot & 0 & 0 & x & y & z\\ 0 & 0 & 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & \cdot & 0 & 0 & 0 & x & y \end{bmatrix}$

(a) $D_n = yD_{n-1} – x^2D_{n-2}, \forall n \geq 1.$
(b) $D_n = y^n(\cos(\dfrac{n \pi}{3}) + \dfrac{1}{\sqrt{3}}\sin(\dfrac{n \pi}{3})), \forall n \geq 1.$
(c) $D_n = x^n(1 + n), \forall n \geq 1.$

3. (20%) If $G$ and $\bar{G}$ are two complementary graphs with the number of vertices greater than or equal $X,$ then either $G$ or $\bar{G}$ is nonplanar.

(a) Please find the value of $X.$
(b) Please explain the reason.

(a) $X = 11$
(b)
Planar graph necessary condition: $e \leq 3n – 6$
(1) When $n$ is even, $|E| = |\bar{E}| = \dfrac{1}{2}\dfrac{n(n – 1)}{2} = \dfrac{n(n – 1)}{4} = e,$ when $n = 12, e = 33 \to e > 3 \cdot 12 – 6 = 30 \to G \text{ or } \bar{G} \text{ is non-planar.}$
(2) When $n$ is odd, $|E| = |\bar{E}| – 1 \to 2e – 1 = \dfrac{n(n – 1)}{2} \to e = \dfrac{n^2 – n + 2}{4},$ when $n = 11, e = 28 > 3 \cdot 11 – 6 = 27 \to G \text{ or } \bar{G} \text{ is non-planar.}$

### 2 留言

1. #### Rakson

請問第二題的(c)小題 答案的x^2應該改成x^n吧？

另外謝謝您提供這麼完整的答案，太感謝了！