BÀI TẬP CHƯƠNG 2 VỀ SỐ ĐẾM

Chia sẻ: Lê Quảng Vàng | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

76
lượt xem 5
download

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

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ỉ.

Chủ đề:

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

Lưu

Nội dung Text: BÀI TẬP CHƯƠNG 2 VỀ 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: và N = n!(1   ... + (1)n 1 Nm = C nm (n - m)! = n! k! 1! + 1 2! 1 n! ) n! trong đó C nm = là tổ hợp chập m của tập n phần tử (số cách chọn m đối m!(n  m)! 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 25000000 thoại thì cần có số mã vùng là : ⌈ ⌉ = ⌈2,5⌉ = 3. Vậy số mã vùng cần thiết 1000000 để 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 = 2 k j 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= 2 ki q và aj = 2 k j 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 = 626 − 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ó 28 xâ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: 2 2 2 2 𝐶𝑛+1 + 2𝐶𝑛+2 + 2𝐶𝑛+3 + 𝐶𝑛+4 = 149 𝐴4𝑛+1 + 3𝐴3𝑛 Tính giá trị biểu thức: M= (𝑛+1)! Giải: 2 2 2 2 Xét phương trình: 𝐶𝑛+1 + 2𝐶𝑛+2 + 2𝐶𝑛+3 + 𝐶𝑛+4 = 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)! (𝑛+2)! (𝑛+3)! (𝑛+4)! (1)⟺ +2 + 2 (𝑛+1)!2! + (𝑛+2)!2! = 1 (𝑛−1)!2! 𝑛!2!
𝑛(𝑛+1) (𝑛+3)(𝑛+4) ⟺ 2 + (𝑛 + 1)(𝑛 + 2) + (𝑛 + 2)(𝑛 + 3) + 2 =1 ⟺ 𝑛2 + 𝑛 − 5 = 0 ⟺ 𝑛 = 5 ℎ𝑜ặ𝑐 𝑛 = − (𝑙𝑜ạ𝑖) 𝐴46 + 3𝐴35 3 Khi 𝑛=5, dễ dàng thấy M= 6! =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) 3 Dễ thấy |A| = 𝐶10 = 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) 6 Ta có |A| = 𝐶12 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 | = 𝐶71 6! = 50 0 |𝐵2 | = 𝐶82 6! = 20160 |𝐵3 | = 𝐶93 6! = 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ử. 5 Do đó số cần tìm là C751 = 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: 5 Người đầu tiên có thể nhận được 5 quân bài bằng C52 cách. 5 Người thứ hai có thể được chia 5 quân bài bằng C 47 cách. Vì chỉ còn 47 quân bài.
5 Người thứ ba có thể nhận được 5 quân bài bằng C 42 cách. 5 Cuối cùng, người thứ tư nhận được 5 quân bài bằng C37 cách. Vì vậy, theo nguyên lý nhân tổng cộng có 52! 5 C52 . C47 5 . C42 5 . C37 5 = 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. y Từ giả thiết và A  B  A  B  A  B ta có x  y   7 hay 2x  y  14 . 2 y Lại do A  B có 7 phần tử suy ra 0  B  7 hay 0  y  7 mà A  B   y 2 2 Từ các kết quả trên ta có y 0;2;4;6 , 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  1  1 A   x  2    x2    x   x Giải: Công thức khai triển của biểu thức là: k  1   11 7 7n 1 A  C x k 11 k 11   x 2    C7 x n 2 k 0   n 0 xn 11 7  A    1 C x k 113k   C7n x143n k 11 k 0 n 0 Để số hạng chứa x5 vậy k=2 và n=3. Vậy hệ số của x5 là C11  C7  90 . 2 3 Bài 16 : Chứng minh k,n  Z thỏa mãn 3  k  n ta luôn có: Cnk  3Cnk 1  2Cnk 2  Cnk3  Cnk 3  Cnk 2 . Giải:
Ta có: Cnk  3Cnk 1  2Cnk 2  Cnk3  Cnk 3  Cnk 2  Cnk  3Cnk 1  3Cnk 2  Ckn3  Ckn3 (*)      VT(5)  Cnk  Cnk 1  2 Cnk 1  Cnk 2  Cnk 2  Cnk 3  Cnk1  2Cnk11  Cnk12  Cnk1  Cnk11  Cnk11  Cnk12  k 1 = Cn2  Cn2  Cn3 ( điều phải chứng minh) k k Bài 17 : Tính giá trị biểu thức: A  4C100  8C100  12C100  ...  200C100 2 4 6 100 Giải: Ta có: 1  x   C100  C100 x  C100 x 2  ...  C100 100 0 1 2 100 100 x (1) 1  x 100  C100 0  C100 1 x  C100 2 x 2  C100 3 x3  ...  C100 100 100 x (2) Lấy (1)+(2) ta được: 1  x 100  1  x 100  2C100 0  2C100 2 x2  2C100 4 x4  ...  2C100 100 100 x Lấy đạo hàm hai vế theo ẩn x ta được 100 1  x   100 1  x   4C100 x  8C100 x3  ...  200C100 99 2 99 4 100 99 x Thay x=1 vào => A  100.2  4C100  8C100  ...  200C100 99 2 4 100 Bài 18 : Khai triển và rút gọn đa thức: Q  x   1  x   1  x   ...  1  x  9 10 14 Ta được đa thức: Q  x   a0  a1x  ...  a14 x14 Xác định hệ số a9. Giải: Hệ số x9 trong các đa thức 1  x  , 1  x  ,..., 1  x  lần lượt là: C9 , C10 ,..., C14 9 10 14 9 5 9 Do đó:
1 1 1 1 a9  C99  C105  ...  C149  1  10  .10.11  .10.11.12  .10.11.12.13  .10.11.12.13.14 2 6 24 20 =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 1 2 𝑛 ( 𝑥 4 + 𝑥 7 )𝑛 biết 𝐶2𝑛+1 +𝐶2𝑛+1 +….+𝐶2𝑛+1 =220 -1 Giải: Áp dụng công thức : 𝐶𝑛𝑘 =𝐶𝑛𝑛−𝑘 tìm n: 1 2 𝑛 𝐶2𝑛+1 +𝐶2𝑛+1 +….+𝐶2𝑛+1 2𝑛 2𝑛−1 𝑛+1 = 𝐶2𝑛+1 +𝐶2𝑛+1 +….+𝐶2𝑛+1 0 2𝑛+1 0 ⇒ 𝐶2𝑛+1 1 +𝐶2𝑛+1 2𝑛−1 +….+𝐶2𝑛+1 2𝑛 +𝐶2𝑛+1 2𝑛+1 +𝐶2𝑛+1 = 2(220 -1) +𝐶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 3 (𝑥 2 − )𝑛 𝑥 Giải: Ta có :(1 + 𝑥)𝑛 =𝐶𝑛0 +𝐶𝑛1 .x+….𝐶𝑛𝑛−1 .𝑥 𝑛−1 +𝐶𝑛𝑛 . 𝑥 𝑛 Khi đó x=2 ⇒6561=𝐶𝑛0 +𝐶𝑛1 .x+….𝐶𝑛𝑛−1 .22 +𝐶𝑛𝑛 . 2𝑛 =3𝑛 ⇒n=8
3 (𝑥 2 − 𝑥)𝑛 =∑8𝑘=0 𝐶8𝑘 .𝑥 2𝑘 (−3)8−𝑘 . 𝑥 8−𝑘 =(−1)𝑘 (3)8−𝑘 ∑8𝑘=0 𝐶8𝑘 . (𝑥)3𝑘−8 ⇒ 3k-8=7⇒k=5 ⇒ hệ số 𝑥 7 là −𝐶85 . 33 =-1512 Tổng các hệ số: ∑8𝑘=0 𝐶8𝑘 .(−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ó A  B  C , B  C   . Theo quy tắc cộng ta có |A|=|B|+|C| hay |C|=|A|-|B| 4 Dễ thấy |A|= C12 . *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ệ  x  y  z  4, x, y, z  N  1  x  5,1  y  4,1  z  3 Hệ trên có nghiệm (1; 1; 2); (1; 2; 1); (2;1; 1). 1 Vậy B= C5 .C 4 .C3 1 2  C51 .C42 .C31  C52 .C41 .C31 .
Do đó |C|= C12 - C5 .C4 .C3  C5 .C4 .C3  C5 .C4 .C3 4 1 1 2 1 2 1 2 1 1 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ó A64 = 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ó A 53 = 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ó A 53 = 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ừ A 34 = 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ừ A23 = 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à A 34 = 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à A23 = 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à 𝐾525 = 𝐶5+25−1 25 25 = 𝐶29 = 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à 𝐾518 = 𝐶5+18−1 18 18 = 𝐶22 - 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à 𝐾518 = 𝐶5+18−1 18 18 = 𝐶22 - 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à 𝐾511 = 𝐶5+11−1 11 11 = 𝐶15 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à𝐾518 + 𝐾518 − 𝐾511 = 𝐶2218 18 + 𝐶22 − 𝐶1511 = 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à 99 (2x)101(-3y)99=2101.(-3)99 x101y99 99 C 200 C 200 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 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 30:Từ một nhóm 30 học sinh gồm 15 học sinh khối A, 10 học sinh khối B và 5 học sinh khối C chọn ra 15 học sinh sao cho có ít nhất 5 học sinh khối A và có đúng 2 học sinh khối C. Tính số cách chọn. Giải: + Loại 1: Chọn 2 học sinh khối C, 13 học sinh khối B hoặc khối A có C25C13 25 cách. + Loại 2: Chọn 2 học sinh khối C, 13 học sinh khối B và khối A không thỏa yêu cầu. - Trường hợp 1: Chọn 2 học sinh khối C, 10 học sinh khối B và 3 học sinh khối A 2 10 3 có C 5C10C15 cách. - Trường hợp 2: Chọn 2 học sinh khối C, 9 học sinh khối B và 4 học sinh khối A có C25C10 9 4 C15 cách. Vậy có C5 (C25 - C10C15 - C10C15 ) = 51861950 cách. 2 13 10 3 9 4 Bài 31:Cho tập hợp A={a,b,c,d},B={b,d,e},C={a,b,e}.Chứng minh: 1) A∩(B∖C)=(A∩B)∖(A∩C) 2) A∖(B∩C)=(A∖B)∪(A∖C).
Giải: 1) Ta có: B∖C={d},A∩B={b,d},A∩C={a,b} ⇒ (A∩B)∖(A∩C)=d. Suy ra: A∩(B∖C)={d},(A∩B)∖(A∩C)={d} Vậy: A∩(B∖C)=(A∩B)∖(A∩C) 2) Ta có: (B∩C)={b,e},A∖B={a,c},A∖C={c,d} Suy ra: A∖(B∩C)={a,c,d} ; (A∖B)∪(A∖C)={a,c,d} Vậy: A∖(B∩C)=(A∖B)∪(A∖C). Bài 32: Gọi A là tập hợp các học sinh của một lớp học có 53 học sinh, B và C lần lợt là tập các học sinh thích môn Toán, tập các học sinh thích môn Văn của lớp này. Biết rằng có 40 học sinh thích môn Toán và 30học sinh thích môn Văn. Hãy biểu diễn A,B,C dưới dạng biểu đồ. Tìm số phần tử lớn nhất và bé nhất có thể có của tập hợpB∩C. Giải: Gọi x là số học sinh thích cả hai môn Văn và Toán. Ta có biểu đồ như hình vẽ ở trang bên. * Số học sinh nhiều nhất thích cả hai môn là 30 em (lúc đó, tất cả 30 em thích môn Văn đều thích môn Toán). Do vậy, số phần tử lớn nhất có thể có của tập hợp B∩C là 30. * Ta có: 40+(30−x)≤ 53 hay x≥17. Vậy số phần tử bé nhất có thể có của tập hợp B∩C là 17 𝑥 4 Bài 33: Tìm số hạng không chứa x trong khai triển ( + )18 2 𝑥
Giải: 𝑥 4 Số hạng tổng quát trong khai triển ( + )18 = (2−1 𝑥 + −1 𝑥)18 là: 2 𝑥 𝑘 𝑘 3𝑘−18 𝐶18 (2−1 𝑥)18−𝑘 + ( 𝑥 −1 )𝑘 = 𝐶18 2 + 𝑥 18−2𝑘 Số hạng không chứa x ứng với 18-2k = 0 k = 9. Bài 34: Tính tổng sau: 0 1 2 3 2006 2007 S = 𝐶2007 - 2𝐶2007 + 22 𝐶2007 - 23 𝐶2007 +…+ 22006 𝐶2007 - 22007 𝐶2007 Giải: Ta có khai triển: 0 1 2 3 2006 2007 (1 − 2)2007 = 𝐶2007 - 2𝐶2007 + 22 𝐶2007 - 23 𝐶2007 +…+ 22006 𝐶2007 - 22007 𝐶2007 Vậy S = -1. Bài 35:Tính số tập hợp con của X = {0; 1; 2; 3; 4; 5; 6} chứa 1 mà không chứa 0. Giải: 0 + Số tập hợp con không chứa phần tử nào của X \ {0; 1} là C 5 . 1 + Số tập hợp con chứa 1 phần tử của X \ {0; 1} là C 5 . 2 + Số tập hợp con chứa 2 phần tử của X \ {0; 1} là C 5 . 3 + Số tập hợp con chứa 3 phần tử của X \ {0; 1} là C 5 . 4 + Số tập hợp con chứa 4 phần tử của X \ {0; 1} là C 5 . 5 + Số tập hợp con chứa 5 phần tử của X \ {0; 1} là C 5 . 0 1 2 3 4 5 Suy ra số tập hợp con của X \ {0; 1} là C 5 + C 5 + C 5 + C 5 + C 5 + C 5 = 32 . Ta hợp các tập hợp con này với {1} thì được 32 tập hợp thỏa bài toán. Bài 36: Từ các chữ số 1,2,3 lập được bao nhiêu số tự nhiên có đúng 5 chữ số 1, 2 chữ số 2 và 3 chữ số 3. Xem số cần lập có 10 chữ số gồm 5 chữ số 1 giống nhau, 2 chữ số 2 giống nhau và 3 chữ số 3 giống nhau. Giải: 10! Áp dụng hoán vị lặp ta có: = 2520 số. 5!2!3!