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

Tài liệu tham khảo cho các bạn sinh viên học chuyên ngành có tư liệu ôn thi tốt đạt kết quả cao trong các kì thi giữa kì và cuối kì với những bài toán khó và hướng dẫn cách giải.
Nội dung trích xuất từ tài liệu:
Bài tập toán rời rạc 1BÀI1:(BÀI 19-Tr44 ,Chỉnh hợp,hoán vị,Tổ hợp)ĐỀ BÀI:Có 3 rỏ đựng cầu xanh,đỏ,tím.mỗi rỏ đựng cầu 1mầu,số cầu trong mỗi rỏ >=8a)Có bao cách chọn 8 quả cầu?b)có bao cách chọn 8 quả mà trong đó có mặt 3 loại c ầu? LỜI GIẢI: Gọi a,b,c lần lượt là số quả cầu ở 3 giỏ (a,b,c ≥8) a) Gọi m,n,p là số cầu lấy từ giỏ 1,2,3 (m+n+p=8)∑ Số cách chọn ra 8 quả cầu là :∑Cam.∑Cbn . Cc8-m-n Với m chạy từ 0->8,n chạy từ 0->8-m b) Số cách lấy 1Đ + 1X + 1T là : Ca1.Cb1.Cc1 Số cách lấy 5 quả bất kỳ: ∑Ca-1m.∑Cb-1n.Cc-15-m-n Với m chạy từ 0->5,n chạy từ 0->5-m=>Số cách chọn là : Ca1.Cb1.Cc1. (∑ Ca-1m. ∑ Cb-1n.Cc-15-m-n) 1BÀI2:(BÀI 20-Tr44 ,Chỉnh hợp,hoán vị,Tổ hợp) xxxxĐỀ BÀI:Xét PT: 1 + 2 + 3 + 4 = 29a) PT có bao nghiệm nguyên dương?b) PT có bao nghiệm ko âm? LỜI GIẢI: :x1 + x 2 + x 3 + x 4 = 29 Phương trình xa) Với : i 1 (i = 1,2,3,4) xy yĐặ t : i = + 1( 0) i i � y + 1+ y + 1+ y y + 1+ + 1 = 29 1 2 3 4 y +y +y +y = 25 1 2 3 4 C25+4-1 = C28 4-1 3=> Số nghiệm cần tìm là : 2 b) Với xi ≥ 0 (I = 1,2,3,4) Số nghiệm cần tìm của phương trình là : C29+4-1 = C32 4-1 3 3BÀI3:(BÀI 1-Tr 44 ,NGUYÊN LÝ BÙ TRỪ)ĐỀ BÀi:Hỏi trong đoạn từ 1 đến 1000 có bao số hoặc là sốlẻ hoặc là số chính phương ? LỜI GIẢI: Gọi A1 : tập các số lẻ trong đoạn 1 -> 1000 A2 : tập các số chính phương trong đoạn 1 -> 1000Số lượng cần đếm là :N(A1 A2) = N(A1) + N(A2) – N(A1 A2)Với N(A1) = 500 N(A2) = 31 N(A1 A2) = 16=> Số lượng cần đếm là : 500 + 31 – 16 = 515 4BÀI4:(BÀI 2-Tr44 ,NGUYÊN LÝ BÙ TRỪ)ĐỀ BÀI:Có bao nhiêu xâu nhị phân độ dài 8 ko chứa 6 số 0liền? LỜI GIẢI: Gọi A là tập các xâu nhị phân độ dài 8 chứa 6 số 0 liền nhau.=> Số lượng xâu cần đếm là N = N(X) – N(A) :Với N(X) = 28 ; N(A) = 8Vậy số xâu cần đếm là : 28 – 8 = 248 5 BÀI5:(BÀI 3-Tr 44 ,NGUYÊN LÝ BÙ TRỪ) ĐỀ BÀI:Có bao nhiêu số có 10 chữ số chỉ gồm các số 1,2,3trong đó mỗI chữ số xuất hiện ít nhất 1 lần? LỜI GIẢI: Gọi Ai : tập các số có 10 chữ số trong chữ số i không xuất hiện ( i = 1,2,3)Số lượng cần đếm là :N = N(X) – N (A1 �A2 �A3 )Với N(X) = 310N1 = N(A1) + N(A2) + N(A3) = 210 + 210 + 210 = 3. 210 N ( A1 �A2) + N ( A2 �A3) + N ( A3 �A1)N2 = = 1+1+1 = 3N3 = 0 Vậy số lượng cần đếm là : 310 – 3.210 + 3 = 55980 6BÀI6:(BÀI 4-Tr 44 ,NGUYÊN LÝ BÙ TRỪ)ĐẾ BÀI:Có bao nhiêu xâu nhị phân độ dài 10 hoặc bắtđầu bởI 3 số 1,hoặc kết thúc bởi 4 số 0? LỜI GIẢI:Gọi A1 :tập xâu nhị phân độ dài 10 bắt đầu bởI 3 số 1 A2 :tập xâu nhị phân độ dài 10 kết thúc bởI 4 số 0N(A1 A2) = N(A1) + N(A2) – N(A1 A2) = 27 + 2 6 – 2 3 =184 7BÀI7:(BÀI 5-Tr 44 ,NGUYÊN LÝ BÙ TRỪ)ĐỀ BÀI:Có bao nhiêu số nguyên dương nhỏ hơn 1000 chiahết cho 7 nhưng ko chia hết chi 5 và 2? LỜI GIẢI: Gọi X : tập các số nguyên dương < 10000 chia hết cho 7- A75 : tập các số nguyên dương < 10000 chia hết cho 7 và 5- A72 : tập các số nguyên dương < 10000 chia hết cho 7 và 2- Số lượng cần đếm là : N ( X ) − N ( A75 � A72) = N ( X ) − N ( A75) − N ( A72) + N ( A75 � A72)- Với : N(X) = 9999/7 = 1428 ; N(A75) = 9999/(7.5) = 285; N(A72) = 9999/(7.2) = 714 N ( A75 A72) = 9999/(7.5.2) = 142Số lượng số cần đếm là : 1428 – 285 – 714 + 142 = 571 8