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 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 : Cỗ ườ ợ ẽ ị ặ ủ ự 32 = 3
V y v i m i xâu có d ng TTEậ ớ ỗ ạ BETT 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ố ừ ế
100<12k<1000
8,3<k<83,3 => k = 83-9+1 = 75 (s )ố
b)S chia h t cho 4 ho c 6ố ế ặ
100<4k<1000 => s chia h t cho 4: 225 (s )ố ế ố
100<6k<1000 => s chia h t cho 6:151 (s )ố ế ố
B = 225+151 – 75 = 301 (s )ố
c)S chia h t cho đúng 1 trong 2 s : 225 + 151 – 150 = 226 (s )ố ế ố ố
d)S không chia h t cho 4 và 6: 901 – 301 = 600 (s ) (T ng s tr câu b)ố ế ố ổ ố ừ
e) S ch a ít nh t 1 s không: ố ứ ấ ố
S có nhi u nh t 3 ch s 0 : 1000 có 1 giá trố ề ấ ữ ố ị
S có nhi u nh t 2 ch s 0ố ề ấ ữ ố
C1: là xâu có d ng A** (A [1,9]), 0 có 2 v trí **, v trí còn l i có 10 giá tr ([0.9])ạ ị ị ạ ị
9 x 10 x 2 = 180 + 1 = 181 (xâu)
Trong 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âu là : 181 – 9 = 172
C2: S có d ngố ạ
A*0 : Có 10x 9 = 90 (s )ố
A0* :Có 10x9 = 90 (s )ố
T ng 90 + 90 + 1 = 181 (s )ổ ố
Trong 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âuặ ẽ ặ ố ị ị ậ ổ ố
là : 181 – 9 = 172
f) 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 iố ạ ớ ố ằ ị ị ạ
có 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 pộ ộ ộ ộ ộ ỏ ộ ộ
bú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ìnhố ượ ỗ ộ ỗ ộ
th 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 đã choứ ấ ượ ư ấ ừ ộ
th a mãn t ng đi u ki n sau đây:ỏ ừ ề ệ
Lý thuy t: L y n ph n t t k lo i : Cế ấ ầ ử ừ ạ nn+k-1
a)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 nấ ạ ượ ấ ừ ạ ẫ
tính bút màu xanh)
T p nghi m: Cậ ệ 79
b) 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: Cớ ấ ừ ạ ẽ ậ ệ 1012
V 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: Cớ ấ ố ấ ấ ậ ệ 68
V y t p nghi m c n tìm : Cậ ậ ệ ầ 1012 – C68
c) 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: Cượ ấ ừ ạ ậ ệ 46
d) 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 Cố ấ ấ ậ ệ 79 (a), trong s này có c t pố ả ậ
nghi 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: Cớ ấ ừ ạ ố ỏ ấ ấ 24
V y t p nghi m c n tìm : Cậ ậ ệ ầ 79 – C24
Câu 2: M t m t kh u đ dài 8 d ng XXXXXXYY, trong đó X là m t ch cái th ngộ ậ ẩ ọ ạ ộ ữ ườ
l 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 trongấ ữ ộ ữ ố ấ ữ ố ỏ
tr 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à : 4ườ ợ ậ ố ầ ử 5 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 : 4ọ ố ầ ử ỗ ế ằ 6 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 : 4ọ ố ầ ử ỗ ắ ầ ằ ế ằ 5 x 10
S l n th câu b : 4ố ầ ử 5 x 102 + 46 x 10 – 45 x 10
Câ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 iộ ố ươ ượ ọ ố ế ư ọ ừ ả
cũ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 2 ậ ổ ố
Câ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
c) Không th a 2 đi u ki n trên:ỏ ề ệ