109成大資聯離散[參考解答]

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.”

參考解答：True, by Pigeon Hole Principle (PHP).

---

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.}$

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！