Discrete Mathematics

Giải thích chi tiết:

1. Tập $S$ chứa các phần tử phân biệt sau: phần tử 1 là tập $\{a\}$, phần tử 2 là $\{a, b\}$, phần tử 3 là $\{a, c\}$, phần tử 4 là $a$, phần tử 5 là $b$. Tổng cộng có 5 phần tử $\Rightarrow \mathbf{|S| = 5}$.

2. Với tập $X$ có $10$ phần tử: tập lũy thừa $\mathcal{P}(X)$ có $2^{10} = 1024$ phần tử (tương ứng 1024 tập con). Số tập con thực sự (*proper subsets*) là tất cả các tập con ngoại trừ chính nó: $2^{10} - 1 = \mathbf{1023}$.

Mẹo giải nhanh bằng Luật biến đổi:

Ta có $\overline{A} \setminus \overline{B} = \overline{A} \cap \overline{\overline{B}} = \overline{A} \cap B = B \setminus A$.

Tập $A = \{5, 7, 9, 11, 13, \dots\}$. Do đó lấy $B = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ trừ đi các số thuộc $A$ (bỏ $5, 7, 9$), ta thu được:

$\overline{A} \setminus \overline{B} = \{0, 1, 2, 3, 4, 6, 8\}$.

Một phân hoạch chia tập hợp thành các khối con rời nhau và có hợp bằng chính tập hợp ban đầu. Có đúng 5 phân hoạch:

1. Phân hoạch 1 khối: $\{\{a, b, c\}\}$
2. Phân hoạch 2 khối: $\{\{a, b\}, \{c\}\}$
3. Phân hoạch 2 khối: $\{\{a, c\}, \{b\}\}$
4. Phân hoạch 2 khối: $\{\{b, c\}, \{a\}\}$
5. Phân hoạch 3 khối: $\{\{a\}, \{b\}, \{c\}\}$

• Hình học $A_1$: Điều kiện $\|x\|_0 \le 1$ nghĩa là vector $(x_1, x_2)$ có tối đa 1 thành phần khác $0 \Rightarrow x_1 = 0$ hoặc $x_2 = 0$. Đây chính là hợp của trục hoành và trục tung ($Ox \cup Oy$) trên mặt phẳng $\mathbb{R}^2$.

• Phần bù $\overline{A_1}$: Gồm các điểm không nằm trên trục tọa độ, tức cả hai tọa độ đều khác không: $\overline{A_1} = \{(x_1, x_2) \in \mathbb{R}^2 \mid x_1 \neq 0 \text{ và } x_2 \neq 0\}$.

• Tính $S = \{x+y \mid x,y \in A_1\}$: Mọi điểm $(a, b) \in \mathbb{R}^2$ đều viết được dưới dạng $(a, 0) + (0, b)$ với $(a, 0) \in A_1$ và $(0, b) \in A_1$. Do đó $\mathbf{S = \mathbb{R}^2}$.

• Đặt $p: 4 < 6$ (True) và $q: 9 > 12$ (False). Mệnh đề gốc $p \rightarrow q$ có dạng $\text{T} \rightarrow \text{F}$, nên có giá trị là False (Sai).

• Mệnh đề Đảo ($q \rightarrow p$): "Nếu $9 > 12$ thì $4 < 6$". Vì tiền đề $q$ Sai ($\text{F} \rightarrow \text{T}$), nên mệnh đề đảo có giá trị True (Đúng).

• Mệnh đề Phản đảo ($\neg q \rightarrow \neg p$): "Nếu $9 \le 12$ thì $4 \ge 6$". Mệnh đề phản đảo luôn tương đương với mệnh đề gốc, nhận giá trị False (Sai).

Để chỉ ra hai mệnh đề không tương đương, ta tìm một bộ giá trị làm hai vế nhận kết quả khác nhau:

Chọn $p = \text{False}$, $q = \text{True}$, $r = \text{False}$:

• Vế trái: $(p \rightarrow q) \rightarrow r = (\text{F} \rightarrow \text{T}) \rightarrow \text{F} = \text{T} \rightarrow \text{F} = \mathbf{False}$.

• Vế phải: $p \rightarrow (q \rightarrow r) = \text{F} \rightarrow (\dots) = \mathbf{True}$.

Do kết quả khác nhau nên phép kéo theo không có tính chất kết hợp.

• $\forall x \exists y (x \ge y)$ (Đúng): Với mọi số nguyên dương $x$, luôn tồn tại số $y = 1 \in \mathbb{Z}^+$ để $x \ge 1$ luôn đúng.

• $\exists x \forall y (x \ge y)$ (Sai): Phát biểu rằng tồn tại một số nguyên dương lớn hơn hoặc bằng mọi số nguyên dương khác (tức là có số nguyên dương lớn nhất), điều này vô lý vì luôn có $y = x + 1 > x$.

• Đặt tiền đề $P: (3 < x < 5) \vee (y \neq 2)$ và kết luận $Q: z = 8$. Mã nguồn khẳng định $P \rightarrow Q$.

• Ta quan sát thấy $z = 7 \neq 8 \Rightarrow \neg Q$ xảy ra. Theo luật Modus Tollens, ta suy ra $\neg P$ phải đúng.

• Áp dụng luật De Morgan: $\neg [(3 < x < 5) \vee (y \neq 2)] \equiv (x \le 3 \vee x \ge 5) \wedge (y = 2)$.

⇒ Kết luận chắc chắn: $y = 2$ và ($x \le 3$ hoặc $x \ge 5$).

Chứng minh trực tiếp từng bước:

1. Giả sử $(x, y) \in (A \times B) \cap U_{[2]}$. Theo định nghĩa giao, ta có $(x, y) \in A \times B$ và $(x, y) \in U_{[2]}$.

2. Do $(x, y) \in U_{[2]}$, theo định nghĩa hai tọa độ phải bằng nhau: $x = y$.

3. Do $(x, y) \in A \times B$, ta có $x \in A$ và $y \in B$. Thay $y = x$, ta có $x \in B$.

4. Vì $x \in A$ và $x \in B$, suy ra $x \in A \cap B$ (điều phải chứng minh).

Các bước biến đổi tương đương:

1. Áp dụng luật De Morgan cho cụm $\overline{x_2 \wedge x_3}$: $\overline{x_2 \wedge x_3} = \overline{x}_2 \vee \overline{x}_3$.

2. Khi đó vế trái trở thành: $x_1 \wedge (\overline{x}_2 \vee \overline{x}_3)$.

3. Dùng luật phân phối của $\wedge$ đối với $\vee$: $x_1 \wedge (\overline{x}_2 \vee \overline{x}_3) = (x_1 \wedge \overline{x}_2) \vee (x_1 \wedge \overline{x}_3)$. Vế trái bằng vế phải (đpcm).

• Biểu thức theo dạng tuyển chuẩn tắc: $f = (xy\overline{z}) \vee (x\overline{y}z) \vee (\overline{x}yz) \vee (xyz)$.

• Nhân bản cụm $xyz$ và gom thừa số chung: $xy(\overline{z}+z) \vee xz(\overline{y}+y) \vee yz(\overline{x}+x)$.

⇒ Biểu thức rút gọn tối ưu: $f(x, y, z) = xy \vee xz \vee yz$.

Vì $\text{NAND}(a, b) = \overline{a \wedge b}$ và $\overline{\overline{u}} = u$, ta chỉ cần 2 cổng NAND:

1. Cổng NAND 1 nhận $x, y \rightarrow$ xuất ra $u = \overline{x \wedge y}$.

2. Chập 2 chân vào của cổng NAND 2 lại với nhau và nối với $u \rightarrow$ đóng vai trò cổng NOT: $\overline{u \wedge u} = \overline{u} = \mathbf{x \wedge y}$.

• Với $S = \{1, 2, 3, 6\}$: Phần bù $x' = 6/x$. Thử với mọi phần tử đều thỏa $\text{lcm}(x, x') = 6$ và $\text{gcd}(x, x') = 1 \Rightarrow$ LÀ Đại số Boole.

• Với $S = \{1, 2, 4, 8\}$: Thử phần tử $x = 2 \Rightarrow x' = 8/2 = 4$. Khi đó $x + x' = \text{lcm}(2, 4) = 4 \neq 8$ (vi phạm luật phần bù) $\Rightarrow$ KHÔNG PHẢI là Đại số Boole.

• Nguyên tắc tìm mệnh đề đối ngẫu: Giữ nguyên các biến và dấu phần bù, hoán đổi toán tử $+ \leftrightarrow \cdot$ và các hằng số $0 \leftrightarrow 1$.

• Biểu thức gốc: $(x' + y')' = x \cdot y$.

⇒ Mệnh đề đối ngẫu: $(x' \cdot y')' = x + y$.

• Tập (a): Mỗi phần tử của $X$ đều có đúng một ảnh trong $Y$. Do đó đây là một hàm số.
 - Miền xác định: $\text{dom } f = \{1, 2, 3, 4\}$. Miền giá trị: $\text{range } f = \{a, b, c, d\} = Y$.
 - Các ảnh $f(1)=d, f(2)=a, f(3)=c, f(4)=b$ đều đôi một khác nhau $\Rightarrow$ Đơn ánh.
 - Mọi phần tử trong $Y$ đều có tạo ảnh $\Rightarrow$ Toàn ánh.
 - Kết luận: Hàm số là Song ánh (Bijective).

• Tập (b): Phần tử $2 \in X$ được gán tới hai ảnh khác nhau là $(2, a)$ và $(2, d)$. Theo định nghĩa, mỗi phần tử trong miền xác định chỉ được có duy nhất một ảnh $\Rightarrow$ KHÔNG PHẢI là một hàm số.

• Với $f(n) = \lceil n/2 \rceil$:
 - Thử $n=1 \Rightarrow \lceil 1/2 \rceil = 1$; thử $n=2 \Rightarrow \lceil 2/2 \rceil = 1$. Có $f(1) = f(2) = 1$ nhưng $1 \neq 2 \Rightarrow$ Không đơn ánh.
 - Với mọi $k \in \mathbb{Z}$, chọn $n = 2k$, khi đó $f(2k) = \lceil 2k/2 \rceil = k \Rightarrow$ Toàn ánh.

• Với $f(n) = 2n$:
 - Giả sử $f(n_1) = f(n_2) \Leftrightarrow 2n_1 = 2n_2 \Leftrightarrow n_1 = n_2 \Rightarrow$ Đơn ánh.
 - Vì $2n$ luôn là số chẵn, các số nguyên lẻ (ví dụ $y = 3$) không có $n \in \mathbb{Z}$ nào để $2n = 3 \Rightarrow$ Không toàn ánh.

• $(f \circ g)(n) = f(g(n)) = f(3n - 1) = 2(3n - 1) + 1 = 6n - 2 + 1 = \mathbf{6n - 1}$.

• $(g \circ f)(n) = g(f(n)) = g(2n + 1) = 3(2n + 1) - 1 = 6n + 3 - 1 = \mathbf{6n + 2}$.

⇒ Lưu ý: Phép hợp thành hàm nói chung không có tính chất giao hoán: $f \circ g \neq g \circ f$.

Bảng theo dõi vị trí chèn:

• $53 \bmod 11 = 9 \rightarrow$ Ô 9 trống $\rightarrow$ lưu tại Ô 9.
• $13 \bmod 11 = 2 \rightarrow$ Ô 2 trống $\rightarrow$ lưu tại Ô 2.
• $281 \bmod 11 = 6 \rightarrow$ Ô 6 trống $\rightarrow$ lưu tại Ô 6.
• $743 \bmod 11 = 6 \rightarrow$ Xung đột tại ô 6! Dò tới ô kế tiếp: Ô 7 trống $\rightarrow$ lưu tại Ô 7.
• $377 \bmod 11 = 3 \rightarrow$ Ô 3 trống $\rightarrow$ lưu tại Ô 3.
• $20 \bmod 11 = 9 \rightarrow$ Xung đột ô 9! Dò tiếp sang ô 10 (trống) $\rightarrow$ lưu tại Ô 10.
• $10 \bmod 11 = 10 \rightarrow$ Xung đột ô 10! Quay vòng về ô 0 (trống) $\rightarrow$ lưu tại Ô 0.
• $796 \bmod 11 = 4 \rightarrow$ Ô 4 trống $\rightarrow$ lưu tại Ô 4.

Kết quả bảng: [0:10, 1:trống, 2:13, 3:377, 4:796, 5:trống, 6:281, 7:743, 8:trống, 9:53, 10:20].

• Tính giá trị: $$f\begin{pmatrix} -3 \\ -6 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}\begin{pmatrix} -3 \\ -6 \end{pmatrix} = \begin{pmatrix} 1(-3) + 2(-6) \\ 2(-3) + 4(-6) \end{pmatrix} = \begin{pmatrix} -15 \\ -30 \end{pmatrix}$$

• Xét tính chất:
 - Định thức: $\det(A) = 1(4) - 2(2) = 0 \Rightarrow \text{rank}(A) = 1 < 2$.
 - Vì $\text{rank}(A) < 2$ (không đủ hạng), ma trận $A$ không khả nghịch. Theo định lý:
 • $f$ không phải là đơn ánh (vì tồn tại vector khác 0 như $(2, -1)^T$ có ảnh là $(0, 0)^T = f((0,0)^T)$).
 • $f$ không phải là toàn ánh (ảnh của $f$ chỉ là một đường thẳng $y = 2x$ trong $\mathbb{R}^2$, không lấp đầy $\mathbb{R}^2$).

• 1. Tổng viễn vọng (Telescoping sum): $$\sum_{i=1}^{10} \left(\frac{1}{i} - \frac{1}{i+1}\right) = \left(1 - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \dots + \left(\frac{1}{10} - \frac{1}{11}\right) = 1 - \frac{1}{11} = \mathbf{\frac{10}{11}}$$

• 2. Các xâu con của $babc$:
- Độ dài 0: Xâu rỗng $\lambda$.
- Độ dài 1: $b, a, c$.
- Độ dài 2: $ba, ab, bc$.
- Độ dài 3: $bab, abc$.
- Độ dài 4: $babc$.

• Phản xạ: Với mọi $x \in \mathbb{Z}^+$, $x - x = 0 = 3 \cdot 0 \Rightarrow 3 \mid (x - x) \Rightarrow (x, x) \in R$.

• Đối xứng: Giả sử $(x, y) \in R \Rightarrow 3 \mid (x - y) \Rightarrow x - y = 3k \Rightarrow y - x = 3(-k) \Rightarrow 3 \mid (y - x) \Rightarrow (y, x) \in R$.

• Bắc cầu: Giả sử $(x, y) \in R$ và $(y, z) \in R \Rightarrow x - y = 3k$ và $y - z = 3m$. Cộng vế theo vế: $x - z = (x - y) + (y - z) = 3(k + m) \Rightarrow 3 \mid (x - z) \Rightarrow (x, z) \in R$.

⇒ Quan hệ thỏa mãn phản xạ, đối xứng, bắc cầu nên là QUAN HỆ TƯƠNG ĐƯƠNG (đồng dư modulo 3).

• Tính $R_2 \circ R_1$ (ghép $(x, y) \in R_1$ với $(y, z) \in R_2$):
 - $(1, 1) \in R_1 \rightarrow (1, 1) \in R_2 \Rightarrow (1, 1)$
 - $(1, 2) \in R_1 \rightarrow (2, 1), (2, 2) \in R_2 \Rightarrow (1, 1), (1, 2)$
 - $(3, 4) \in R_1 \rightarrow (4, 4) \in R_2 \Rightarrow (3, 4)$
 - $(4, 2) \in R_1 \rightarrow (2, 1), (2, 2) \in R_2 \Rightarrow (4, 1), (4, 2)$
⇒ $\mathbf{R_2 \circ R_1 = \{(1, 1), (1, 2), (3, 4), (4, 1), (4, 2)\}}$.

• Tính $R_1 \circ R_2$ (ghép $(x, y) \in R_2$ với $(y, z) \in R_1$):
⇒ $\mathbf{R_1 \circ R_2 = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (4, 2)\}}$.

• Lớp tương đương của phần tử lẻ $1$: $[1] = \{x \in X \mid x \text{ là số lẻ}\} = \mathbf{\{1, 3, 5\}}$.

• Lớp tương đương của phần tử chẵn $2$: $[2] = \{x \in X \mid x \text{ là số chẵn}\} = \mathbf{\{2, 4\}}$.

⇒ Hai lớp tương đương $\{1, 3, 5\}$ và $\{2, 4\}$ rời nhau và hợp thành đúng tập $X$, tạo nên một phân hoạch hoàn chỉnh.

Một xâu có độ dài lẻ bắt đầu từ 1 ký tự, và mỗi lần mở rộng sẽ thêm 2 ký tự (chẵn + lẻ = lẻ):

$N = \{\sigma, B\}$, $T = \{0, 1\}$, ký hiệu bắt đầu $\sigma$.
Tập luật sinh $R$:
• $\sigma \rightarrow 0 \mid 1 \mid 00\sigma \mid 01\sigma \mid 10\sigma \mid 11\sigma$

Hoặc gọn hơn: $\sigma \rightarrow B \sigma B \mid B$, với $B \rightarrow 0 \mid 1$.

• Bước cơ sở ($n=1$): Vế trái $= 1 \cdot 2^2 = 4$. Vế phải $= \frac{1(2)(3)(8)}{12} = 4$. Khẳng định đúng với $n=1$.

• Giả thiết quy nạp: Giả sử đẳng thức đúng với $n = k \ge 1$, tức là $S_k = \frac{k(k+1)(k+2)(3k+5)}{12}$.

• Bước quy nạp: Cần chứng minh đúng với $n = k+1$: $$S_{k+1} = S_k + (k+1)(k+2)^2 = \frac{k(k+1)(k+2)(3k+5)}{12} + (k+1)(k+2)^2$$ Đặt nhân tử chung $\frac{(k+1)(k+2)}{12}$: $$= \frac{(k+1)(k+2)}{12} [k(3k+5) + 12(k+2)] = \frac{(k+1)(k+2)}{12} [3k^2 + 17k + 24]$$ Phân tích $3k^2 + 17k + 24 = (k+3)(3k+8) = ((k+1)+2)(3(k+1)+5)$. Khẳng định đúng với $n = k+1$. Theo nguyên lý quy nạp toán học, bài toán được chứng minh.

1. Đưa về dạng chuẩn: $a_n - \frac{7}{2}a_{n-1} + \frac{3}{2}a_{n-2} = 0 \Leftrightarrow 2r^2 - 7r + 3 = 0$.

2. Giải phương trình bậc hai: $(2r - 1)(r - 3) = 0 \Rightarrow r_1 = 3, r_2 = \frac{1}{2}$.

3. Dạng nghiệm: $a_n = b \cdot 3^n + d \cdot (1/2)^n$.

4. Áp dụng điều kiện đầu:
 - $a_0 = b + d = 1 \Rightarrow d = 1 - b$
 - $a_1 = 3b + \frac{1}{2}d = 1 \Leftrightarrow 3b + \frac{1}{2}(1 - b) = 1 \Leftrightarrow \frac{5}{2}b = \frac{1}{2} \Rightarrow b = \frac{1}{5}, d = \frac{4}{5}$.

⇒ Đáp số: $a_n = \frac{1}{5} \cdot 3^n + \frac{4}{5} \left(\frac{1}{2}\right)^n$.

1. Đặt $u_n = \sqrt{a_n}$ (với $u_n > 0$). Khi đó hệ thức trở thành: $u_n = u_{n-1} + 2u_{n-2}$ với $u_0 = u_1 = \sqrt{1} = 1$.

2. Phương trình đặc trưng: $r^2 - r - 2 = 0 \Leftrightarrow (r - 2)(r + 1) = 0 \Rightarrow r_1 = 2, r_2 = -1$.

3. Dạng nghiệm: $u_n = b \cdot 2^n + d \cdot (-1)^n$.

4. Tìm $b, d$: $u_0 = b + d = 1$ và $u_1 = 2b - d = 1 \Rightarrow 3b = 2 \Rightarrow b = 2/3, d = 1/3$.

5. Suy ra: $u_n = \frac{2^{n+1} + (-1)^n}{3} \Rightarrow \mathbf{a_n = \left(\frac{2^{n+1} + (-1)^n}{3}\right)^2}$.

• Để chuyển $n$ đĩa từ cọc A sang cọc C bằng cọc trung gian B:
 1. Chuyển $n-1$ đĩa trên từ A sang B (mất $H_{n-1}$ bước).
 2. Chuyển đĩa lớn nhất còn lại từ A sang C (mất 1 bước).
 3. Chuyển $n-1$ đĩa từ B sang C (mất $H_{n-1}$ bước).

• Hệ thức truy hồi: $H_n = 2H_{n-1} + 1$ với $H_1 = 1$.

• Giải bằng phương pháp thế: $H_n + 1 = 2(H_{n-1} + 1) = \dots = 2^{n-1}(H_1 + 1) = 2^n \Rightarrow \mathbf{H_n = 2^n - 1}$.

• Cơ sở ($n=1$): $f(1) = \frac{10^1 - 1}{9} = 1$ (đúng với đề bài cho).

• Giả thiết: Giả sử $f(k) = \frac{10^k - 1}{9}$ với $k \ge 1$.

• Bước quy nạp: $$f(k+1) = 10f(k) + 1 = 10\left(\frac{10^k - 1}{9}\right) + 1 = \frac{10^{k+1} - 10 + 9}{9} = \frac{10^{k+1} - 1}{9}$$ Đẳng thức đúng với $n = k+1$. Vậy $f(n) = \frac{10^n - 1}{9}$ với mọi $n \ge 1$.

Các số nguyên tố nhỏ hơn hoặc bằng 11 là: $2, 3, 5, 7, 11$. Đếm số mũ Legendre $\lfloor 11/p \rfloor + \lfloor 11/p^2 \rfloor + \dots$:

• Số mũ của 2: $\lfloor 11/2 \rfloor + \lfloor 11/4 \rfloor + \lfloor 11/8 \rfloor = 5 + 2 + 1 = 8$.
• Số mũ của 3: $\lfloor 11/3 \rfloor + \lfloor 11/9 \rfloor = 3 + 1 = 4$.
• Số mũ của 5: $\lfloor 11/5 \rfloor = 2$.
• Số mũ của 7: $\lfloor 11/7 \rfloor = 1$.
• Số mũ của 11: $\lfloor 11/11 \rfloor = 1$.

⇒ $11! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7^1 \cdot 11^1$.

• 1. Số bit của $N = 3^{481}$: $$\text{Số bit} = \lfloor \log_2(3^{481}) \rfloor + 1 = \lfloor 481 \cdot \log_2(3) \rfloor + 1 = \lfloor 481 \cdot 1.58496 \rfloor + 1 = \lfloor 762.36 \rfloor + 1 = \mathbf{763 \text{ bits}}.$$

• 2. Chuyển đổi $A03_{16}$:
- Hệ thập phân: $A \cdot 16^2 + 0 \cdot 16^1 + 3 \cdot 16^0 = 10 \cdot 256 + 0 + 3 = \mathbf{2563}$.
- Hệ nhị phân (mỗi ký tự hex tương ứng 4 bits): $A = 1010_2$, $0 = 0000_2$, $3 = 0011_2 \Rightarrow \mathbf{101000000011_2}$.

• Tính $n$ và $\phi(n)$:
$n = 17 \times 23 = \mathbf{391}$.
$\phi(n) = (17 - 1)(23 - 1) = 16 \times 22 = \mathbf{352}$.

• Tìm khóa giải mã $d$: Cần giải $31d \equiv 1 \pmod{352}$. Dùng thuật toán Euclid mở rộng: $$352 = 31 \times 11 + 11 \Rightarrow 11 = 352 - 31 \times 11$$ $$31 = 11 \times 2 + 9 \Rightarrow 9 = 31 - 11 \times 2$$ $$11 = 9 \times 1 + 2 \Rightarrow 2 = 11 - 9 \times 1$$ $$9 = 2 \times 4 + 1 \Rightarrow 1 = 9 - 2 \times 4$$ Truy ngược lại thu được $31 \times (-79) + 352 \times 7 = 1$. Do đó $d \equiv -79 \equiv 352 - 79 = \mathbf{273}$.

• Mã hóa $M = 101$: $C = 101^{31} \bmod 391 = \mathbf{315}$.

1. Chia liên tiếp (Thuật toán Euclid):
$252 = 198 \times 1 + 54$
$198 = 54 \times 3 + 36$
$54 = 36 \times 1 + 18$
$36 = 18 \times 2 + 0 \Rightarrow \mathbf{\gcd(252, 198) = 18}$.

2. Truy hồi tìm hệ số Bezout:
$18 = 54 - 36 \times 1 = 54 - (198 - 54 \times 3) = 54 \times 4 - 198$
$18 = (252 - 198) \times 4 - 198 = 252(4) + 198(-5)$.

⇒ Hệ số: $s = 4$ và $t = -5$.

• (a) $BAF_6 \rightarrow$ Thập phân: $$BAF_6 = 1 \cdot 6^2 + 0 \cdot 6^1 + 5 \cdot 6^0 = 36 + 0 + 5 = \mathbf{41}_{10}.$$

• (b) $137_{10} \rightarrow$ Hệ cơ số 6:
- $137 \div 6 = 22$ dư 5 (ký tự F)
- $22 \div 6 = 3$ dư 4 (ký tự E)
- $3 \div 6 = 0$ dư 3 (ký tự D)
Ghi các phần dư theo thứ tự từ dưới lên: $345_6$ tương ứng mã ký tự là $\mathbf{DEF_6}$.

• 1. Xếp sách theo khối:
- Có 3 khối chuyên ngành, số cách xếp thứ tự 3 khối là $3! = 6$ cách.
- Trong khối Tin: $5! = 120$ cách.
- Trong khối Toán: $3! = 6$ cách.
- Trong khối Mỹ thuật: $2! = 2$ cách.
⇒ Tổng số cách xếp: $3! \times 5! \times 3! \times 2! = 6 \times 120 \times 6 \times 2 = \mathbf{8640}$ cách.

• 2. Đếm hoán vị chứa AE hoặc EA:
- Coi cụm "AE" là 1 siêu ký tự, cùng với B, C, D tạo thành 4 phần tử $\Rightarrow 4! = 24$ xâu chứa AE.
- Tương tự, có $4! = 24$ xâu chứa EA.
- Vì không thể chứa đồng thời cả AE và EA trong xâu có đúng 5 ký tự phân biệt, giao của 2 tập này bằng rỗng.
⇒ Số xâu thỏa mãn: $24 + 24 = \mathbf{48}$ xâu.

• Tổng số người trong CLB: $6 + 7 = 13$ người.

• Tổng số cách chọn 4 người bất kỳ từ 13 người: $C(13, 4) = \frac{13 \times 12 \times 11 \times 10}{4 \times 3 \times 2 \times 1} = 715$ cách.

• Số cách chọn ban đại diện toàn nam (không có nữ): $C(6, 4) = 15$ cách.

• Số cách chọn ban đại diện toàn nữ (không có nam): $C(7, 4) = 35$ cách.

⇒ Số cách chọn chứa cả hai giới tính: $715 - (15 + 35) = \mathbf{665}$ cách.

• 1. Xác suất vi xử lý đạt chuẩn:
- Số vi xử lý tốt: $100 - 10 = 90$ chiếc.
- Xác suất chọn 4 chiếc đều tốt: $$P = \frac{C(90, 4)}{C(100, 4)} = \frac{\frac{90 \times 89 \times 88 \times 87}{24}}{\frac{100 \times 99 \times 98 \times 97}{24}} = \frac{90 \times 89 \times 88 \times 87}{100 \times 99 \times 98 \times 97} \approx \mathbf{0.6516} \ (65.16\%).$$

• 2. Số nguyên 6-bit $\ge 60$:
- Một số 6-bit nhận các giá trị từ $0$ đến $2^6 - 1 = 63$ (tổng cộng 64 kết quả đồng khả năng).
- Các giá trị $\ge 60$ gồm: $60, 61, 62, 63$ (4 kết quả thuận lợi).
⇒ Xác suất: $P = \frac{4}{64} = \frac{1}{16} = \mathbf{0.0625} \ (6.25\%)$.

• Không gian mẫu: Có $2^3 = 8$ bộ giá trị $(x, y, z)$ có cùng xác suất $1/8$.

• Phân tích các trường hợp $E = 1$:

• Nhánh 1: $\overline{x \vee y \vee z} = 1 \Leftrightarrow x = y = z = 0$ (cho đúng 1 bộ $(0, 0, 0)$).
• Nhánh 2: $x \wedge z = 1 \Leftrightarrow x = 1$ và $z = 1$ ($y$ tùy ý là 0 hoặc 1 $\Rightarrow$ cho 2 bộ: $(1, 0, 1)$ và $(1, 1, 1)$).

• Hai nhánh trên hoàn toàn không giao nhau. Do đó biến cố $E = 1$ có đúng $1 + 2 = 3$ bộ thỏa mãn.

⇒ $P(E = 1) = \frac{3}{8} = \mathbf{0.375} \ (37.5\%)$.

• 1. Bài toán tháng Một: Tháng Một có đúng 31 ngày (coi 31 ngày là 31 chiếc chuồng). Có 32 người (32 con bồ câu). Vì số bồ câu $32 > 31$, theo nguyên lý Dirichlet, tồn tại ít nhất $\lceil 32/31 \rceil = 2$ người nhận séc vào cùng một ngày.

• 2. Bài toán chọn 6 số có tổng bằng 11:
- Ta phân hoạch tập $S$ thành 5 cặp số có tổng bằng 11 (5 chiếc chuồng): $$H_1 = \{1, 10\}, \ H_2 = \{2, 9\}, \ H_3 = \{3, 8\}, \ H_4 = \{4, 7\}, \ H_5 = \{5, 6\}$$ - Ta chọn 6 số phân biệt từ $S$ (6 con bồ câu đặt vào 5 chiếc chuồng). - Theo nguyên lý chuồng bồ câu, do có 6 số đặt vào 5 cặp, chắc chắn có ít nhất 2 số cùng rơi vào một cặp $H_i$. - Vì các số được chọn là phân biệt, hai số này chính là hai phần tử của cặp $H_i$, do đó tổng của chúng bằng đúng 11 (đpcm).

• Ma trận kề $A$ (kích thước $5 \times 5$ theo thứ tự $a, b, c, d, e$): $$A = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \end{pmatrix}$$ (Lưu ý: Tổng các phần tử trên hàng $i$ bằng chính bậc $\delta(v_i)$: $\delta(a)=4, \delta(b)=2, \delta(c)=4, \delta(d)=3, \delta(e)=3$).

• Ma trận liên thuộc $M$ (5 đỉnh $\times$ 8 cạnh $x_1 \dots x_8$): Mỗi cột tương ứng với một cạnh và có đúng 2 số 1 tại 2 đỉnh đầu mút của cạnh đó.
 - Cột $x_1(a,b)$: hàng $a=1, b=1$. Cột $x_2(b,c)$: hàng $b=1, c=1$.
 - Cột $x_3(a,e)$, $x_4(c,d)$, $x_5(a,c)$, $x_6(a,d)$, $x_7(c,e)$, $x_8(e,d)$.

• Cách giải thích: Một đồ thị là phẳng nếu có thể nhúng vào mặt phẳng sao cho các cạnh chỉ giao nhau tại các đỉnh.

• Đồ thị $K_4$ ban đầu có 2 đường chéo $(a, d)$ và $(b, c)$ cắt nhau tại tâm hình vuông. Để vẽ lại:

1. Giữ nguyên chu trình 4 đỉnh ngoài cùng: $a - b - d - c - a$ và đường chéo bên trong $(a, d)$.

2. Cạnh $(b, c)$ thay vì vẽ thẳng xuyên qua tâm, ta uốn cong nó vòng ra hẳn bên ngoài chu trình $a-b-d-c$.

⇒ Khi đó không còn bất kỳ cạnh nào cắt nhau $\Rightarrow$ Đồ thị là đồ thị phẳng.

• 1. Tính số cạnh $m$: Theo định lý bắt tay, tổng bậc của các đỉnh bằng $2m$.
 - Nhìn vào đường chéo chính: phần tử $A_{cc} = 2$ cho biết có 1 khuyên tại $c$ (đóng góp 2 vào bậc); $A_{dd} = 2$ cho biết có 1 khuyên tại $d$.
 - Tổng tất cả các phần tử trong ma trận kề: $\sum \text{hàng} = 3 + 4 + 5 + 5 + 4 = 21$? Tổng các bậc $\sum \delta(v) = 2m \Rightarrow m = \frac{\sum A_{ij}}{2} = \mathbf{9 \text{ cạnh}}$ (tính cả khuyên).

• 2. Công thức Euler cho đồ thị liên thông phẳng: $f = e - v + 2$.
 Với $v = 5$ đỉnh và $e = 9$ cạnh: $$f = 9 - 5 + 2 = \mathbf{6 \text{ mặt (faces)}} \text{ (bao gồm 5 miền kín và 1 miền vô hạn bên ngoài)}.$$

• Định luật Kirchhoff (Bảo toàn luồng tại đỉnh trung gian): Tổng luồng vào bằng tổng luồng ra.

• Xét đỉnh $b$: Luồng vào từ cạnh $(a, b)$ là $F_{ab} = 3$. Cạnh ra duy nhất là $(b, c) \Rightarrow F_{bc} = 3$.

• Xét đỉnh $d$: Cạnh ra duy nhất là $(d, e)$ có $F_{de} = 2 \Rightarrow$ luồng vào từ $a$ phải là $F_{ad} = 2$.

• Xét đỉnh $e$: Luồng vào gồm $F_{de} = 2$ và cạnh ngược $F_{ec}$? Nếu cạnh là $(c, e)$ hoặc $(e, z) = 3 \Rightarrow$ cân bằng luồng vào/ra.

• Giá trị của luồng $V(F)$: Bằng tổng luồng rời khỏi điểm phát $a$: $$V(F) = F_{ab} + F_{ad} = 3 + 2 = \mathbf{5}.$$ (Đúng bằng tổng luồng đổ vào điểm thu $z$: $F_{cz} + F_{ez} = 2 + 3 = 5$).

Quy trình tăng luồng:

1. Tìm đường từ $a$ đến $z$ còn dung lượng dư $C_{ij} - F_{ij} > 0$ trên các cạnh cùng chiều:
• Xét đường $P_1 = (a, b, c, z)$:
 - Cạnh $(a, b)$: $C - F = 5 - 3 = 2$
 - Cạnh $(b, c)$: $C - F = 6 - 3 = 3$
 - Cạnh $(c, z)$: $C - F = 5 - 0 = 5$
⇒ Độ tăng cực đại: $\Delta = \min(2, 3, 5) = \mathbf{2}$.

2. Cập nhật luồng mới:
 $F_{ab} = 3 + 2 = 5$ (đạt bão hòa); $F_{bc} = 3 + 2 = 5$; $F_{cz} = 0 + 2 = 2$.
⇒ Giá trị luồng tăng lên: $V(F') = 5 + 2 = 7$.

3. Kiểm tra tiếp: Cạnh $(a, d)$ có $C-F = 4 - 2 = 2$, xét tiếp đường qua $e$ tới $z$... Khi không còn đường tăng luồng nào từ $a$ sang $z$, thuật toán dừng.

⇒ Luồng cực đại (Max Flow) đạt được là $V(F_{\max}) = \mathbf{8}$.

Quy tắc BST: Từ nhỏ hơn gốc đi sang cây con trái, lớn hơn đi sang cây con phải.

• 1. Gốc: FOUR.
• 2. SCORE > FOUR $\rightarrow$ con phải của FOUR.
• 3. AND < FOUR $\rightarrow$ con trái của FOUR.
• 4. SEVEN: > FOUR (phải), < SCORE (trái của SCORE).
• 5. YEARS: > FOUR (phải), > SCORE (phải của SCORE).
• 6. AGO: < FOUR (trái), > AND (phải của AND).
• 7. OUR: > FOUR (phải), < SCORE (trái), < SEVEN (trái của SEVEN).

⇒ Cây thu được có chiều cao là 3 (gốc ở mức 0).

• Cấu trúc cây nhị phân biểu thức:
- Gốc chính là phép toán thực hiện cuối cùng: Cổng chia $/$.
- Cây con bên trái đại diện cho tử số: $*$, với con trái là $-$ ($A, C$) và con phải là $D$.
- Cây con bên phải đại diện cho mẫu số: $+$, với con trái là $A$ và con phải là $+$ ($B, D$).

• Dạng Tiền tố (Preorder - Duyệt Gốc, Trái, Phải):
/ * - A C D + A + B D

• Dạng Hậu tố (Postorder - Duyệt Trái, Phải, Gốc):
A C - D * A B D + + /

Mô phỏng cơ chế Stack của máy tính: Đọc biểu thức từ trái sang phải, gặp toán hạng thì Push vào Stack, gặp toán tử thì Pop 2 phần tử ra tính rồi Push kết quả trở lại:

• Gặp $A=1$: Push $1 \rightarrow \text{Stack: } [1]$
• Gặp $B=2$: Push $2 \rightarrow \text{Stack: } [1, 2]$
• Gặp $C=3$: Push $3 \rightarrow \text{Stack: } [1, 2, 3]$
• Gặp $+ \rightarrow$ Lấy $3$ và $2$, tính $2 + 3 = 5$, Push $5 \rightarrow \text{Stack: } [1, 5]$
• Gặp $- \rightarrow$ Lấy $5$ và $1$, tính $1 - 5 = -4$, Push $-4 \rightarrow \text{Stack: } [-4]$

⇒ Kết quả: $1 - (2 + 3) = \mathbf{-4}$.

Các bước gom cụm có tần số nhỏ nhất:

1. Danh sách ban đầu: $\{\alpha:5, \beta:6, \gamma:6, \delta:11, \epsilon:20\}$.

2. Chọn 2 tần số nhỏ nhất là $\alpha(5)$ và $\beta(6) \rightarrow$ ghép thành nút cha $N_1(11)$. Danh sách còn: $\{\gamma:6, \delta:11, N_1:11, \epsilon:20\}$.

3. Chọn 2 tần số nhỏ nhất là $\gamma(6)$ và $\delta(11) \rightarrow$ ghép thành nút cha $N_2(17)$. Danh sách: $\{N_1:11, N_2:17, \epsilon:20\}$.

4. Chọn $N_1(11)$ và $N_2(17) \rightarrow$ ghép thành $N_3(28)$. Danh sách: $\{\epsilon:20, N_3:28\}$.

5. Ghép $\epsilon(20)$ và $N_3(28) \rightarrow$ Gốc(48).

• Gán mã nhị phân (nhánh trái = 0, nhánh phải = 1):
 - $\epsilon$: mã 0 (độ dài 1 bit - ký tự xuất hiện nhiều nhất có mã ngắn nhất!)
 - $\alpha$: đi qua $N_3 \rightarrow N_1 \rightarrow \alpha \Rightarrow$ mã 100.
 - $\beta$: đi qua $N_3 \rightarrow N_1 \rightarrow \beta \Rightarrow$ mã 101.
 - $\gamma$: đi qua $N_3 \rightarrow N_2 \rightarrow \gamma \Rightarrow$ mã 110.
 - $\delta$: đi qua $N_3 \rightarrow N_2 \rightarrow \delta \Rightarrow$ mã 111.

Cấu trúc cây quyết định 2 lần cân:

Lần cân 1 (Gốc): Đặt đồng 1 lên đĩa trái, đồng 2 lên đĩa phải.

• Trường hợp 1 (Cân thăng bằng: $1 = 2$): Cả đồng 1 và 2 đều là đồng thật! Đồng giả nằm trong $\{3, 4\}$.
 → Lần cân 2: Đặt đồng 1 (đã biết là thật) cân với đồng 3.
 • Nếu $1 = 3 \Rightarrow$ đồng 4 chắc chắn là đồng giả!
 • Nếu $1 \neq 3 \Rightarrow$ đồng 3 chắc chắn là đồng giả!

• Trường hợp 2 (Cân lệch: $1 \neq 2$): Đồng 3 và 4 chắc chắn là thật! Đồng giả nằm trong $\{1, 2\}$.
 → Lần cân 2: Đặt đồng 3 (thật) cân với đồng 1.
 • Nếu $3 = 1 \Rightarrow$ đồng 2 là đồng giả!
 • Nếu $3 \neq 1 \Rightarrow$ đồng 1 là đồng giả!

⇒ Cây quyết định có chiều cao là 2, giải quyết dứt điểm bài toán trong tối đa 2 lần cân.