Nội dung

ĐẠ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 DANH SÁCH NHÓM I 1. NGÔ VĂN HÀO – 11520549 2. PHẠM MINH ĐỨC – 11520070 3. VĂN TẤN QUỐC – 11520312 4. TRẦN ANH KHOA – 11520178 5. LÊ ĐÌNH PHI – 11520282 6. PHẠM ĐĂNG VINH – 11520480 7. TRẦN PHƯƠNG CHUNG – 11520034 8. NGUYỄN HOÀNG HUY – 11520576 9. PHAN HUY TÀI – 11520340 10.LÊ VĂN TOÀN – 11520423 11. ĐẶNG ĐÌNH ĐỨC – 11520534 12.HỒNG MINH NHÂN – 10520615 13. PHẠM ĐỨC MẠNH – 10520443 14.NGUYỄN XUÂN THỌ - 09520673 15. TRẦN PHÚC THỊNH – 09520670 16. TRẦN HỮU LỘC – 09520556 17. NGUYỄN MẠNH HÙNG – 09520535 18. VY VĂN ANH – 11520010 19. NGUYỄN PHƯỚC LỘC – 08520654 20. ĐẶNG QUỐC THÁI - 08520340 Bài 1 : Giả sử A = {1,{1},{2}}. Hãy chỉ ra các khẳng định đúng trong số các khẳng định dưới đây : a) (Đúng) b) (Đúng) c) (Đúng) d) (Đúng) e) (Sai) (Sai) f) Bài 2 : Hãy liệt kê các phần tử trong các tập hợp dưới đây : a) {0,2} b) c) {1/( | } { } Bài 3 : Xét các tập hợp con của Z : A= C= E= , , B= D= F= Hãy xác định các khẳng định đúng trong số các khẳng định sau đây a) A = B (Đúng) d) D = E (Sai) b) A = C (Đúng) e) D = F (Đúng) c) B = C (Đúng) f) E = F (Sai) Bài 4 : Trong số các tập hợp dưới đây, tập hợp nào khác a) = b) c) d) e) f) ? = = = Q) Bài 5 : Xét 4 tập hợp con của tập hợp vũ trụ A = {1,2,3,4,5}, B = {1,2,4,8} C = {1,2,3,5,7}, D = {2,4,6,8} Hãy xác định các tập hợp dưới đây a) b) c) d) e) f) g) h) i) Giải a) Ta có : b) Ta có : c) Ta có : d) Ta có : - e) Ta có : f) Ta có : g) Ta có : h) Ta có : i) Ta có : Bài 6 : Xét các tập hợp con của Z : A = {2n | n ∊ Z}, C = {4n | n ∊ Z}, B = {3n | n ∊ Z} D = {6n | n ∊ Z} E = {8n | n ∊ Z} Hãy chỉ ra các khẳng định đúng trong các khẳng định dưới đây : a) E ⊂ C ⊂ A b) A ⊂ C ⊂ E c) D ⊂ B d) D ⊂ A e) B ⊂ D f) ⊂ (Đúng) (Sai) (Đúng) (Đúng) (Sai) (Sai) Bài 7 : Xét các tập con tùy ý A,B,C,D của tập hợp vũ trụ U. Hãy chứng minh các khẳng định dưới đây a) Nếu A ⊂ B và C ⊂ D thì b) Nếu A ⊂ C và B ⊂ C thì c) A ⊂ B khi và chỉ khi d) A ⊂ B khi và chỉ khi và và Giải a) Ta có - A ⊂ B và C ⊂ D (1) - (1) - (2) Điều phải chứng minh b)c)d) Tương tự Bài 8 : Dùng các quy luật của Lý thuyết tập hợp để đơn giản các biểu thức dưới đây a) b) c) Giải a) b) c) Bài 8: Một sinh viên có thể chọn bài thực hành từ 1 trong ba danh sách tương ứng có 29, 15, 31 bài. Vậy sinh viên đó có bao nhiêu cách chọn bài thực hành Giải Theo quy tắc cộng ta có : 29 + 15 + 31 = 75 (cách chọn) Bài 9 : Người ta ghi nhãn cho những chiếc ghế trong giảng đường bằng chữ và 1 số nguyên dương không vượt quá 100. Vậy có nhiều nhất bao nhiêu chiếc ghế được ghi nhãn khác nhau. Giải Thủ tục ghi nhãn cho một chiếc ghế gồm hai việc, gán một trong 26 chữ cái và sau đó gán một trong 100 số nguyên dương. Quy tắc nhân chỉ ra rằng có 26.100=2600 cách khác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán nhãn cho 2600 chiếc ghế. Bài 10 : Có bao nhiêu xâu nhị phân có độ dài n. Giải Mỗi một trong n bit của xâu nhị phân có thể chọn bằng hai cách vì mỗi bit hoặc bằng 0 hoặc bằng 1. Bởi vậy theo quy tắc nhân có tổng cộng 2 n xâu nhị phân khác nhau có độ dài bằng n. Bài 11 : Có thể tạo được bao nhiêu ánh xạ từ tập A có m phần tử vào tập B có n phần tử? Giải Theo định nghĩa, một ánh xạ xác định trên A có giá trị trên B là một phép tương ứng mỗi phần tử của A với một phần tử nào đó của B. Rõ ràng sau khi đã chọn được ảnh của i - 1 phần tử đầu, để chọn ảnh của phần tử thứ i của A ta có n cách. Vì vậy theo quy tắc nhân, ta có n.n...n=nm ánh xạ xác định trên A nhận giá trị trên B. Bài 12 : 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 = C nm (n - m)! = trong đó C nm = n! m!(n  m)! n! k! và N = n!(1  1 1! + 1 2!  ... + (1)n 1 ) 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 13 : 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 0XX8XXXXX 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 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à : . Vậy số mã vùng cần thiết để thỏa yêu cầu là 3. Bài 14 : 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ố từ 0-9. Hỏi 1 tỉnh cần đăng ký cho 1 triệu xe thì cần bao nhiêu serial X. Giải 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ả. Sáu số ký tự còn lại là N nhận giá trị từ 0-9 nên có trường hợp. Theo nguyên lý Dirichlet, số serial X tối thiểu phải thỏa mãn : Bài 15 : 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 16 : 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 17 : Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau. Giải Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của A hoặc có ít nhất ba người là kẻ thù của A, điều này suy ra từ nguyên lý Dirichlet tổng quát, vì = 3. Trong trường hợp đầu ta gọi B, C, D là bạn của A. nếu trong ba người này có hai người là bạn thì họ cùng với A lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người B, C, D không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau. Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ thù của A. Bài 18 : Cần phải có bao nhiêu SV ghi tên vào lớp TRR để chắc chắn có ít nhất 65 SV đạt cùng điểm thi, giả sử thang điểm thi gồm 10 bậc. Giải Gọi n là số sinh viên tối thiểu thỏa mãn đề bài, theo nguyên lý Dirichlet thì = 65. Do vậy n = 10 * 64 +1 = 641 SV. Bài 19 : Chỉ ra rằng nếu chọn 5 số từ tập 8 số {1, 2, …, 7, 8} thì bao giờ cũng có ít nhất 01 cặp số có tổng là 9. Giải Từ 8 số ở trên, ta chia thành 04 cặp: {1, 8}, {2, 7}, {3, 6}, {4, 5} và tổng của mỗi cặp đều bằng 9. Như vậy, đề bài sẽ trở thành chọn 5 số từ 4 cặp số trên. Theo nguyên lý Dirichlet, phải có ít nhất 01 cặp số được chọn hết. Vậy bài toán đã được chứng minh. Bài 20 : 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