Bài tập Toán rời rạc - Bài 1

Toán rời rạc Bài tập 1 Bài 1 Hãy chứng minh rằng có vô hạn số nguyên tố. Bài 2 Dùng nguyên lý Sắp thứ tự tốt để chứng minh rằng: với mọi số nguyên không âm n, ta luôn có n≤ 3n/3 (1) Gợi ý: Hãy kiểm tra (1) với các giá trị n≤ 4. Bài 3 Với n = 40 giá trị của đa thức p(n) ::= n2 + n+ 41 không phải là số nguyên tố. Ta dự đoán rằng, ngoại trừ các đa thức hằng số, không có đa thức nào chỉ sinh ra các giá trị là các số nguyên tố. Cụ thể, xét đa thức q(n) với hệ số nguyên dương, và xét c ::= q(0) là số hạng hằng số của q(n). (a) Chứng minh rằng q(cm) là bội của c với mọi m ∈ Z. (b) Chứng minh rằng nếu đa thức q không phải đa thức hằng số và c > 1, thì tập {q(n) | n ∈ N} chứa vô hạn số không nguyên tố. (c) Kết luận rằng với mọi đa thức q không phải hằng số, có một số nguyên n sao cho q(n) không là số nguyên tố. Bài 4 Chứng minh rằng trong một nhóm gồm 9 người luôn có bốn người đôi một quen nhau hoặc ba người đôi một lạ nhau.