Bài tập chương 2: Số đếm

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN ---  --- BÀI TẬP CHƯƠNG 2: SỐ ĐẾM GVBM: CAO THANH TÌNH BÀI TẬP THUYẾT TRÌNH NHÓM I Bài 1 : Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì. Hỏi xác suất để xảy ra không một lá thư nào đúng địa chỉ. Giải Mỗi phong bì có n cách bỏ thư vào, nên có tất cả n! cách bỏ thư. Vấn đề còn lại là đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ. Gọi U là tập hợp các cách bỏ thư và Am là tính chất lá thư thứ m bỏ đúng địa chỉ. Khi đó theo công thức về nguyên lý bù trừ ta có: N = n!  N1 + N2  ... + (1)nNn, trong đó Nm (1  m  n) là số tất cả các cách bỏ thư sao cho có m lá thư đúng địa chỉ. Nhận xét rằng, Nm là tổng theo mọi cách lấy m lá thư từ n lá, với mỗi cách lấy m lá thư, có (n-m)! cách bỏ để m lá thư này đúng địa chỉ, ta nhận được: Nm = m nC (n - m)! = n k ! ! và N = n!(1  1 1! + 1 2!  ... + (1)n 1 n! ) trong đó m nC = )!(! ! mnm n  là tổ hợp chập m của tập n phần tử (số cách chọn m đối tượng trong n đối tượng được cho). Từ đó xác suất cần tìm là: 𝟏  𝟏 𝟏! + 𝟏 𝟐!  . . . +(−𝟏)𝒏 𝟏 𝐧! . Bài 2 : Số mã vùng cần thiết nhỏ nhất là bao nhiêu để đảm bảo 25 triệu máy điện thoại khác nhau. Mỗi điện thoại có 9 chữ số dạng 0XX-8XXXXX với X nhận giá trị từ 0-9 Giải Vì số mã vùng có dạng 0XX-8XXXXX, với X nhận các giá trị từ 0-9, có 7 ký tự X do vậy những 107 trường hợp. Do đó theo nguyên lý Dirichet với 10 triệu máy điện thoại thì cần có số mã vùng là : ⌈ 25000000 1000000 ⌉ = ⌈2,5⌉ = 3. Vậy số mã vùng cần thiết để thỏa yêu cầu là 3. Bài 3 : Trong một tháng gồm 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trận nhưng chơi không quá 45 trận. Chứng minh rằng tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận. Giải Gọi aj là số trận mà đội đã chơi từ ngày đầu tháng đến hết ngày j. Khi đó 1  a1 < a2 < ... < a30 < 45 15  a1+14 < a2+14 < ... < a30+14 < 59. Sáu mươi số nguyên a1, a2, ..., a30, a1+ 14, a2 + 14, ..., a30+14 nằm giữa 1 và 59. Do đó theo nguyên lý Dirichlet có ít nhất 2 trong 60 số này bằng nhau. Vì vậy tồn tại i và j sao cho ai = aj + 14 (j < i). Điều này có nghĩa là từ ngày j + 1 đến hết ngày i đội đã chơi đúng 14 trận. Bài 4 : Chứng tỏ rằng trong n + 1 số nguyên dương không vượt quá 2n, tồn tại ít nhất một số chia hết cho số khác. Giải Ta viết mỗi số nguyên a1, a2,..., an+1 dưới dạng aj = jk2 qj trong đó kj là số nguyên không âm còn qj là số dương lẻ nhỏ hơn 2n. Vì chỉ có n số nguyên dương lẻ nhỏ hơn 2n nên theo nguyên lý Dirichlet tồn tại i và j sao cho qi = qj = q. Khi đó ai= ik2 q và aj = jk2 q. Vì vậy, nếu ki  kj thì aj chia hết cho ai còn trong trường hợp ngược lại ta có ai chia hết cho aj. Bài 5 : Mỗi người sử dụng máy tính dùng password có 6 -> 8 ký tự. Các ký tự có thể là chữ số hoặc chữ cái, mỗi password phải có ít nhất 01 chữ số. Tìm tổng số password có thể có. Giải Phân biệt chữ thường với chữ hoa. Chữ cái thường: 26 Chữ cái hoa: 26 Chữ số: 10 Do đó, tổng cộng có 26 + 26 + 10 = 62 ký tự khác nhau. Nếu password có n ký tự thì ta có : Tổng số trường hợp = 62𝑛 Số trường hợp không có chữ số = 52𝑛 Vậy số trường hợp có ít nhất 1 chữ số là = 62𝑛-52𝑛 Với n = 6,7,8 ta có tổng số trường hợp là 𝑛 = 𝑛6 + 𝑛7 + 𝑛8 = 62 6 − 526 + 627 − 527 + 628 − 528 = 16 . 10. .5 3.0 0 Bài 6 : Có bao nhiêu xâu nhị phân có độ dài 10: a) Bắt đầu bằng 00 hoặc kết thúc bằng 11. b) Bắt đầu bẳng 00 và kết thúc bằng 11. Giải: a) Bắt đầu bằng 00 hoặc kết thúc bằng 11. Xâu nhị phân bắt đầu bằng 00 có dạng: 00.xxxx.xxxx. Ký tự x có thể là 0 hoặc 1, có 8 ký tự x do vậy có 28xâu. Xâu nhị phân kết thúc bằng 11 có dạng: xx.xxxx.xx11. Tương tư ta cũng tính được có 28 xâu. Xâu nhị phân bắt đầu bằng 00 và kết thúc bằng 11 có dạng 00.xxxx.xx11. Tương tự như trên, ta cũng tính được có 26 xâu. Vậy số xâu nhị phân bắt đầu bằng 00 hay kết thúc bằng 11 là: n = 2*28 - 26 = 512 – 64 =448 xâu. Bắt đầu bằng 00 và kết thúc bằng 11. Xâu nhị phân thỏa mãn đề bài phải có dạng: 00.xxxx.xx11. Hai ký tự đầu và 02 ký tự cuối là không đổi, do vậy chỉ còn 06 ký tự ở giữa. Do đó số xâu nhị phân thỏa mãn đề bài là: 𝟐 xâu. Bài 7 : Biết rằng số n nguyên dương thỏa mản biểu thức: 𝐶𝑛+1 2 + 2𝐶𝑛+2 2 + 2𝐶𝑛+3 2 + 𝐶𝑛+4 2 = 149 Tính giá trị biểu thức: M= 𝐴𝑛+1 4 + 3𝐴𝑛 3 (𝑛+1)! Giải: Xét phương trình: 𝐶𝑛+1 2 + 2𝐶𝑛+2 2 + 2𝐶𝑛+3 2 + 𝐶𝑛+4 2 = 149 (1) Khi 𝑛 + 1 ≥ 2 ⇒ 𝑛 + 2 > 2; 𝑛 + 3 > 2; 𝑛 + > 2. Vậy đk để (1) có nghĩa là 𝑛 ≥ 1, 𝑛 là số nguyên. Áp dụng công thức tính số tổ hợp ta có: (1)⟺ (𝑛+1)! (𝑛−1)!2! + 2 (𝑛+2)! 𝑛!2! + 2 (𝑛+3)! (𝑛+1)!2! + (𝑛+4)! (𝑛+2)!2! = 1 ⟺ 𝑛(𝑛+1) 2 + (𝑛 + 1)(𝑛 + 2) + (𝑛 + 2)(𝑛 + 3) + (𝑛+3)(𝑛+4) 2 = 1 ⟺ 𝑛2 + 𝑛 − 5 = 0 ⟺ 𝑛 = 5 ℎ𝑜ặ𝑐 𝑛 = − (𝑙𝑜ạ𝑖) Khi 𝑛=5, dễ dàng thấy M= 𝐴6 4+ 3𝐴5 3 6! = 3 4 Bài 8 : Cho hình thập giác lồi, hỏi có thể lặp được bao nhiêu tam giác có đỉnh là đỉnh của thập giác lồi nhưng cạnh không phải là cạnh của thập giác lồi? Giải: Gọi A là tất cả các tam giác có đỉnh là đỉnh của thập giác lồi. B là tam giác có đỉnh của là đỉnh của thập giác nhưng có it nhất 1 cạnh là cạnh của thập giác. C lá tam giác cần tìm. Ta có: |C| = |A| - |B| (1) Dễ thấy |A| = 𝐶10 3 = 120 (2) Gọi 𝐵1 là tam giác có 1 cạnh là cạnh của thập giác. 𝐵2 là tam giác có 2 cạnh là cạnh của thập giác. |𝐵| = |𝐵1| + |𝐵2| (3) Tính 𝐵1 - Chọn 1 cạnh của thập giác. Số cạnh là 𝑛1 = 10. - Chọn đỉnh của tam giác là 6 đỉnh còn lại 𝑛2 = 6. |𝐵1| = 10.6 = 60. Ta có |𝐵2| = 10. Theo đó |𝐵| = 60 + 10 = 0.(4) Từ (2)(3)(4) ta có |𝐶| = 120 − 0 = 50. Vậy có 50 tam giác thỏa yêu cầu. Bài 9 : Một thầy giáo có 12 cuốn sách đôi 1 khác nhau, gồm 5 cuốn văn học, 4 âm nhạc, 3 hội họa. Ông lấy 6 cuốn sách ra tặng cho 6 học sinh, mỗi hs 1 cuốn sau khi tặng xong mỗi loại còn lại ít nhất 1 cuốn. Hỏi có bao nhiêu cách chọn. Giải: Gọi A là tập hợp tất cả các cách tặng sách B là tập hợp cách tặng sách không thỏa yêu cầu. C là tập hợp cách tạng sách đủ yêu cầu. |C| = |A| - |B| (1) Ta có |A| = 𝐶12 6 6! = 6652 0.(2) Vì không thể xảy ra trường hợp còn lại 1 loại sách. Nên gọi |𝐵1| |𝐵2| |𝐵3| lần lượt là tập hợp tất cả các cách sau khi tặng xong hết sách văn học, hội họa, âm nhạc. |𝐵1| = 𝐶7 16! = 50 0 |𝐵2| = 𝐶8 26! = 20160 |𝐵3| = 𝐶9 36! = 60 0 |B|= 5040 + 20160 + 60480 = 85680 Từ (1)(2)(3) suy ra |C| = 665280 – 85680 = 579600 Bài 10 : Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két đựng tiền gồm những tờ 1000đ, 2000đ, 5000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ. Giả sử thứ tự mà các tờ tiền được chọn 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ờ. Giải: Vì ta không kể tới thứ tự chọn tờ tiền và vì ta chọn đúng 5 lần, mỗi lần lấy một từ 1 trong 7 loại tiền nên mỗi cách chọn 5 tờ giấy bạc này chính là một tổ hợp lặp chập 5 từ 7 phần tử. Do đó số cần tìm là 5 157 C = 462. Bài 11 : Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân? Giải: Người đầu tiên có thể nhận được 5 quân bài bằng 5 52C cách. Người thứ hai có thể được chia 5 quân bài bằng 5 47C cách. Vì chỉ còn 47 quân bài. Người thứ ba có thể nhận được 5 quân bài bằng 5 42C cách. Cuối cùng, người thứ tư nhận được 5 quân bài bằng 5 37C cách. Vì vậy, theo nguyên lý nhân tổng cộng có 5 52C . 5 47C . 5 42C . 5 37C = 52! 5 5 5 5 32!!. !. !. !. cách chia cho 4 người mỗi người một xấp 5 quân bài. Bài 12 : Giả sử một người gửi 10.000 đô la vào tài khoản của mình tại một ngân hàng với lãi suất kép 11% mỗi năm. Sau 30 năm anh ta có bao nhiêu tiền trong tài khoản của mình? Giải: Gọi Pn là tổng số tiền có trong tài khoản sau n năm. Vì số tiền có trong tài khoản sau n năm bằng số có sau n  1 năm cộng lãi suất của năm thứ n, nên ta thấy dãy {Pn} thoả mãn hệ thức truy hồi sau: Pn = Pn-1 + 0,11Pn-1 = (1,11)Pn-1 với điều kiện đầu P0 = 10.000 đô la. Từ đó suy ra Pn = (1,11)n.10.000. Thay n = 30 cho ta P30 = 228922,97 đô la. Bài 13 : Cho hai tập hợp A và B biết tập A B có số phần tử bằng một nửa số phần tử của B và A B có 7 phần tử. Hãy tìm số phần tử của mỗi tập hợp. Giải: Gọi x là số phần tử của tập A, y là số phần tử của tập B. Từ giả thiết và A B A B A B     ta có 7 2 y x y   hay 2 14x y  . Lại do A B có 7 phần tử suy ra 0 7B  hay 0 7y  mà 2 2 y A B y   Từ các kết quả trên ta có  0;2;4;6y , tương ứng ta có x nhận các giá trị 7; 6; 5;4. Bài 14 : Tính số các số tự nhiên đôi một khác nhau có 6 chữ số tạo thành từ các chữ số 0, 1, 2, 3, 4, 5 sao cho 2 chữ số 3 và 4 đứng cạnh nhau. Giải: Xét số có 5 chữ số gồm 0, 1, 2, 5 và chữ số “kép” là (3, 4). + Loại 1: chữ số hàng trăm ngàn có thể là 0. - Bước 1: sắp 5 chữ số vào 5 vị trí có 5! = 120 cách. - Bước 2: với mỗi cách sắp chữ số kép có 2 hoán vị chữ số 3 và 4. Suy ra có 120.2 = 240 số. + Loại 2: chữ số hàng trăm ngàn là 0. - Bước 1: sắp 4 chữ số vào 4 vị trí còn lại có 4! = 24 cách. - Bước 2: với mỗi cách sắp chữ số kép có 2 hoán vị chữ số 3 và 4. Suy ra có 24.2 = 48 số. Vậy có 240 – 48 = 192 số. Bài 15 : Tìm hệ số của x5 trong khai triển của biểu thức: 11 7 2 2 1 1 A x x x x                Giải: Công thức khai triển của biểu thức là:     11 7 7 11 2 11 72 0 0 11 7 11 3 14 3 11 7 0 0 1 1 1 k n k k n n k n k k k n n k n A C x C x x x A C x C x                         Để số hạng chứa x5 vậy k=2 và n=3. Vậy hệ số của x5 là 2 3 11 7 90C C  . Bài 16 : Chứng minh  k,n Z thỏa mãn  3 k n ta luôn có:          k k 1 k 2 k k 3 k 2 n n n n 3 n n C 3C 2C C C C . Giải: Ta có:                   k k 1 k 2 k k 3 k 2 k k 1 k 2 k 3 k n n n n 3 n n n n n n n 3 C 3C 2C C C C C 3C 3C C C (*)                                 k k 1 k 1 k 2 k 2 k 3 k k 1 k 2 k k 1 k 1 k 2n n n n n n n 1 n n 1 n 1 n n n 1VT(5) C C 2 C C C C C 2C C C C C C =      k k 1 k n 2 n 2 n 3 C C C ( điều phải chứng minh) Bài 17 : Tính giá trị biểu thức: 2 4 6 100 100 100 1004 8 12 ... 200A C C C C     Giải: Ta có:   100 0 1 2 2 100 100 100 00 1001 ...x C C x C x C x      (1)   100 0 1 2 2 3 3 100 100 100 00 100 1001 ...x C C x C x C x C x       (2) Lấy (1)+(2) ta được:     100 100 0 2 2 4 4 100 100 100 100 1001 1 2 2 2 ... 2x x C C x C x C x        Lấy đạo hàm hai vế theo ẩn x ta được     99 99 2 4 3 100 99 100 100100 1 100 1 4 8 ... 200x x C x C x C x       Thay x=1 vào => 99 2 4 100 100 100100.2 4 8 ... 200A C C C     Bài 18 : Khai triển và rút gọn đa thức:         9 10 14 1 1 ... 1Q x x x x       Ta được đa thức:   140 1 14...Q x a a x a x    Xác định hệ số a9. Giải: Hệ số x9 trong các đa thức       9 10 14 1 , 1 ,..., 1x x x   lần lượt là: 9 5 9 9 10 14, ,...,C C C Do đó: 9 5 9 9 10 14 1 1 1 1 ... 1 10 .10.11 .10.11.12 .10.11.12.13 .10.11.12.13.14 2 6 24 20 a C C C          =11+55+220+715+2002=3003. Bài 19 : Tìm hệ số của số hạng chứa 𝑥26 trong nhị thức Niutơn của ( 1 𝑥4 + 𝑥7)𝑛 biết 𝐶2𝑛+1 1 +𝐶2𝑛+1 2 +….+𝐶2𝑛+1 𝑛 =220-1 Giải: Áp dụng công thức : 𝐶𝑛 𝑘=𝐶𝑛 𝑛−𝑘 tìm n: 𝐶2𝑛+1 1 +𝐶2𝑛+1 2 +….+𝐶2𝑛+1 𝑛 = 𝐶2𝑛+1 2𝑛 +𝐶2𝑛+1 2𝑛−1+….+𝐶2𝑛+1 𝑛+1 ⇒ 𝐶2𝑛+1 0 +𝐶2𝑛+1 1 +….+𝐶2𝑛+1 2𝑛−1+𝐶2𝑛+1 2𝑛 +𝐶2𝑛+1 2𝑛+1= 2(220-1) +𝐶2𝑛+1 0 +𝐶2𝑛+1 2𝑛+1 ⇒ 22𝑛+1=221 ⇒2n+1=21 ⇒ n=10 Vậy số hạng chứa 𝑥26 là 210. Bài 20 : Cho 𝐶𝑛 0+ 2𝐶𝑛 1+22𝐶𝑛 2 +…+2𝑛𝐶𝑛 𝑛=6561 Tim hệ số của số hạng 𝑥7 và tổng tất cả cá hệ số của số hạng trong khai triển (𝑥2 − 3 𝑥 )𝑛 Giải: Ta có :(1 + 𝑥)𝑛=𝐶𝑛 0+𝐶𝑛 1.x+….𝐶𝑛 𝑛−1.𝑥𝑛−1+𝐶𝑛 𝑛. 𝑥𝑛 Khi đó x=2 ⇒6561=𝐶𝑛 0+𝐶𝑛 1.x+….𝐶𝑛 𝑛−1.22+𝐶𝑛 𝑛. 2𝑛=3𝑛 ⇒n=8 (𝑥2 − 3 𝑥 )𝑛=∑ 𝐶8 𝑘8 𝑘=0 .𝑥 2𝑘(−3)8−𝑘. 𝑥8−𝑘 =(−1)𝑘(3)8−𝑘 ∑ 𝐶8 𝑘8 𝑘=0 . (𝑥) 3𝑘−8 ⇒ 3k-8=7 ⇒k=5 ⇒ hệ số 𝑥7 là −𝐶8 5. 33=-1512 Tổng các hệ số: ∑ 𝐶8 𝑘8 𝑘=0 .(−3) 8−𝑘=(1 − 3)8=256 Bài 21 :Đội thanh niên xung kích của một trường phổ thông có 12 học sinh, gồm 5 học sinh lớp T, 4 học sinh lớp L và 3 học sinh lớp H. Cần chọn ra 4 học sinh tham gia trực tuần sao cho 4 học sinh đó thuộc không quá 2 trong 3 lớp nói trên. Hỏi có bao nhiêu cách chọn? Giải: Gọi A là tập tất cả các cách chọn 4 học sinh trong 12 học sinh. Gọi B là tập hợp tất cả các cách chọn không thoả mãn yêu cầu bài toán. Gọi C là tập hợp tất cả các cách chọn thoả mãn yêu cầu bài toán. Ta có  CBCBA , . Theo quy tắc cộng ta có |A|=|B|+|C| hay |C|=|A|-|B| Dễ thấy |A|= 4 12C . *Ta tính |B| Gọi x, y, z lần lượt là số học sinh của lớp T, L, H được chọn trong cách chọn thuộc B. Ta có hệ      31,41,51 ,,,4 zyx Nzyxzyx Hệ trên có nghiệm (1; 1; 2); (1; 2; 1); (2;1; 1). Vậy B= 1 3 1 4 2 5 1 3 2 4 1 5 2 3 1 4 1 5 ...... CCCCCCCCC  . Do đó |C|= 4 12C - 1 3 1 4 2 5 1 3 2 4 1 5 2 3 1 4 1 5 ...... CCCCCCCCC  Bài 22 : Tính số các số tự nhiên có 4 chữ số đôi một khác nhau được thành lập từ 0, 1, 2, 3, 4, 5 sao cho trong mỗi số đó đều có mặt ít nhất chữ số 1 hoặc 2. Giải: + Loại 1: chữ số a1 có thể là 0. Sắp 4 trong 6 chữ số vào 4 vị trí có 4 6A 360= cách. Sắp 4 chữ số 0, 3, 4, 5 vào 4 vị trí có 4! = 24 cách. Suy ra có 360 – 24 = 336 số. + Loại 2: chữ số a1 là 0 (vị trí a1 đã có chữ số 0). Sắp 3 trong 5 chữ số vào 3 vị trí có 3 5A 60= cách. Sắp 3 chữ số 3, 4, 5 vào 3 vị trí có 3! = 6 cách. Suy ra có 60 – 6 = 54 số. Vậy có 336 – 54 = 282 số. Cách khác: + Loại 1: Số tự nhiên có 4 chữ số tùy ý. - Bước 1: Chọn 1 trong 5 chữ số khác 0 sắp vào a1 có 5 cách. - Bước 2: Chọn 3 trong 5 chữ số khác a1 sắp vào 3 vị trí còn lại có 3 5A 60= cách. Suy ra có 5.60 = 300 số. + Loại 2: Số tự nhiên có 4 chữ số gồm 0, 3, 4, 5 (không có 1 và 2). - Bước 1: Chọn 1 trong 3 chữ số khác 0 sắp vào a1 có 3 cách. - Bước 2: Sắp 3 chữ số còn lại vào 3 vị trí 3! = 6 cách. Suy ra có 3.6 = 18 số. Vậy có 300 – 18 = 282 số. Bài 23 :Từ 4 chữ số 0, 1, 2, 3 lập thành các số tự nhiên có 3 chữ số phân biệt. Tính tổng các số được thành lập. Giải: + Xét số A có 3 chữ số phân biệt và chữ số hàng trăm có thể là 0. Từ 3 4A 24= số A ta lập được 12 cặp số có tổng là 333. Ví dụ 012 + 321 = 333. Suy ra tổng các số A là 12.333 = 3996. + Xét số B có 3 chữ số phân biệt và chữ số hàng trăm là 0. Từ 2 3A 6= số B ta lập được 3 cặp số có tổng là 44. Ví dụ 032 + 012 = 44. Suy ra tổng các số B là 3.44 = 132. Vậy tổng các số thỏa yêu cầu là 3996 – 132 = 3864. Cách khác: + Xét số A có 3 chữ số phân biệt và chữ số hàng trăm có thể là 0. - Số các số A là 3 4A 24= số. Số lần các chữ số có mặt ở hàng trăm, hàng chục và đơn vị là như nhau và bằng 24 : 4 = 6 lần. - Tổng các chữ số hàng trăm (hàng chục, đơn vị) của 24 số là: 6.(0 + 1 + 2 + 3) = 36. Suy ra tổng các số A là 36.(100 + 10 + 1) = 3996. + Xét số B có 3 chữ số phân biệt và chữ số hàng trăm là 0. - Số các số B là 2 3A 6= số. Số lần các chữ số 1, 2, 3 có mặt ở hàng chục và đơn vị là như nhau và bằng 6 : 3 = 2 lần. - Tổng các chữ số hàng chục (đơn vị) của 6 số là 2.(1 + 2 + 3) = 12. Suy ra tổng các số B là 12.(10 + 1) = 132. Vậy tổng các số thỏa yêu cầu là 3996 – 132 = 3864. Bài 24 :Tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1có ít nhất 5 bi, biết rằng hộp 2 và hộp 3 không chứa quá 6 bi. Giải: Trước hết ta tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi. Nhận xét rằng ta cần lấy 5 bi để xếp trước vào hộp 1, do đó số bi còn lại là 25. Suy ra số cách xếp trong trường hợp này bằng số cách xếp 25 bi vào 5 hộp mà không có điều kiện gì thêm. Số cách xếp đó là 𝐾5 25 = 𝐶5+25−1 25 = 𝐶29 25 = 23 51 (1). Tương tự ta có: - Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 2 chứa ít nhất 7 bi là 𝐾5 18 = 𝐶5+18−1 18 = 𝐶22 18 - Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 3 chứa ít nhất 7 bi là 𝐾5 18 = 𝐶5+18−1 18 = 𝐶22 18 - Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, mỗi hộp 2 và 3 chứa ít nhất 7 bi là 𝐾5 11 = 𝐶5+11−1 11 = 𝐶15 11 Sử dụng công thức |A∪ B| = |A| + |B| − |A∩ B| ta suy ra số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, đồng thời hộp 2 hay hộp 3 chứa ít nhất 7 bi là𝐾5 18 + 𝐾5 18 − 𝐾5 11 = 𝐶22 18 + 𝐶22 18 − 𝐶15 11 = 13265 (2) Theo yêu cầu bài toán, khi xếp 30 viên bi vào 5 hộp thì hộp 1 phải có ít nhât 5 bi còn mỗi hộp 2 và 3 phải có không quá 6 bi. Do đó số cách xếp này sẽ bằng hiệu của hai cách xếp (1) và (2), tức là bằng: 23751−13265=10486 . Bài 25:CM: 2n+1≤2n với n≥3=P(n) Giải: Ta có với n=3 => 2.3+1=7≤8 Giả sử với n=k thì : 2k+1≤2k (1) Ta sẽ cm p(n) đúng với n=k+1 Ta có 2k+1=2.2k≥2(2k+1)= 2(2k+1)+(2(k+1)+1)- (2(k+1)+1)= (2(k+1)+1)+2k-1 Mà k≥3 => 2k-1 >0 Vậy 2k+1≥2(k+1)+1) Vậy P(n) đúng với mọi n(dpcm) Bài 26:CM: n2≤2n với n≥4 Giải: Ta có với n=4 => 22=4≤22 Giả sử với n=k thì : k2≤2k (1) Ta sẽ cm p(n) đúng với n=k+1 Ta có 2k+1=2.2k≥ 2k2+(k+1)2-(k+1)2=2k2+k2-2k-1 Dễ thấy k2-2k-1>0(xét hàm f(k)= k2-2k-1 ngoài khoảng 2 nghiệm của f(k) nhận giá trị dương) Vậy 2k+1≥ ( k+1)2 Vậy P(n) đúng với mọi n(dpcm). Bài 27:Tìm hệ số của x101y99 trong khai triển (2x-3)200? Giải: Số hạng thứ 100 trong khai triển (2x-3)200 là C 99 200 (2x)101(-3y)99=2101.(-3)99 C 99 200 x101y99 Vậy hệ số của x101y99 là : 2101.(-3)99 C 99 200 . Bài 28:Phương án đánh số điện thoại. Giả sử một số điện thoại gồm 10 ký số được chia thành 3 nhóm: 2 nhóm gồm 3 ký số và một nhóm 4 ký số. Do một số lý do nào đó, có một số hạn chế trêncác ký số của số điện thoại. Để xác định dạng hợp lệ của một số điện thoại. ta dung ký hiệu X để chỉ một ký số có thể lấy giá trị từ 0 đến 9, N để chỉ một kýsố từ 2 đến 9, và Y chỉ một ký số là 0 hoặc 1. Chúng ta có 2 phương án để đánh số điện thoại : một phương án cũ và một phương án mới. Theo phương án cũ, số điện thoại có dạng NYX NNX XXXX; và theo phương án mới thì số điện thoại có dạng NXX NXX XXXX. Hỏi số lượng số điện thoại khác nhau của mỗi phương án là bao nhiêu? Giải: Do qui tắc nhân, đối với phương án đánh số điện thoại cũ, số trường hợp khác nhau của mỗi nhóm ký số trong 3 nhóm lần lượt là: 8.2.10 = 160 (ứng với dạng NYX), 8.8.10 = 640 (ứng với dạng NNX),và 10.10.10.10 = 10000 (ứng với dạng XXXX). Vậy, trong phương án đánh số điện thoại cũ, số lượng số điện thoại là 160. 640.10000 = 1 024 000 000. Tương tự Số lượng số điện thoại trong phương án đánh số mới là : (8.10.10).(8.10.10).(10.10.10.10) = 800.800.10000 = 6 400 000 000. Bài 29:Tính số các số tự nhiên đôi một khác nhau có 6 chữ số tạo thành từ các chữ số 0, 1, 2, 3, 4, 5 sao cho 2 chữ số 3 và 4 đứng cạnh nhau. Giải: Xét số có 5 chữ số gồm 0, 1, 2, 5 và chữ số “kép” là (3, 4). + Loại 1: chữ số hàng trăm ngàn có thể là 0. - Bước 1: sắp 5 chữ số vào 5 vị trí có 5! = 120 cách. - Bước 2: với mỗi cách sắp chữ số kép có 2 hoán vị chữ số 3 và 4. Suy ra có 120.2 = 240 số. + Loại 2: chữ số hàng trăm ngàn là 0. - Bước 1: sắp 4 chữ số vào 4 vị trí còn lại có 4! = 24 cách. - Bước 2: với mỗi cách sắp