Các bài Toán về nguyên lý số đếm

Chia sẻ: Trần Thị Thủy | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

64
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mời các em và giáo viên tham khảo về các bài Toán về nguyên lý số đếm sẽ giúp bạn định hướng kiến thức ôn tập và rèn luyện kỹ năng giải bài tập tốt hơn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các bài Toán về nguyên lý số đếm

Các bài toán v nguyên lý m CÁC BÀI TOÁN V NGUYÊN LÝ M I. TÓM T T LÝ THUY T 1. Ch nh h p Cho m t t p h p g m n ph n t ( 1 ≤ n ∈ » ) . M i b s p th t g m k ph n t trong s n ph n t ã cho ư c g i là m t ch nh h p ch p k c a n phân t ó. k S các ch nh h p ch p k c a n ph n t là: An = n ( n − 1) ... ( n − k + 1) = n! ( n − k )! 2. Hoán v : M t ch nh h p ch p n c a n ph n t ư c g i là m t hóan v c a n n ph n t ó. S các hoán v c a n ph n t là: Pn = An = n ( n − 1) ....2.1 = n ! 3. T h p: Cho m t t p h p n ph n t phân bi t. M i t p con g m k ph n t phân bi t không s p th t ( 0 ≤ k ≤ n ), l y trong s n phân t ã cho là m t t h p ch p k c a n ph n t . S các t h p ch p k c a n ph n t là: C n = 1 ⋅ An = k k n! k! k !( n − k ) ! 4. Qui t c c ng Cho X 1 , X 2 ,..., X n là các t p h p h u h n không giao nhau: X i ∩ X j = ∅ thì X 1 ∪ X 2 ... X n −1 ∪ X n = X 1 + X 2 + ... + X n −1 + X n v i X i là s ph n t . Ý nghĩa s h c: Gi s m t phép ch n ư c th c hi n qua n bư c c l p v i nhau trong ó: Bư c 1 có p1 cách th c hi n; Bư c 2 có p 2 cách; … Bư c n có p n cách. Khi ó có p1 + p 2 + ... + p n cách khác nhau th c hi n phép ch n. 5. Qui t c nhân Cho Cho X 1 , X 2 ,..., X n là các t p h p h u h n v i s ph n t : X i = p i , khi ó: X 1 × X 2 × ... × X n −1 × X n = p1 × p 2 × ... × p n −1 × p n Ý nghĩa s h c: Gi s m t phép ch n ư c th c hi n qua n bư c liên ti p trong ó: Bư c 1 có p1 cách th c hi n; Bư c 2 có p 2 cách ; … Bư c n có p n cách . Khi ó có p1 × p 2 × ... × p n −1 × p n cách khác nhau th c hi n phép ch n. 251
Chương III. T h p, Xác su t và S ph c − Tr n Phương II. CÁC D NG BÀI T P CƠ B N TRONG NGUYÊN LÝ M II.1. PHƯƠNG PHÁP CHUNG GI I BÀI TOÁN V C UT OS Gi s m, n là các s nguyên dương v i m ≤ n thì: m 1) S cách vi t m trong n ch s khác nhau vào m v trí nh trư c là An m 2) S cách vi t m ch s khác nhau trong n v trí nh trư c là An ( n − m v trí còn l i không thay i ch s ) 3) S cách vi t m ch s gi ng nhau trong n v trí nh trư c là C n − m = C n n m 4) Cho t p h p g m n ch s , trong ó có ch s 0, s các s có m ch s t o m thành t chúng là ( n − 1) An −−1 1 Th c v y, có ( n − 1) cách ch n ch s ng u, sau ó áp d ng m nh 2. Sau ây là các d ng toán thư ng g p. A. D ng 1. S T O THÀNH CH A CÁC CH S NH TRƯ C. Cho t p h p g m n ch s , trong ó có ch s 0, t chúng vi t ư c bao nhiêu s có m ch s khác nhau sao cho trong ó có k ch s nh trư c (thu c n ch s trên) v i k < m ≤ n . Cách gi i: S t o thành g m m v trí a1 a 2 ...a m . G i t p h p k ch s inh trư c là X. Ta xét hai bài toán nh theo các kh năng c a gi thi t v t p h p X và ch s 0 như sau: 1) Trong X ch a ch s 0 Ta có ( m − 1) cách ch n v trí cho s 0; S cách ch n ( k − 1) ch s khác 0 thu c X trong ( m − 1) v trí còn l i là Am −1k m− theo m nh (1) . Theo qui t c nhân, ta ư c s các s ó là S = ( m − 1) Am−1 ⋅ An −−kk k −1 m 2) Trong X không ch a ch s 0 Bư c 1: Tính s các s t o thành ch a ch s 0. L n lư t có ( m − 1) cách ch n v trí cho 0 ; 252
Các bài toán v nguyên lý m k S cách vi t k ch s thu c X vào ( m − 1) v trí còn l i là Am −1 theo m nh 2; S cách ch n ( m − k − 1) trong s ( n − k − 1) ch s khác 0 mà không thu c X vào ( m − k − 1) v trí còn l i là An −−kk−−1 theo m nh m 1 1. Theo qui t c nhân, ta ư c s các s ó là: S1 = ( m − 1) Am −1 ⋅ An −−kk−−1 k m 1 Bư c 2: Tính s các s t o thành không ch a ch s 0. k S cách vi t k ch s thu c X trong m v trí là Am theo m nh 2; S cách ch n ( m − k ) trong s ( n − k − 1) ch s khác 0 mà không thu c X vào ( m − k ) v trí còn l i là An −−kk−1 theo m nh m 1. Theo qui t c nhân, ta ư c s các s ó là: S 2 = Am ⋅ An −−kk−1 k m Bư c 3: Theo qui t c c ng, ta ư c s các s t o thành th a mãn bài toán là: S = S1 + S 2 Bài m u. T các s 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 có th l p ư c bao nhiêu s g m 6 ch s khác nhau sao cho trong các ch s ó có m t ch s 0 và 1? Gi i: Có 5 cách ch n v trí cho ch s 0. 4 V i m i cách ch n trên l i có 5 cách ch n v trí cho ch s 1 và có A8 cách ch n v trí cho 4 trong 8 ch s còn l i. 4 V y có t t c 5.5. A8 = 42000 s g m 6 ch s khác nhau và trong các ch s ó có m t ch s 0 và 1. B. D ng 2. S T O THÀNH KHÔNG CH A HAI CH S NH TRƯ C C NH NHAU Cho t p h p g m n ch s , t chúng vi t ư c bao nhiêu s có m ( m ≤ n ) ch s khác nhau mà trong ó có hai ch s nh trư c nào ó không ng c nh nhau. Cách gi i: S t o thành có d ng a1 a 2 ...a m và 2 ch s nh trư c là x, y (thu c n ch s ã cho) . Ta xét ba bài toán nh theo các kh năng c a gi thi t v ch s x, y và ch s 0 như sau: 1) N u n ch s ã cho ch a ch s 0 và hai ch s nh trư c x, y khác 0. Bư c 1: Tính s các s t o thành m t cách b t kì 253
Chương III. T h p, Xác su t và S ph c − Tr n Phương Có n − 1 cách ch n v trí cho ch s 0 và áp d ng m nh 2 ư c s các s ó m là: S1 = ( n − 1) An −−1 1 Bư c 2: Tính s các s có 2 ch s x, y c nh nhau theo th t xy và yx . TH1: a1 a 2 = xy . Khi ó m i s a 3 ...a m ng v i m t ch nh h p ch p ( m − 2 ) m c a ( n − 2 ) ch s khác x, y. S các s ó là: S 2 = An −−22 theo m nh 1. TH2: a1 a 2 ≠ xy . L n lư t ta có ( n − 3) cách ch n ch s cho a1 ≠ 0, x, y ; ( m − 2 ) cách ch n v trí cho xy ; S cách ch n ( m − 3) trong ( n − 3) ch s còn m l i khác a1 , x, y cho ( m − 3) v trí còn l i là An −−3 theo m nh 3 1. m Theo qui t c nhân, s các s ó là: S 3 = ( n − 3) ( m − 2 ) An −−3 . 3 T 2 trư ng h p trên, ta ư c s các s có ch a xy là S 2 + S 3 . Tương t có S 2 + S 3 s ch a yx . Bư c 3: V y s các s th a mãn bài toán là: S = S1 − 2 ( S 2 + S 3 ) . 2) N u n ch s ã cho ch a ch s 0 và m t trong hai ch s nh trư c b ng 0. m Bư c 1: Tính s các s t o thành m t cách b t kì: S1 = ( n − 1) An −−1 1 m Bư c 2: Tính s các s có 2 ch s x và 0 c nh nhau: S 2 = ( 2m − 3) An −−22 (có m – 1 cách vi t x0 và m – 2 cách vi t 0 x vào m v trí) Bư c 3: V y s các s th a mãn bài toán là: S = S1 − S 2 . m m 3) N u n ch s ã cho không ch a ch s 0: S = An − 2 ( m − 1) An −−22 Bài 1. T các s 0, 1, 2, 3, 4, 5, 6 có th l o ư c bao nhiêu s có 6 ch s khác nhau? Trong ó có bao nhiêu s mà ch s 1 và ch s 6 không ng c nh nhau? Gi i: Bư c 1: Tính s các s t o thành m t cách b t kì 5 Có 6 cách ch n ch s u tiên khác 0 và có A6 cách ch n 5 trong 6 s vào 5 5 v trí còn l i. V y có 6 A6 s có 6 ch s t o thành t các ch s trên. Bư c 2: Tính s các s có 2 ch s 1, 6 c nh nhau theo th t 16 và 61. TH1: N u 2 ch s u tiên là 1, 6, khi ó có 2! cách o v trí 2 s này. 254
Các bài toán v nguyên lý m 4 4 Có A5 cách ch n 4 trong 5 s vào 4 v trí còn l i. V y có 2 A5 s có 6 ch s t o thành t các ch s trên và có 2 s u tiên là 1 và 6. TH2: N u s u tiên khác 1 và 6, khi ó có 4 cách ch n s này khác 0. Có 4 cách ch n v trí cho 2 s 1 và 6 c nh nhau. 3 Có A4 cách ch n 3 trong 4 s vào 3 v trí còn l i. 3 M t khác ta có 2! cách o v trí 2 s 1 và 6 c nh nhau. V y có 4.4. A4 .2! s có 6 ch s có hai s 1, 6 ng c nh nhau và không ng u tiên. Bư c 3: V y s các s th a mãn bài toán là: S = 6 A6 − 2 ( A5 + 4.4. A4 ) = 3312 . 5 4 3 C. D ng 3. S T O THÀNH CH A CH S L PL I Ví d : Có bao nhiêu s t nhiên só 6 ch s sao cho trong ó có 1 ch s xu t hi n 3 l n, 1 ch s khác xu t hi n 2 l n và 1 ch s khác 2 ch s trên. L i gi i: N u k c trư ng h p ch s 0 ng u, l n lư t: 3 Có 10 cách ch n ch s xu t hi n 3 l n và có C 6 cách ch n 3 trong 6 v trí cho 2 ch s ó. Sau ó có 9 cách ch n ch s xu t hi n 2 l n và có C 3 cách ch n 2 trong 3 v trí còn l i cho ch s ó. Ti p theo có 8 cách ch n ch s cho v trí 3 2 3 2 còn l i cu i cùng. Ta ư c s các s ó là: S = 10.C 6 .9.C 3 .8 = 720.C 6 .C 3 . Do vai trò c a 10 ch s 0, 1, … 9 là như nhau nên s các s có ch s ng u khác 0 th a mãn bài toán là: 9 S = 648.C 6 .C 3 3 2 10 Bài toán t ng quát: Cho t p h p g m n ch s , t chúng vi t ư c bao nhiêu s có m ch s sao cho trong ó có m t ch s xu t hi n k l n, m t ch s khác xu t hi n q l n v i k + q = m . Cách gi i: Ta xét hai bài toán nh dư i ây: 1) N u n ch s ã cho có ch a ch s 0. Bư c 1: N u k c trư ng h p ch s 0 ng u, ta th y: k Có n cách ch n ch s xu t hi n k l n và có C m cách ch n k trong m v trí cho ch s ó. Sau ó có ( n − 1) cách ch n ch s xu t hi n q l n cho q v trí k còn l i. Theo qui t c nhân ta tính ư c s các s ó là: S = n ( n − 1) C m 255
Chương III. T h p, Xác su t và S ph c − Tr n Phương Bư c 2: Vai trò c a n ch s như nhau nên s các s có ch s ng u khác 0 th a mãn bài toán là: n − 1 S n k 2) N u n ch s ã cho không ch a ch s 0: S = n ( n − 1) C m Bài 1. T các ch s 0, 1, 2, 3, 4, 5 có th l p ư c bao nhiêu s g m 8 ch s trong ó ch s 1 có m t 3 l n còn m i ch s khác có m t úng 1 l n. Gi i Xét 8 ch s hình th c 0, 1a, 1b, 1c, 2, 3, 4, 5. Ta s l p s g m 8 ch s trên. Ch s u tiên (hàng ch c tri u) không th là 0 nên có 7 cách ch n. M i ch s ti p sau có th là s b t kỳ trong 7 ch s còn l i nên có 7! cách ch n. Như v y t t c có 7.7! s có 8 ch s . Do1a = 1b = 1c = 1 nên các ch s trên ã l p l i 3! = 6 l n. V y s các s th a mãn yêu c u bài toán là 7.7! = 5880 s . 3! Bài 2. Cho t p h p A = {1, 2, 3, 4, 5, 6, 7} a. T t p A có th l p ư c bao nhiêu s có 12 ch s sao cho ch s 5 có m t 3 l n, ch s 6 có m t 4 l n còn l i ch s khác có m t 1 l n? b. T t p A có th l p ư c bao nhiêu s có 7 ch s sao cho có 1 ch s l p l i 4 l n; m t ch s khác l p l i 2 l n và m t ch s khác v i hai ch s trên? Gi i a. + Có 3 C12 cách ch n v trí cho 3 ch s 5 4 + Có C 9 cách ch n v trí cho 4 ch s 6. + Có 5! cách x p 5 ch s còn l i vào 5 v trí. 3 4 V y có t t c : C12 .C 9 .5! = 3326400 s c n tìm. b. Bư c 1: Có 7 cách ch n ch s l p l i 4 l n t 7 ch s ã cho. 4 Có C 7 cách ch n v trí cho 4 ch s này. Bư c 2: Có 6 cách ch n ch s l p l i 2 l n t 6 ch s ã cho còn l i 2 Có C 3 cách ch n v trí cho 2 ch s này. Bư c 3: Có 5 cách ch n ch s xu t hi n 1 l n t 5 ch s ã cho còn l i. 4 2 V y s các s c n tìm là: 7.C 7 .6.C 3 .5 = 22050 s . 256
Các bài toán v nguyên lý m II.2. CÁC D NG BÀI TOÁN S H C TÍCH H P S V T, HI N TƯ NG A. D ng 1: BÀI TOÁN CH N V T 1) c trưng c a bài toán: Ch n m t t p h p g m có k ph n t t n ph n t khác nhau, k ph n t không có tính ch t gì thay i n u như hoán v k v trí c a nó. ây chính là c i m nh n d ng s d ng công th c t h p. 2. Phương pháp: Bư c 1: Li t kê các tính ch t có th có c a t p con c n ch n Bư c 2: Phân chia trư ng h p (n u có) k Bư c 3: Tính s cách ch n b ng cách d a vào công th c C n . Bư c 4: Dùng quy t c nhân và quy t c c ng ⇒ k t qu c a bài toán Bài 1. M t h p ng 7 viên bi xanh; 5 viên bi và 4 viên bi vàng. a) Có bao nhiêu cách l y ra 7 viên bi 3 màu, trong ó có 3 viên bi xanh và nhi u nh t 2 viên bi ? b) Có bao nhiêu cách l y ra 8 viên bi có 3 màu? Gi i a) Xét hai trư ng h p sau: TH1: Có 1 viên bi 1 : khi ó có C 5 cách l y 1 viên bi 3 ; có C 7 cách l y ra 3 3 1 3 3 viên bi xanh và có C 4 cách l y ra 3 viên bi vàng. V y có C 5 .C 7 .C 4 cách l y ra 7 viên bi trong ó có 3 bi xanh, 1 bi và 3 bi vàng. TH2: Có 2 viên bi 2 : khi ó có C 5 cách l y 2 viên bi 3 ; có C 7 cách l y ra 3 2 2 3 2 viên bi xanh và có C 4 cách l y ra 2 viên bi vàng. V y có C 5 .C 7 .C 4 cách l y ra 7 viên bi trong ó có 3 bi xanh, 2 bi và 2 bi vàng. 1 3 3 2 3 2 V y có t t c : C 5 C 7 C 4 + C 5 C 7 C 4 = 2800 cách. b) Bư c 1: Tính s cách l y ra 8 viên bi b t kỳ: có C16 cách 8 Bư c 2: Tính s cách l y ra 8 viên bi không có màu vàng mà ch có hai màu 7 1 6 2 5 3 4 4 3 5 xanh và : C 7 C 5 + C 7 C 5 + C 7 C 5 + C 7 C 5 + C 7 C 5 = 495 257
Chương III. T h p, Xác su t và S ph c − Tr n Phương Bư c 3: Tính s cách l y ra 8 viên bi không có màu mà có hai màu xanh và 7 1 6 2 5 3 4 4 vàng: C7 C 4 + C7 C4 + C7 C4 + C7 C4 = 165 Bư c 4: Tính s cách l y ra 8 viên bi không có màu xanh mà ch có hai màu 5 3 4 4 và vàng: C 5 C 4 + C 5 C 4 = 9 8 V y có t t c : C16 − ( 495 + 165 + 9 ) = 12201 cách. Chú ý: T bư c 2 ta có th tính theo cách sau: 8 Bư c 2: Tính s cách l y ra 8 viên bi trong t ng s 12 viên xanh và : C12 8 Bư c 3: Tính s cách l y ra 8 viên bi trong t ng s 11 viên xanh và vàng: C11 8 Bư c 4: Tính s cách l y ra 8 viên bi trong t ng s 9 viên và vàng: C 9 8 8 8 8 V y có t t c : C16 − (C12 + C11 + C 9 ) = 12201 cách. Bài 2. Có 8 con tem và 5 bì thư. Ch n ra 3 con tem dán vào 3 bì thư, m i bì thư dán 1 con tem. H i có bao nhiêu cách dán? Gi i 3 3 Ch n 3 con tem có C 8 cách; Ch n 3 bì thư có C 5 cách M t con tem có th dán vào bì thư nào cũng ư c trong 3 bì l y ra nên có t t 3 3 c : 3!C 8 C 5 = 3360 cách. Bài 3. Trên m t giá sách có 10 cu n sách giáo khoa và 7 cu n sách tham kh o. a) Có bao nhiêu cách l y 6 cu n trong ó có 2 cu n sách giáo khoa? b) Có bao nhiêu cách l y 7 cu n trong ó có ít nh t 4 cu n sách giáo khoa? Gi i a) Có C10 cách l y b t kỳ 2 cu n trong 10 cu n sách giáo khoa; Có C 7 cách 2 4 2 4 ch n 4 cu n còn l i trong 7 cu n sách tham kh o. V y có C10 C 7 = 1575 cách. b) Có C10 C 7 cách ch n trong ó có 4 cu n SGK và 3 cu n sách tham kh o 4 3 5 2 Có C10 C 7 cách ch n trong ó có 5 cu n SGK và 2 cu n sách tham kh o. 6 1 Có C10 C 7 cách ch n trong ó có 6 cu n SGK và 1 cu n sách tham kh o. 7 0 Có C10 C 7 cách ch n trong ó có 7 cu n SGK và 0 cu n sách tham kh o. 4 3 5 2 6 1 7 0 V y có C10 C 7 + C10 C 7 + C10 C 7 + C10 C 7 = 14232 cách. 258
Các bài toán v nguyên lý m B. D ng 2: BÀI TOÁN CH N NGƯ I Bài 1. L p 11A c a Tu n có 11 h c sinh nam và 18 h c sinh n . a. Có bao nhiêu cách ch n ra m t i văn ngh g m 10 ngư i nam và n . b. Ch n ra m t t tr c nh t g m 13 ngư i, trong ó có 1 t trư ng. H i có bao nhiêu cách ch n n u Tu n luôn có m t trong t và ch là thành viên? Gi i a. Bư c 1: Ch n 10 ngư i b t kì trong 29 ngư i c nam và n có C 29 cách 10 10 Bư c 2: Ch n 10 ngư i u là nam có C11 cách 10 Bư c 3: Ch n 10 ngư i u là n có C18 cách 10 10 10 V y có C 29 − C11 − C18 = 19986241 cách ch n. b. Do Tu n luôn có m t trong t nên ch ch n thêm 12 ngư i trong 28 ngư i 1 11 còn l i. Có C 28 cách ch n 1 t trư ng và C 27 cách ch n 11 thành viên còn l i. 1 11 V y có C 28 .C 26 = 216332480 cách ch n. Bài 2. M t trư ng trung h c có 7 th y d y Toán, 6 th y d y Lý và 4 th y d y Hóa. Ch n t ó ra m t i có 5 th y d i h i. H i có bao nhiêu cách ch n có 3 b môn? Gi i Ch n 1 th y d y Toán, 1 th y d y Lý, 3 th y d y Hóa có C 3 C 5 C 82 cách 1 1 1 2 2 Ch n 1 th y d y Toán, 2 th y d y Lý, 2 th y d y Hóa có C 7 C 6 C 4 cách 1 3 1 Ch n 1 th y d y Toán, 3 th y d y Lý, 1 th y d y Hóa có C 7 C 6 C 4 cách 2 1 2 Ch n 2 th y d y Toán, 1 th y d y Lý, 2 th y d y Hóa có C 7 C 6 C 4 cách 2 2 1 Ch n 2 th y d y Toán, 2 th y d y Lý, 1 th y d y Hóa có C 7 C 6 C 4 cách 3 1 1 Ch n 3 th y d y Toán, 1 th y d y Lý, 1 th y d y Hóa có C 7 C 6 C 4 cách 1 1 3 1 2 2 1 3 1 2 1 2 2 2 1 3 1 1 V y có t t c : C 7 C 6 C 4 + C 7 C 6 C 4 + C 7 C 6 C 4 + C 7 C 6 C 4 + C 7 C 6 C 4 + C 7 C 6 C 4 = 168 + 630 + 560 + 756 + 1260 + 840 = 4214 cách ch n. 259
Chương III. T h p, Xác su t và S ph c − Tr n Phương 5 S cách ch n 5 th y b t kì trong 17 th y là: C17 5 S cách ch n 5 trong 13 th y d y Toán và Lý là: C13 5 S cách ch n 5 trong 11 th y d y Toán và Hóa là: C11 5 S cách ch n 5 trong 10 th y d y Lý và Hóa là: C10 5 5 5 5 V y s cách ch n có c 3 b môn là: C17 − C13 − C11 − C10 = 4187 cách 6188 − 1287 − 462 − 252 Bài 3. L p 12A c a Ti n có 30 h c sinh. a. Hãy ch n trong l p Ti n m t t tr c nh t có 11 ngư i, trong ó có 1 t trư ng và còn l i các thành viên. H i có bao nhiêu cách ch n n u Ti n luôn có m t trong t ? b. Hãy ch n trong l p Ti n m t i văn ngh có 8 ngư i, trong ó có 1 i trư ng, 1 thư ký và các thành viên. H i có bao nhiêu cách ch n n u Ti n luôn có m t trong i? Gi i a. Khi Ti n luôn có m t trong t thì Ti n có th là t trư ng ho c thành viên. Xét 2 trư ng h p sau: TH1: N u Ti n là t trư ng thì có C 29 cách ch n 10 thành viên còn l i 10 TH2: N u Ti n là thành viên thì có C 29 cách ch n t trư ng và có C 28 cách 1 9 1 9 ch n 9 thành viên còn l i suy ra có C 29 .C 28 cách ch n 10 1 9 V y có t t c : C 29 + C 29 .C 28 = 20030010+200300100=220330110 cách ch n. 10 Chú ý: Có C 29 cách ch n 10 thành viên còn l i có t tr c nh t 11 ngư i trong ó có Ti n. Có 11 cách ch n 1 trong s ó làm t trư ng do ó s cách 10 ch n là: 11.C 29 = 220330110 cách. b. Có C 29 cách ch n 7 thành viên còn l i 7 ư c i văn ngh 8 ngư i trong ó có Ti n. Có 8 cách ch n i trư ng và ng v i m i cách l i có 7 cách ch n 7 thư kí. V y t ng s cách ch n là: 56.C 29 = 87403680 260
Các bài toán v nguyên lý m C. D ng 3. BÀI TOÁN S P X P V T Bài 1. Có bao nhiêu cách x p 15 viên bi vào 3 h p ng bi? Gi i V i m i viên bi ta có 3 cách ch n h p nên có 315 cách x p 15 viên bi vào h p. Bài 2. T i cu c thi "Theo dòng l ch s ", BTC s d ng 7 th vàng và 7 th , ánh d u m i lo i theo các s 1, 2, 3, 4, 5, 6, 7. H i có bao cách x p t t c các th này thành m t hàng sao cho hai th cùng màu không n m li n nhau? Gi i N u các th vàng n m v trí l thì các th n m v trí ch n, ta có 7!.7! cách x p khác nhau. + N u các th vàng n m v trí ch n thì các th n m v trí l , ta có 7!.7! cách x p khác nhau. V y có t t c : 7!.7! + 7!.7! = 50803200 cách. D. D ng 4: BÀI TOÁN S P X P NGƯ I Bài 1. M t t có 8 h c sinh 5 n và 3 nam. H i có bao nhiêu cách s p x p các h c sinh trong t ng thành m t hàng d c vào l p sao cho: a. Các b n n ng chung v i nhau b. Nam n không ng chung nhau Gi i a. Các b n n ng chung v i nhau ta xem như m t nhóm oàn k t nên có 4! cách. Có 5! hoán v 5 b n n v i nhau. V y có 5!.4! = 2880 cách. b. Các b n nam ng riêng ta có: 3! cách. Các b n n ng riêng ta có: 5! cách Có 2! cách i ch 2 nhóm nam và n nên có t t c : 2!.5!.3! = 1440 cách. Bài 2. i văn ngh c a trư ng g m 10 h c trong ó có 3 b n Lan, H ng, Nga h c cùng m t l p. H i có bao nhiêu cách x p i văn ngh thành m t hàng d c sao cho 3 b n Lan, H ng, Nga luôn bên c nh nhau? Gi i Ba b n Lan, H ng, Nga ng c nh nhau ta g i là m t nhóm oàn k t. + Nhóm oàn k t này cùng v i 7 h c sinh còn l i ta s có 8! cách s p x p +M il n i ch 3 h c sinh trong nhóm oàn k t ta ư c 3! cách s p x p. V y có t t c : 8!.3!= 241920 cách. 261
Chương III. T h p, Xác su t và S ph c − Tr n Phương E. D ng 5: BÀI TOÁN M TRONG HÌNH H C Bài 1. Xét các tam giác có 3 nh l y t các nh c a a giác u H có 10 c nh. a, Có t t c bao nhiêu tam giác? Có bao nhiêu tam giác có úng 2 c nh c a H? b. Có bao nhiêu tam giác có úng m t c nh là c a H? Có bao nhiêu tam giác không có c nh nào c a H? Gi i a. a giác có 10 c nh nên có 10 3 nh và có C10 = 120 tam giác có 3 nh là nh c a H. Tam giác có úng hai c nh c a a giác là tam giác t o b i 3 nh liên ti p c a a giác. ó là các tam giác: A1 A2 A3 , A2 A3 A4 , A3 A4 A5 ,..., A9 A10 A1 , A10 A1 A2 nên có úng 10 tam giác. b. Ch n m t c nh c a H và hai bên c nh này ta b i 2 c nh t c là b i4 nh, còn l i 6 nh. ng v i m t trong 6 nh và c nh ã ch n ta có m t tam giác có úng m t c nh c a H, nên có 6 tam giác ng v i m t c nh ã ch n ban u c a H. V y có 6.10 = 60 tam giác có úng 1 c nh là c nh c a H. T ó suy ra s các tam giác không ch a c nh nào c a H là: 120 – 10 – 60 = 50 tam giác. Bài 2. Cho 15 i m trên m t ph ng , trong ó không có 3 i m nào th ng hàng. Xét t p h p các ư ng th ng i qua 2 i m c a 15 i m ã cho. S giao i m khác 15 i m ã cho do các ư ng th ng này t o thành nhi u nh t là bao nhiêu? Gi i 2 C 2 i m có 1 ư ng th ng nên s ư ng th ng t 15 i m là: C15 = 105 2 N u c 2 ư ng th ng cho 1 giao i m thì s có C105 giao i m. Nhưng m i 2 i m ã cho có 14 ư ng th ng i qua nên i m này ph i là giao c a C14 c p 2 2 ư ng th ng. Như v y v i 15 i m ã cho s có 15. C14 giao i m trong C105 2 2 giao i m nói trên. Suy ra s giao i m c n tìm là: C105 − 15.C14 = 4095 Bài 3. Cho 2 h ư ng th ng c t nhau: H (L 1) g m 10 ư ng th ng song song v i nhau; H (L 2) g m 15 ư ng th ng song song v i nhau. H i có bao nhiêu hình bình hành ư c t o b i (L1) và (L2) Gi i M t hình bình hành ư c t o b i 2 ư ng th ng c a h (L 1) và 2 ư ng th ng 2 2 c a h (L2) nên s hình bình hành ư c t o b i là C10 C15 = 45 × 105 = 4725 262
Các bài toán v nguyên lý m F. D ng 6. BÀI TOÁN PHÂN CHIA T P H P Cho t p A có n ph n t khác nhau. Chia t p A thành các t p con A1 , A2 ,..., Ak ; trong ó m i t p con Ai ( i = 1, k ) có n i ( i = 1, k ) ph n t . Khi ó vi c ch n n i ph n t trong n ph n t là phép ch n và lo i tr d n các ph n t ã ư c ch n. Bài 1. C n ph i phát 6 thi khác nhau cho 4 em h c sinh. H i có bao nhiêu cách phát thi n u m i em h c sinh u làm ít nh t 1 bài thi? Gi i TH1: M i em u làm m t bài thi: 4 + Có C 6 = 15 cách ch n thi. + V i 1 cách ch n 4 thi phát cho 4 h c sinh s có 4! cách phát 4 4 V y có 4!C 6 = A6 = 360 cách phát thi mà m i em làm 1 bài. TH2: Có m t em nào ó làm 2 bài thi: 2 2 + Có C 6 cách ch n 2 bài thi trong 6 bài thi và có 4.C 6 cách phát 2 bài thi cho 1 trong 4 h c sinh. 3 + V i 4 bài thi còn l i s có A4 cách chia cho 3 thí sinh. 2 3 V y có 4.C 6 . A4 = 1440 cách phát thi mà trong ó có 1 em làm 2 bài thi. TH3: Có hai em nào ó làm 2 bài thi: 2 2 + Có C 6 cách ch n 2 bài thi trong 6 bài thi và có 4.C 6 cách phát 2 bài thi cho 1 trong 4 h c sinh. 2 2 + Có C 4 cách ch n 2 bài thi trong 4 bài thi còn l i và có 3.C 4 cách phát 2 bài thi cho 1 trong 3 h c sinh còn l i. + V i 2 bài thi còn l i s có 2! cách phát cho 2 thí sinh còn l i. 2 2 V y có 4.C 6 .3.C 4 .2! = 2160 cách phát thi mà trong ó có 2 em làm 2 bài thi. TH4: Có m t em nào ó làm 3 bài thi: 3 3 + Có C 6 cách ch n 3 bài thi trong 6 bài thi và có 4.C 6 cách phát 3 bài thi cho 1 trong 4 h c sinh. + V i 3 bài thi còn l i s có 3! cách phát cho 3 thí sinh còn l i. 3 V y có 4.C 6 .3! = 480 cách phát thi mà trong ó có 1 em làm 3 bài thi. 263
Chương III. T h p, Xác su t và S ph c − Tr n Phương K t lu n: T ng h p 4 trư ng h p ã xét ta có s cách phát thi m i em h c sinh u làm ít nh t 1 bài thi là: 4 2 3 2 2 3 4!C 6 + 4.C 6 . A4 + 4.C 6 .3.C 4 .2! + 4.C 6 .3! = 360 + 1440 + 2160 + 480 = 4440 cách Bài 2. Cho A là t p h p có 15 ph n t khác nhau. a. Có bao nhiêu t p h p con c a A? b. Có bao nhiêu t p h p con khác r ng c a A mà có s ph n t là s ch n? Gi i a. + S t p con c a A có 0 ph n t (t p r ng) là: C15 0 1 + S t p con c a A có 1 ph n t là C15 2 + S t p con c a A có 2 ph n t là C15 ………………………………………….. 15 + S t p con c a A có 15 ph n t là C15 0 1 2 15 15 V y t ng s t p h p con c a A là: C15 + C15 + C15 + ... + C15 = (1 + 1) = 215 b. Do C15 + C15 + C15 + C15 + ... + C15 + C15 = C15 + C15 + C15 + C15 + ... + C15 + C15 0 1 2 3 14 15 0 14 2 12 14 0 nên 215 = 2 ( C15 + C15 + C15 + ... + C15 ) suy ra C15 + C15 + ... + C15 = 214 − 1 0 2 4 14 2 4 14 V y s t p h p con khác r ng c a A có s ph n t ch n là: T = 214 − 1 . Bài 3. Cho t p h p A g m 20 ph n t khác nhau. Có bao nhiêu t p h p con khác r ng c a A mà có s ph n t là s ch n? Gi i S các t p con không r ng ch a m t s ch n các ph n t rút ra t t p h p 20 2 4 20 ph n t trên là S = C 20 + C 20 + ... + C 20 . Ta tính t ng S theo cách sau ây: 20 C 20 + C 20 + C 20 + ... + C 20 = (1 + 1) = 2 20 (1) 0 1 2 20 0 1 2 20 20 C 20 − C 20 + C 20 − ... + C 20 = (1 − 1) = 0 (2) L y (1) c ng v i (2) v theo v ta ư c: 2C 20 + 2C 20 + 2C 20 + ... + 2C 20 = 2 20 0 2 4 20 ⇔ C 20 + C 20 + C 20 + ... + C 20 = 219 ⇔ S = C 20 + C 20 + ... + C 20 = 219 − 1 0 2 4 20 2 4 20 V y s các t p con không r ng ch a m t s ch n các ph n t là S = 219 − 1 . 264