lOMoAR cPSD| 46831624
BÀI TẬP ÔN THI MÔN TOÁN RỜI RẠC
Bài 1: Có bao nhiêu cách chọn 20 tờ giấy bạc từ các loại tiền 1 đồng, 2 đồng,
5 đồng, 10 đồng và 20 đồng? Nếu yêu cầu thêm có ít nhất 7 tờ
5 đồng và không quá 8 tờ 20 đồng thì có bao nhiêu cách chọn?
Gọi số tờ tiền của các loại tiền 1 đồng, 2 đồng, 5 đồng, 10 đồng và 20 đồng lần lượt là: ,𝑥 ,𝑥 ,𝑥 ,𝑥
. Theo đề bài, ta có phương trình sau: 𝑥 1 2 5 10 20 +𝑥 +𝑥 +𝑥 + 𝑥
= 20 ớ 𝑣 𝑖 𝑥 ,𝑥 ,𝑥 ≥0; 𝑥 ≥7; 0 ≤ 𝑥 𝑥 1 2 5 10 20 1 2 10 5 20 ≤ 8 (1)
Số cách chọn thỏa yêu cầu của đề bài cũng là số nghiệm nguyên của phương trình (1). Đổi biến: ′ 𝑥 =𝑥 − 7 ≥0 5 5 Xét phương trình: ′ +𝑥 +𝑥′ +𝑥 + 𝑥
= 20−7=13 ớ 𝑣 𝑖 𝑥 ,𝑥 ,𝑥 ,𝑥 ,𝑥 ≥ 𝑥 1 2 5 10 20 1 2 10 5 20 0 ( )𝐼 13
Số nghiệm phương trình (I) là 𝐾 5 13+5−1 =𝐶 5−1 17 =𝐶 4 Xét phương trình: ′ lOMoAR cPSD| 46831624 +𝑥 +𝑥′ +𝑥 + 𝑥
= 13 ớ 𝑣 𝑖 𝑥 ,𝑥 ,𝑥 ,𝑥 ≥0;𝑥 ≥9 𝑥 1 2 5 10 20 1 2 10 5 20 (𝐼𝐼) Đổi biến: ′ 𝑥 =𝑥 − 9 ≥0 20 20
Phương trình (II) tương đương ′ ′ +𝑥 +𝑥′ +𝑥 + ′𝑥
= 13− 9=4 ớ 𝑣 𝑖 𝑥 ,𝑥 ,𝑥 ,𝑥 ,𝑥 ≥0 𝑥 1 2 5 10 20 1 2 10 5 20 4
Số nghiệm phương trình (II) là 𝐾 5 4+5−1 =𝐶 4 5−1 8 =𝐶
Ta có: Số nghiệm phương trình (1) = Số nghiệm phương trình (I) – Số nghiệm phương trình (II) =𝐶 17 4 4 8 − 𝐶 = 2380− 70= 2310
Vậy số cách chọn thỏa yêu cầu đề bài là 2310 cách.
Bài 2: Tìm hệ số của đơn thức 2 3 7
a) xy z t khi khai triển (x + 2y – z +4t – 5u) lOMoAR cPSD| 46831624 3 9 4 3 3 2 3 9
b) x y z t khi khai triển (2x – y – 3z + 4t ) a) Đặt: a = x; b = 2y; c = -z; d = 4t; e = -5u; Ta có: 7 7 (𝑥+2 − +4 −5𝑦𝑧 𝑡 𝑢)= (𝑎+ + + +𝑏 𝑐 𝑑 𝑒) = 𝑃 7 7! ∗ 1 2 3 1 0 (1,2,3,1,0) 𝑎 𝑏 𝑐 𝑑 𝑒 + ⋯= 1 2 3 𝑥 (2𝑦 (−𝑧 (4𝑡 1 0 1!2!3!1!0! ) ) ) −5𝑢 ( ) + 2 3
⋯= −6720(𝑥𝑦 𝑧 𝑡) +⋯ Vậy hệ số cần tìm là: -6720 b) Đặt: a = 2x; 3 b = -y 2 c = -3z 3 d = 4t Ta có: 3 2 3 9 9 (2 −𝑥 𝑦 − 3𝑧 +4𝑡 ) = (𝑎+ + +𝑏 𝑐 𝑑) = ∗ 9! 3 3 2 1 𝑃 3,3,2,1 𝑎 𝑏 𝑐 𝑑 +⋯= lOMoAR cPSD| 46831624 9 ( ) 3 3 3 2 2 3 (2𝑥
(−𝑦 ) (−3𝑧 ) (4𝑡 ) 1 3!3!2!1! ) + 3 9 4 3 ⋯= −1451520(𝑥 𝑦 𝑧 𝑡 )
Vậy hệ số cần tìm là: -1451520
Bài 3: Tìm số nghiệm nguyên không âm của bất phương trình: x + y +z ≤ 19
Đặt =𝑡 19− (𝑥+ +𝑦 𝑧) ≥0
Phương trình đã cho tương đương: 𝑥+ + + =𝑦
𝑧𝑡 19 ớ , , , ≥𝑣 𝑖 𝑥 𝑦 𝑧 𝑡 0 19
Số nghiệm của phương trình là 𝐾 4 22 = 𝐶 3 = 1540 nghiệm
Bài 4: Tìm số nghiệm nguyên của bất phương trình: x + y + z + t > -20 trong
đó x < 1, y ≤ 4, z ≤ -3 và t < 6 ′ Đặt 𝑥
=−𝑥≥0⇒ =− ′𝑥 𝑥 ′ Đặt 𝑦
=−(𝑦−4) =− +4≥0𝑦 ⇒ =4− ′𝑦 𝑦 ′ Đặt 𝑧
=−(𝑧+3) =− −3≥0𝑧 ⇒ =−3− ′𝑧𝑧 ′ Đặt 𝑡
=−(𝑡−5) =− +5≥0𝑡 ⇒ =5− ′𝑡 𝑡
Khi đó bất phương trình trở thành ′ ′ ′ ′ −𝑥 +4−𝑦 −3−𝑧 +5−𝑡 ≥−19 ′ ′ ′ ′ ⇔𝑥 +𝑦 +𝑧 +𝑡 ≤ 19+4−3+5=25 (1) lOMoAR cPSD| 46831624 ′ ′ ′ ′ Đặt =𝑘 25−(𝑥 +𝑦 +𝑧
+𝑡 )≥0∈ℤ, Bất phương trình (1) sẽ có cùng
số nghiệm với phương trình ′ ′ ′ ′ 𝑥 +𝑦 +𝑧 +𝑡 + =𝑘 25 25
Phương trình trên có số nghiệm tương ứng là 𝐾 5 25+5−1 =𝐶 5−1 29 =𝐶 4 = 23751
Vậy bất phương trình đề bài cho có 23751 nghiệm 𝑘 = 𝑘+1 𝑘+2 2 ( ≥0)𝑛 𝑆 ∑ ( )( ) 𝑛 𝑛 𝑘=0 𝑘 = Ta thấy 𝑆 ∑ (𝑘+1)(𝑘+2)2 𝑛 𝑛 𝑘=0 𝑛 𝑘 = (𝑛+1)(𝑛+2)2 +∑(𝑘+1)(𝑘+2)2 𝑛−1 𝑘=0 𝑛 + 𝑛+1 𝑛+2 ⋅2 lOMoAR cPSD| 46831624 =𝑆 ( )( ) 𝑛−1 =1∗2∗1=2 Ta có 𝑆 0
Ta sẽ giải hệ thức đệ quy 𝑆 𝑛 =𝑆 +
𝑛+1 𝑛+2 2 với ≥1𝑛 (∗) { ( )( ) ( ) 𝑛 𝑛−1 =2 (∗∗) 𝑆 0
Ta thấy (1) là hệ thức đệ quy không thuần nhất có dạng 𝑛 =𝜆𝑆 +𝜑 ( ) (với ≥1)𝑛 𝑆 𝑛 𝛼 𝑛 𝑛−1 2 Với =1𝜆
, 𝜑 (𝑛) = (𝑛+1)(𝑛+2) có deg(𝜑 ) =2 và 𝛼=2 2 2
Xét hệ thức đệ quy thuần nhất của (∗) =𝑆 với ≥1 (□)𝑛 𝑆 𝑛 𝑛−1 =𝜆𝑆 với
Ta có (□) là hệ thức đệ quy cấp 1 có dạng 𝑆 𝑛 𝑛−1 𝜆=1, có nghiệm ′ 𝑛 tổng quát 𝑠 𝑛 =𝑝 𝜆⋅
=𝑝 với ∈ℝ𝑝 và ≥0𝑛 Do ≠𝜆
𝛼 nên (∗) có một nghiệm cụ thể dạng: ′′ ( ) 𝑛 lOMoAR cPSD| 46831624 𝑠 𝑛 2 (với ≥0)𝑛 𝑛 =𝜓 2 2
Với deg(𝜓 ) =2. Giả sử 𝜓 (𝑛) =𝑎 𝑛⋅
+𝑏 𝑛⋅ +𝑐 với , , ∈ℝ, ≠0𝑎 𝑏 𝑐 𝑎 2 2
Thay 𝑠′′ vào (∗) ta có 2 𝑛 (𝑎 𝑛 + + 𝑏 𝑛 𝑐) ∗2 2 𝑛−1 𝑛 = (𝑎(𝑛−1) +𝑏(𝑛−1) +𝑐) ∗2 + (𝑛+1) ∗ (𝑛+2) ∗2 2 ⇔2 𝑎 𝑛 + 2 + 𝑏 𝑛 2𝑐 2 2 =𝑎(𝑛 −2 +1𝑛 ) + − + +2 ∗ 𝑏 𝑛 𝑏 𝑐 (𝑛 +3 +2)𝑛 2 2
⇔2 𝑎 𝑛 + 2 + 𝑏 𝑛 2 =𝑐 (𝑎+2)𝑛 + (−2 + +6𝑎 𝑏 ) ∗ + − + +4𝑛 𝑎 𝑏 𝑐 Đồng nhất
phương trình trên ta được hệ phương trình 2 = +2𝑎 𝑎 { 2 =−2 + +6𝑏 𝑎 𝑏 2 = − + +4𝑐 𝑎 𝑏 𝑐 𝑎=2 ⇔{ 𝑏=2 𝑐=4 ′′ 2 𝑛 Vậy 𝑠 (𝑛) = (2𝑛 +2 +4𝑛 )2 (với ≥0)𝑛 ′ ′ =𝑠
Khi đó ta có nghiệm tổng quát của 𝑆 𝑛 𝑛 𝑛 +𝑠 lOMoAR cPSD| 46831624 ′ 2 ( = +𝑝 2𝑛 +2 +𝑛 𝑛 4)2 (với ≥0)𝑛
Thay vào (∗∗) ta có +4=2⇒ =−2𝑝 𝑝 . Vậy =−2+ 2𝑛2 +2 +𝑛 𝑆 ( 𝑛 𝑛 4)2 (với ≥0)𝑛
Bài 6: Giải hệ thức đệ quy sau: 𝑥 + 4𝑥 − 5𝑥 = 12 + 8𝑛 (với ≥2) (∗)𝑛 𝑛 𝑛−1 𝑛−2 { = −5 (∗∗) 𝑥 =0,𝑥 0 1
Ta thấy hệ thức đề bài cho là một hệ thức đệ quy bậc 2 không đồng nhất có dạng 𝑥 +𝜆𝑥 +𝜇𝑥 =𝜑 (𝑛) (với ≥2𝑛 𝛼 𝑛 𝑛−1 𝑛−2 1 𝑛 { ) = −5 𝑥 =0,𝑥 0 1 ( ) ( Với =4𝜆 , =−5𝜇 , 𝜑 𝑛 = 12 +8𝑛 có deg 𝜑 ) =1, 𝛼=1 1 1
Xét hệ thức đệ quy đồng nhất tương ứng của (∗) 𝑥 +4𝑥 −5𝑥 =0 (với ≥2) (□𝑛 ) 𝑛 𝑛−1 𝑛−2 lOMoAR cPSD| 46831624 2
Khi đó (□) có tam thức tương ứng là 𝑓(𝑥 ) =𝑥 +4 −5𝑥
Vì 𝑓(𝑥 ) =0 có 2 nghiệm 𝑥=1 và =−5𝑥 Nên (□) sẽ có nghiệm tổng quát là 𝑥 𝑛 ′ 𝑛 ( )𝑛 ( )𝑛 =𝑝∗1 +𝑞 −5 = +𝑝 𝑞 −5 (với ≥0)𝑛 Với , ∈ℝ𝑝 𝑞 ′
Ta lại có 𝑓(𝛼 ) = (1)=0𝑓
và 𝑓 (𝛼 ) =2∗1+4=6≠0 nên (∗) có một nghiệm cụ thể dạng: 𝑛 𝑥 ( ) ′′ 𝑛 (với ≥0)𝑛 1 =𝑛 𝜓 ) ( ) Với deg(𝜓 =1, giả sử 𝜓 𝑛
=𝑎 𝑛 + 𝑏 với , ∈ℝ, ≠0𝑎 𝑏 𝑎 1 1 ′′
Thay 𝑥 vào (∗), ta có 𝑛(𝑎 𝑛 + 𝑏) +4( −1)𝑛
[𝑎 (𝑛−1) +𝑏] −5( −𝑛
2)[𝑎 (𝑛−2) +𝑏] = 12 +𝑛 8 2 2 2 ⇔ 𝑎 𝑛 + 𝑏 𝑛 +4𝑎(𝑛 −2 +1𝑛
) +4𝑏(𝑛−1) −5𝑎(𝑛 −4 +4𝑛 )
−5𝑏(𝑛−2) − 12 −8=0𝑛 2
⇔ (𝑎+4 −5𝑎 𝑎)𝑛
+ (𝑏−8 +4 +𝑎 𝑏 20 −5 −𝑎 𝑏 12)𝑛+4 −4𝑎 𝑏 − 20 +𝑎 10 −8=0𝑏
⇔ (12 −𝑎 12)𝑛−16 +6 −8=0𝑎 𝑏
Đồng nhất hệ số phương trình trên ta được hệ phương trình: lOMoAR cPSD| 46831624 12 −𝑎 12=0 { −16 +6 −8=0𝑎 𝑏 𝑎=1 ⇔{ 𝑏=4 Vậy 𝑥 𝑛 ′′ ( )
=𝑛∗ 𝑛+4 (với ≥0)𝑛 Khi đó 𝑥 =𝑥 𝑛 𝑛 ′ +𝑥 𝑛 ′′ ( )𝑛 ( ) = +𝑝 𝑞 −5
+𝑛∗ 𝑛+4 (với ≥0)𝑛 𝑝+ =0𝑞
Thay 𝑥 vào (∗∗) ta được hệ { 𝑛 𝑝−5 +1∗5=−5𝑞 𝑝+ =0𝑞 ⇔{ 𝑝−5 =−𝑞 10 5 𝑝=− ⇔{ 3 5 lOMoAR cPSD| 46831624 𝑞= 3 5 Khi đó 𝑥 =− 𝑛 5 + 3 𝑛 3 ( )
+𝑛∗ 𝑛+4 với ≥0𝑛 −5 ( )
ÔN TẬP PHẦN 1: LÝ THUYẾT TỔ HỢP
1. Mệnh đề ¬p → q tương đương logic với ________ a) ¬q → ¬p b) q → p c) ¬p → ¬q d) p ∨ q Đáp án: d
2. Mệnh đề (p → r) ∨ (q → r) tương đương logic với ________ a) (p ∧ q) ∨ r b) (p ∨ q) → r c) (p ∧ q) → r d) (p → q) → r Đáp án: c
3. Cho hai tập hợp C và D, tập hợp (C - D) ∩ D sẽ là __________ a) C lOMoAR cPSD| 46831624 b) D c) Φ
d) Không có tập nào được đề cập Đáp án: c
4. Tập hợp A có 16 tập con. Số phần tử của tập hợp A đó là _________ a) 2 b) 3 c) 4 d) 6 Đáp án: c
5. Tuấn phải chọn một số PIN có bảy chữ số và mỗi chữ số có thể được chọn từ 0
đến 9. Tuấn có thể chọn bao nhiêu số PIN khác nhau ? a) 10000000 b) 9900000 c) 67285000 d) 39654900 Đáp án: a
6. Đối với Khóa học Văn học Anh của mình, Lan phải chọn một cuốn tiểu thuyết
để học trong danh sách 10 cuốn, một bài thơ từ danh sách 15 bài thơ và một truyện
ngắn từ danh sách 7 truyện. Hỏi Lan có bao nhiêu sự lựa chọn khác nhau? a) 3490 b) 2650 c) 1200 d) 1050 Đáp án: d
7. Đặt P (x) là “x là hoàn hảo” và F (x) là “x là bạn của bạn” và miền của x là tất
cả mọi người.Câu nói: "Ít nhất một trong những người bạn của bạn là hoàn hảo"
có thể là biểu thức nào ? a) ∀x (F (x) → P (x)) b) ∀x (F (x) ∧ P (x)) c) ∃x (F (x) ∧ P (x)) d) ∃x (F (x) → P (x)) Đáp án: d
8. Nếu tập A và B lần lượt có 3 và 4 phần tử thì số tập con của tập (AxB) là bao nhiêu? a) 1024 b) 2048 c) 512 d) 4096 Đáp án: d
9. Nếu A là viết tắt của “Tôi thích bóng bàn nhưng ghét văn học”. Điều nào sau
đây biểu thị phủ định của A?
a) Tôi ghét bóng bàn và văn học
b) Tôi không thích bóng bàn hoặc văn học
c) Tôi không thích bóng bàn nhưng yêu văn học
d) Tôi ghét bóng bàn hoặc thích văn học Đáp án: d
10. Vùng bóng mờ của hình được mô tả tốt nhất bằng? lOMoAR cPSD| 46831624 a) A' (Phần bù của A) b) B - (A ∩ B) - (C ∩ B) c) A ∩ C ∩ B d) B' (Phần bù của B) Đáp án: b
11. Có bao nhiêu cách có thể sắp xếp lại các chữ cái của từ SANFOUNDRY để
các nguyên âm A, O, U luôn xuất hiện cùng nhau? a)(8+3)!/2! b) 6!/2! c) 8! * 3! d)4!/8! Đáp án: c
12. Mã két là dãy 7 ô, trong đó: 3 ô đầu là các chữ số (lấy bất kỳ từ 0 đến 9) và 4
ô sau là các chữ cái in hoa trong bảng chữ cái. Có bao nhiêu mã có thể có ? Lưu
ý rằng các chữ số và chữ cái có thể được lặp lại. a) 874261140 b) 537856330 c) 549872700 d) 456976000 Đáp án: d
13. Cho các tập A, B, C. Tập B ∩ C có 8 phần tử, tập A ∩ B có 7 phần tử và tập
C∩A có 7 phần tử. Khi đó số phần tử nhỏ nhất của tập AUBUC sẽ là …? a) 8 b) 14 c) 22 d) 15 Đáp án: a
14. Hai tập hợp A và B lần lượt chứa a và b phần tử. Nếu số tập con của A nhiều
hơn số tập con của B là 16, thì giá trị của b và a là _______ a) 4, 5 b) 6, 7 c) 2, 3
d) Không có phần tử nào được đề cập Đáp án: a
15. Một lớp có 30 sinh viên. Hỏi có bao nhiêu cách lựa chọn ra 6 bạn giữ các chức
vụ trong ban cán sự lớp và ban chấp hành chi đoàn, biết 3 bạn trong ban cán sự
lớp gồm lớp trưởng, lớp phó đời sống, lớp phó học tập, 3 bạn trong ban chấp hành
chi đoàn gồm bí thư, phó bí thư và ủy viên. A. 30!/24!/6! B. 30!/24! C. 6! lOMoAR cPSD| 46831624 D. 30! Đáp án: B
16. Một lớp có 37 sinh viên. Mỗi môn học đều được đánh giá theo thang điểm
chữ A, B, C, D, F. Có thể khẳng định chắc chắn được nhiều nhất bao nhiêu sinh viên có cùng điểm. A. 7 B. 8 C. 37 D. 36 Đáp án: B
17. Một nhân viên bắt đầu làm việc tại công ty từ năm 2015 với mức lương khởi
điểm là 40000 đô la một năm. Hàng năm anh ta được nhận thêm 1000 đô la và
5% lương của năm trước. Giả sử L(n) là lương của nhân viên sau n năm. Hãy cho
biết hệ thức truy hồi tương ứng với công thức tính lương của nhân viên sau n năm tính từ năm 2015 ?
A. L(n)=1.05 * L(n-1) + 1000, L(0)=1000
B. L(n)=1.05 * L(n-1) + 1000, L(0)=40000
C. L(n)=0.05 * L(n-1) + 1000, L(0)=40000
D. L(n)=0.05 * L(n-1) + 1000, L(0)=1000 Đáp án: B
18. Trong đĩa hoa quả có táo, cam, lê, mỗi loại có ít nhất 5 quả. Số cách lấy 5 quả
từ đĩa này nếu thứ tự các quả được chọn không quan trọng là bao nhiêu ? A. 22 B. 15 C. 21 D. 24 Đáp án: C
19. Có bao nhiêu cách chọn năm tờ tiền từ một két đựng tiền gồm những tờ tiền
có mệnh giá 1$, 2$, 5$, 10$, 20$, 50$ và 100$. Giả sử thứ tự mà các tờ tiền được
chọn ra là không quan trọng, các tờ tiền cùng loại là không phân biệt và mỗi loại có ít nhất 5 tờ. A. 432 B. 462 C. 380 D. 280 Đáp án: B