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

Câu 1 Tốt nghiệp 2007 (Đợt 1) Cho xâu S = “AABCCDD” có |S| = 7, Có bao nhiêu xâu tạo ra từ S thỏa:a)Chữ b đứng chính giữa xâu (dạng ***B***) C1: Chữ B giữ 1 vị trí ở giữa xâu, nên 6 vị trị còn
Nội dung trích xuất từ tài liệu:
Bài tập môn toán rời rạcCâu 1 Tốt nghiệp 2007 (Đợt 1)Cho xâu S = “AABCCDD” có |S| = 7, Có bao nhiêu xâu tạo ra từ S thỏa: Chữ b đứng chính giữa xâu (dạng ***B***) a) C1: Chữ B giữ 1 vị trí ở giữa xâu, nên 6 vị trị còn lại là hoán vị lặp của 6 giá chữ còn lại: 6! /(2!x2!x2!) = 90 (xâu) C2: Chia trường hợp a thành 2 trường hợp (Với ** là 2 ký tự trùng nhau, * là 1 ký tự khác, ví dụ AACBCDD,ACABDDC,…) Sẽ có 6 trường hợp cho mỗi ký tự lặp (***): AAD,AAC,CCA,CCD,DDA,DDC Và mỗi trường hợp sẽ là hoán vị lặp của 1 ký tự : C32 = 3 Vậy với mỗi xâu có dạng TTEBETT có 3x3 = 9 trường hợp (vì có dạng ***B***) Vậy trường hợp 1 có 6x9 = 54 (xâu) Trường hợp 2 gồm các *** có dạng 3 ký tự khác nhau :C,A,D Trường hợp 2 có 3!x3! = 36(xâu) Vậy tổng trường hợp a có 90 (xâu)b)Hai chữ A không đứng kề nhau: 2 chữ A đứng kề nhau có 6 trường hợp Vậy tổng xâu trường hợp B 7!/(2!x1!x2!x2!x2!) – 6 = 624(xâu)c)Hai chữ A không đứng kề nhau và 2 chữ C không đứng kề nhau Gọi S là số xâu có 2 chữ A đứng kề nhau và 2 chữ C đứng kề nhau S = 5! / 2! = 60 (xâu) Tổng xâu : 630 – 60 = 570 (xâu)d)chữ B đứng trước tất cả chữ A : 630 / 3 = 210(xâu)Câu 1 tốt nghiệp 2007 (đợt 2) Cho X là tập các số nguyên trong đoạn [100,1000], trong X có bao nhiêu số thỏa mãnđiều kiện sau: a) Số vừa chia hết cho 4 và 6 100Trong quá trình lặp sẽ có các cặp số 100,200,…,900 bị trùng 1 giá trị, Vậy tổng số xâulà : 181 – 9 = 172f) Số chứa đúng 1 số 7: C1: số có dạng A** với A = [1,9] / {7}, Số 7 nằm 1 trong 2 vị trí **, vị trí còn lạicó 9 giá trị ([0,9]/7) 8x2x9 = 144 (số) Với A = 7, 2 vị trí còn lại mỗi vị trí có 9 giá trị ([0,9] / {7}) 9x9 = 81 (số)Vậy tổng số : 144 + 81 = 225 (số) C2: Số có dạng 7** : 9x9 = 81 (số) Số có dạng *7*: 8 x 9 = 72 (số) Số có dạng **7: 8x9 = 72(số) Tổng : 144 + 81 = 225 (số)Câu 1 tốt nghiệp năm 2010 (đợt 1)Cho 3 hộp bút bi, trong đó có một hộp bút màu xanh, một hộp bút màu đỏ và một hộpbút màu đen. Số lượng bút trong mỗi hộp là 10 cây và các cây bút trong mỗi hộp có hìnhthức và chất lượng như nhau. Có bao nhiêu cách lấy ra 10 cây bút từ 3 hộp bút đã chothỏa mãn từng điều kiện sau đây:Lý thuyết: Lấy n phần tử từ k loại : Cnn+k-1a)Số bút lấy ra ít nhất là 3: Trong 10 cây bút, ta lấy ra 3 cây bút màu xanh, còn lại 7 cây được lấy từ 3 loại bút ( vẫntính bút màu xanh) Tập nghiệm: C79b) Số bút màu xanh lấy ra nhiều nhất là 3:Với 10 cây bút lấy ra từ 3 loại, ta sẽ có tập nghiệm: C1012Với 10 cây bút lấy ra sao cho số bút màu xanh lấy ra ít nhất là 4, tập nghiệm: C68Vậy tập nghiệm cần tìm : C1012 – C68c) Số bút mỗi màu lấy ra ít nhất là 2:Lập luận tương tự câu a, với 10 cây bút lấy ra, mỗi màu ta lấy ra 2 cây, vậy còn 4 cây bútđược lấy ra từ 3 loại, tập nghiệm: C46d) Số bút màu xanh ít nhất là 3 và số bút màu đỏ nhiều nhất là 4:Ta có số bút mày xanh lấy ra ít nhất là 3 có tập nghiệm C79 (a), trong số này có cả tậpnghiệm số bút màu đỏ nhiều nhất là 4 và tập nghiệm số bút màu đỏ ít nhất là 5:Với 7 cây bút lấy ra từ 3 loại sao cho số bút màu đỏ lấy ra ít nhất là 5: C24Vậy tập nghiệm cần tìm : C79 – C24Câu 2: Một mật khẩu đọ dài 8 dạng XXXXXXYY, trong đó X là một chữ cái thườnglấy trong các chữ cái a,b,c,d và Y là một chữ số lấy trong các chữ số 0,1,…,9. Hỏi trongtrường hợp xấu nhất phải thử bao nhiêu lần để phát hiện mật khẩu nếu: a) Mật khẩu bắt đầu bằng chữ a: X ở vị trí 1 là a, 5 X còn lại mỗi X có thể có 4 trường hợp, và 2 Y mỗi Y có 10 trường hợp, vậy số lần thử là : 45 x 102 b) Mật khẩu bắt đầu bằng chữ a hoặc kết thúc bằng chữ số 9: Gọi P là số lần thử chuỗi kết thúc bằng 9 : 46 x 10 Gọi P là số lần thử chuỗi bắt đầu bằng a và kết thúc bằng 9 : 45 x 10 Số lần thử câu b : 45 x 102 + 46 x 10 – 45 x 10Câu 1 tốt nghiệp 2009 ( đợt 1)Một số nguyên dương được gọi là số palindrome nếu như khi đọc nó từ trái qua phảicũng như từ phải qua trái ta được cùng một số. Ví dụ : 1001, 20502 là các sốpalindrome. Hỏi có bao nhiêu xâu trong tập X = {1,2,…,1000000}Từ 1 đến 1000.000 gồm các số có 1,2,3,4,5,6 chữ số, xét từng trường hợp: Với độ dài bằng 1([1,9]) : có 9 số Với độ dài bằng 2([10,99]): Có 9 trường hợp :11,22,…,99 Với độ dài bằng 3([100,999]): Xâu palindrome có dạng : A*A với A={1,9} Số xâu : 9x10 = 90 (số) Với độ dài bằng 4([1000,9999]): Xâu palindrome có dạng: A**A với A = {1,9}, với mỗi ** là cặp số trùng nhau Số xâu : 9 x 10 = 90 (Số) Với độ dài bằng 5([10000,99999]): Xâu palindrome có dạng: A*B*A với A ={1,9}, ** là cặp số trùng nhau, B = {0,9} Số xâu : 9 x 10 x 10 = 900 (Số) Với độ dài bằng 6([100000,999999]): Xâu palindrome có dạng: A*BB*A với A ={1,9}, ** là các cặp trùng nhau, BB là các cặp trùng nhau Số xâu : 9 x 10 x 10 = 900 (số)Vậy tổng số là : 900 x 2 + 90 x 2 + 9 x 2Câu 2: Cho X là tập các xâu tam phân độ dài 8 chứa đúng 3 chữ số 0, 3 chữ số 1, 2 chữsố 2. Hỏi có bao nhiêu xau thỏa mãn từng điều kiện sau đây: a) Xâu bắt đầu bằng “00” : Có dạng 00****** 1 số 0 còn lại chiếm 1 vị trí, 3 chữ số 1 chiếm 3 vị trí, còn 2 vị trí của 2 số 2 C36 x C13 b) Xâu kết thúc bằng “22”: Có dạng ******22 3 số 0 chiếm 3 vị trí, còn 3 vị trí của 3 số 1 C36 Không thỏa 2 điều kiện trên: c) ...