Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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ỉ. | ĐẠI HỌC QUỐC GIA THÀNH PHỐ HÒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN ẼQ 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 cm n - m n và N n 1 - 1 2 - . -1 1 vỉ ỉ ỉ nỉ m nỉ trong đó C - 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à 1 - ị - . -l nẰ 1 2 v J n 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 2 51 3. Vậy số mã vùng cân thiết 1000000 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 xi. -L. A A Á . T250000001 thoại thì cân có số mã vùng là để 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 ai 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
