Đang chuẩn bị liên kết để tải về tài liệu:
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. | Links downloaded from ToanDHSP.COM Bai tap toan roi rac co giai BÀI TẬP CHƯƠNG I 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. 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ự X do 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 cần thiết là 25.000.000 10.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. 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ối cù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ó 105 trường hợp. Theo nguyên lý Dirichlet số serial X tối thiểu phải thỏa mãn 10. 100 . Điều này không hợp lý vì số ký tự chữ cái chỉ là 26. Do số xe thì kết quả hợp lý hơn khi đó số serial là 10.000.000 100.000 vậy nếu bài toán sửa lại là 1 triệu bảng 1.000.000 _ 100.000 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ắc nhâ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ểu phải là 3 84 4. 10.000.000 _ 2.600.000 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 bang 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 8 vậy có 2 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