Bài tập toán rời rạc có lời giải

L Bài 1: 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ố có dạng 0XX-8XXXXX với X nhận giá trị từ 0 đến 9.
Nội dung trích xuất từ tài liệu:
Bài tập toán rời rạc có lời giảiBai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L BÀI TẬP CHƯƠNG IBài 1: 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ố có dạng 0XX-8XXXXX với X nhận giá trị từ 0 đến 9. Giải: Vì số mã vùng có dạng: 0XX-8XXXXX, với X nhận các giá trị từ 0 đến 9 (10 số), có 07 ký tự Xdo vậy sẽ có 107 trường hợp. Do đó, theo nguyên lý Dirichlet với 10 triệu máy điện thoại thì số mã vùng ⎤ 25.000.000 ⎡ = ]2,5[ = 3 . Vậy số mã vùng cần thiết thỏa yêu cầu bài toán là 3.cần thiết là: ⎥ ⎦ 10.000.000 ⎢ ⎣Bài 2: Biển số xe gồm 8 ký tự, dạng NN-NNNN-XN, ví dụ 75_1576_F1. Hai số đầu là mã tỉnh, X làchữ cái (26 chũ cái). N gồm các số 0, 1, …, 9. Hỏi một tỉnh nào đó cần đăng ký cho 10 triệu xe thìcần bao nhiêu serial (X). Giải Bài toán này có 02 cách hiểu: serial ở đây có thể là 02 ký tự NN đầu tiên hoặc là 02 ký tự XN cuốicùng.Cách hiểu 1: (serial là 02 ký tự XN cuối cùng). Hai số NN đầu là mã tỉnh, do nhà nước quy định nên không ảnh hưởng đến kết quả bài toán. Sáu ký tự còn lại có 5 ký tự là N, như vậy có 10 5 trường hợp. Theo nguyên lý Dirichlet, số serial ⎤10.000.000 ⎡ = 100 . Điều này không hợp lý vì số ký tự chữ cái chỉ là 26. DoX tối thiểu phải thỏa mãn: ⎥ ⎦ 100.000 ⎢ ⎣vậy, nếu bài toán sửa lại là 1 triệu bảng số xe thì kết quả hợp lý hơn, khi đó số serial là:⎤1.000.000 ⎡⎥ 100.000 ⎢ = 10 .⎦ ⎣Cách hiểu 2: (serial là 02 ký tự NN đầu tiên) Bốn ký tự NNNN sẽ có 104 trường hợp, 02 ký tự XN sẽ có 26*10 = 260 trường hợp. Theo quy tắcnhân, tổng số trường hợp sẽ là: 104*260 = 2.600.000. Do đó, theo nguyên lý Dirichlet, số serial tối thiểuphải là: ⎤ 10.000.000 ⎡ ⎥ 2.600.000 ⎢ = ]3,84[ = 4 . ⎦ ⎣ Vậy cần 04 số serial để đăng ký đủ cho 10 triệu xe.Bài 3: 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 dovậy có 2 8 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, tacũng tính được có 2 6 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à: 1BT Toan roi racBai tap toan roi rac co giai inks downloaded from ToanDHSP.COM L n = 2 * 2 8 − 2 6 = 512 − 64 = 448 xâu. b. 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à: 26 xâu.Bài 4: Khóa 29 CNTT có 150 SV học NNLT Java, 160 SV hoc Delphi, 40 SV học cả hai môn trên. a. Tìm tất cả SV của khóa 29 biết rằng SV nào cũng phải học ít nhất 01 môn. b. Biết tổng số SV là 285, hỏi có bao nhiêu SV không học Java hoặc Delphi. GiảiGọi J: SV học Java D: SV học Delphi a. Số SV của khóa 29 là: n1 = J U D = J + D − J I D = 150 + 160 − 40 = 270 SV b. Câu b có 02 cách hiểu:Cách 01: không học ít nhất 01 môn. Số SV không học Java hoặc Delphi là (áp dụng nguyên lý bù trừ) ta tính được:n 2 = n − J I D = 285 − 40 = 245 SVCách 02: không học Java cũng chẳng học Delphi: Theo cách hiểu này, áp dụng nguyên lý bù trừ ta tính được số SV như sau:n2 = J U D = n − J − D + J I D = 285 − 150 − 160 + 40 = 15 SV 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ặcchữ 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 Bài toán này cũng có thể được hiểu theo 02 cách.Cách 01: phân biệt chữ thường với chữ hoa. Chữ cái thường: 26 Chữ cái hoa: 26 Chữ số: 10Do đó, tổng cộng có 26 + 26 + 10 = 62 ký tự khác nhau.Nếu password có n ký tự. Tổng số trường hợp: 62 n Số password không có chữ số: 52 n Suy ra số password có ít nhất 01 chữ số: nn = 62 n − 52 nÁp dụng cho các trường hợ ...