Tài liệu sưu tầm. Giải đề toán rời rạc

LỜI GIẢI CHI TIẾT ĐỀ THI Câu 1 (2.0 điểm)
Đề bài: Tìm số nghiệm nguyên dương của hệ: (x + y + z + t = 20
x > 3, y ≥ 4, z ≥ 5, t ≥ 2 Giải:
• Vì x là số nguyên, điều kiện x > 3 tương đương với x ≥ 4.
• Ta đưa bài toán về tìm số nghiệm nguyên không âm bằng cách đặt biến phụ:
– Đặt x′ = x − 4 ⇒ x = x′ + 4 (với x′ ≥ 0)
– Đặt y′ = y − 4 ⇒ y = y′ + 4 (với y′ ≥ 0)
– Đặt z′ = z − 5 ⇒ z = z′ + 5 (với z′ ≥ 0)
– Đặt t′ = t − 2 ⇒ t = t′ + 2 (với t′ ≥ 0)
• Thế vào phương trình tổng:
(x′ + 4) + (y′ + 4) + (z′ + 5) + (t′ + 2) = 20
⇔ x′ + y′ + z′ + t′ = 20 − (4 + 4 + 5 + 2) = 5
• Áp dụng công thức số tổ hợp lặp (bài toán chia kẹo Euler): 8 · 7 · 6 Ck−1 = C4−1 = C3 = = 56 n+k−1 5+4−1 8 3 · 2 · 1
Đáp số: Có tất cả 56 nghiệm nguyên dương. Câu 2 (3.0 điểm)
a) Chứng minh (X, |) là một quan hệ thứ tự:
Một quan hệ là quan hệ thứ tự nếu thỏa mãn 3 tính chất:
1. Phản xạ: Với mọi a ∈ X, a chia hết cho a (a|a). Luôn đúng.
2. Phản đối xứng: Với mọi a, b ∈ X, nếu a|b và b|a thì a = b. Luôn đúng với số nguyên dương.
3. Bắc cầu: Với mọi a, b, c ∈ X, nếu a|b và b|c thì a|c. Luôn đúng theo tính chất phép chia. 1
Vậy (X, |) là một quan hệ thứ tự.
b) Tìm các phần tử đặc biệt:
• Tối tiểu: {2, 3} (không có số nào trong X là ước của chúng ngoài chính nó).
• Tối đại: {6, 8} (chúng không là ước của số nào khác trong X).
• Nhỏ nhất/Lớn nhất: Không có (vì có nhiều hơn một phần tử tối tiểu/tối đại). c) Biểu đồ Hasse: 8 4 6 2 3 Câu 3 (2.0 điểm)
Tìm nghiệm của hệ thức đệ quy an = an−1 + 6an−2 với a0 = 2, a1 = 2.
• Phương trình đặc trưng: r2 − r − 6 = 0.
• Giải phương trình: (r − 3)(r + 2) = 0 ⇒ r1 = 3, r2 = −2.
• Nghiệm tổng quát: an = A · 3n + B · (−2)n.
• Thay điều kiện ban đầu: ( ( A + B = 2 2A + 2B = 4 6 4 ⇒ ⇒ 5A = 6 ⇒ A = , B = 3A − 2B = 2 3A − 2B = 2 5 5
Đáp số: an = 1.2 · 3n + 0.8 · (−2)n. Câu 4 (3.0 điểm)
Cho hàm Boole: f (x, y, z, t) = x¯ yz ∨ xyt ∨ ¯ xy ¯ z ∨ xt.
• a) Tế bào lớn: Qua biểu đồ Karnaugh, các tế bào lớn (nhóm ô số 1 lớn nhất) là: xt, x¯ yz, và ¯ xy ¯ z.
• b) Đa thức tối tiểu: f = xt ∨ x¯ yz ∨ ¯ xy ¯ z 2
• c) Mạng cổng tổng hợp: Cần 3 cổng AND cho các tích và 1 cổng OR cho tổng
cuối cùng. (Sử dụng các cổng NOT cho các biến có gạch ngang đầu). – HẾT – 3