109成大電機離散[參考解答]

1. (10%) Consider the letters A, F, K, R, T, and X below. Which of them are isomorphic?

$$圖片請看原檔$$

參考解答：
A and R, F and T, K and X.

---

2. (20%) Let

$X = \{-5, \, -4, \, -3, \, -2, \, -1, \, 0, \, 1, \, 2, \, 3, \, 4, \, 5\}$
For $x, \, y \in X$, set $x \, R \, y$ if $x^2 < y^2$ or $x = y$
(a) Show that $R$ is a partial ordering on $X$
(b) Draw a Hasse Diagram of $R$

參考解答：
(a)
Reflexive: Since $\forall x \in X$, $x = x$ so $x \, R \, x$.
Anti-symmetric: When $x \neq y, \, x^2 < y^2$ and $y^2 < x^2$ won’t happen at the same time, but one of the condition must occur, so is either $x \, R \, y$ or $y \, R \, x$.
Transitive: Let $a, \, b, \, c \in X$ where $a \, R \, b$ and $b \, R \, c$, then we get $a^2 < b^2$ and $b^2 < c^2$ so $a^2 < c^2$ which means $a \, R \, c$.
So $R$ is a partial ordering relation on $X$.
(b)

---

3. (15%) Find the value of sum after the given program segment is executed (Here $i, \, j, \, k, \, increment,$ and $sum$ are integer variables)

increments := 0
sum := 0

for i := 1 to 87 do
 for j := 1 to i do
  for k := 1 to j do
   begin
    increment := increment - 3
    sum := sum + increment
   end
  next k
 next j
next i

參考解答：$-3 \times \binom{89}{3} = -340692$

---

4. DNA(Deoxyribonucleic acid) is a molecule that carries the genetic instructions for all known organism and many viruses. It consists of a chain of bases. In DNA chain, there are four types of bases: A, C, G, T. For example, a DNA chain of length 10 can be ACGTACGTAT.

(a) Let g(n) be the number of configurations of a DNA chain of length n, in which no two T are consecutive and no two G are consecutive. Write a recurrence for g(n).
(b) Solve the recurrence from part (a).

參考解答：
(a) $g(n) – 2g(n-1) – 5g(n-2) – 2g(n-3) = 0, \, n \geq 4. \\ g(1) = 4, \, g(2) = 14, \, g(3) = 50.$
(b) $g(n) = \dfrac{1}{34}((17 + 5 \sqrt{17})(\dfrac{3 + \sqrt{17}}{2})^n + (17 – 5 \sqrt{17})(\dfrac{3 – \sqrt{17}}{2})^n)$

---

5. (10%) Give any 7 distinct numbers, there must exist a sum or a difference of two numbers, where the sum or the difference is a multiple of 10. Please explain the reason.

參考解答：
PH: (1,9) (2,8) (3,7) (4,6) (5) (0)
再用Pigeon Hole Principle(PHP)解釋即可。

---

6. (10%) We learned the notations of Big-O, Big-Theta and Big-Omega. However, when we estimate the efficiency of an algorithm, the most commonly used notation is Big-O. Why? Please write down your thinking.

參考解答：
(1) Because $f = O(g) \iff g = \Omega (f)$, so $\Omega$ can be replaced by $O$.
(2) 在估upper-bound時比較簡單（因而$O$比較好用），但是還要再估lower-bound才可得Big-Theta較為麻煩。

---

7. (15%) A student council consists of three freshmen, four sophomores, four juniors and five seniors. How many committees of eight members of the council contain at least one member from each class?

參考解答： $\binom{16}{8} – [\binom{13}{8} + 2 \binom{12}{8} + \binom{11}{8}] + [2 \binom{9}{8} + 2 \binom{8}{8}]$

---

試題(pdf)：連結

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