Bài giảng Toán rời rạc - Bài tập phép đếm

Nội dung text: Bài giảng Toán rời rạc - Bài tập phép đếm

1. Trường đại học Cần Thơ Khoa Công nghệ thông tin và truyền thông Bộ môn Khoa học máy tính BÀI TẬP PHÉP ĐẾM 1
2. Bài tập 1  Có bao nhiêu cách chia 10 cuốn sách cho 3 sinh viên sao cho Lan nhận 5 cuốn, Cúc nhận 3 cuốn và Trúc nhận 2 cuốn sách. 2
3. Bài tập 1 10!  Số cách chia là: 5!3!2! 3
4. Bài tập 2  Trong thư viện có 3 loại sách máy tính, vật lý, lịch sử. Giả sử thư viện có ít nhất 6 cuốn cho mỗi loại. Tính số cách chọn 6 cuốn sách. 4
5. Bài tập 2  Số cách chọn 6 cuốn sách không phân biệt thứ tự, cho phép lặp lại từ 3 loại sách trong thư viện là: C(6 + 3 -1, 3 – 1) = C(8, 2) = 28. 5
6. Bài tập 3  Hỏi có bao nhiêu dãy nhị phân có chiều dài 10 bit mà mỗi dãy hoặc bắt đầu bằng 2 chữ số giống nhau hoặc kết thúc bằng 2 chữ số giống nhau. 6
7. Bài tập 3  Số dãy nhị phân có chiều dài 10 bit: 210 = 1024  Số dãy nhị phân có chiều dài 10 bit bắt đầu bằng 2 chữ số khác nhau và kết thúc cũng bằng 2 chữ số khác nhau: 4.26 = 256  Số dãy nhị phân có chiều dài 10 bit mà mỗi dãy hoặc bắt đầu bằng 2 chữ số giống nhau hoặc kết thúc bằng 2 chữ số giống nhau: 1024 – 256 = 768 7
8. Bài tập 4  Một con kiến bò theo các cạnh từ điểm M đến điểm N, theo chiều từ trái sang phải và đi lên hoặc đi xuống, trên một cái lưới như hình vẽ. Hỏi có bao nhiêu cách bò? M N 8
9. Bài tập 4  Mỗi hành trình mô tả bởi 1 chuỗi có độ dài 2n (n = 5)  Mỗi chuỗi nhận được bằng cách chọn n (n = 5) vị trí đối với đi lên (không quan tâm đến thứ tự) còn lại n (n = 5) vị trí đi xuống. 10!  Tổng đường đi: C(2n, n) = C(10, 5) = 5!5! 9
10. Bài tập 5  Xét chuỗi MISSISSIPPI. Có bao nhiêu chuỗi khác nhau khi sắp xếp lại các ký tự của chuỗi này? 10
11. Bài tập 5  Chiều dài chuỗi là 11, có C(11, 2) cách chọn vị trí ký tự P, có C(9, 4) cách chọn vị trí ký tự S sau khi đã chọn P, có C(5, 4) cách chọn vị trí ký tự I sau khi đã chọn P, S, cuối cùng chỉ còn lại vị trí ký tự M sau khi đã chọn P, S, I => Tổng các chuỗi khác nhau: C(11,2) C(9,4) C(5,4) = 11
12. Bài tập 6  Trong một hội thảo có n người, thảo luận về m chủ đề (với n > m), mỗi người tham dự vào ít nhất một chủ đề và có thể tham dự vào một vài chủ đề. Chứng minh rằng có hai người có số chủ đề tham dự bằng nhau. 12
13. Bài tập 6  Gọi ni là số chủ đề mà người thứ i tham dự : 1 ni m n số ni nhận m giá trị (n > m) theo nguyên lý Dirichlet => phải có ít nhất 2 số ni nào đó có cùng giá trị. 13
14. Bài tập 7  CM rằng trong 37 số nguyên bất kỳ, có thể chọn ra được 7 số mà tổng chia hết cho 7. 14
15. Bài tập 7  Số hộp = 7 (số dư của phép chia cho 7) Số vật = 37 Sắp số vào hộp “số dư của phép chia số đó cho 7” Nếu không có hộp nào rỗng => 7 số được chọn từ mỗi hộp một số có tổng chia hết cho 7 Nếu có hộp rỗng, 37 số được sắp vào 6 hộp Nguyên lý Dirichlet => có hộp chứa 37/6 = 7 số, tổng của 7 số lấy trong hộp này chia hết cho 7 15
16. Bài tập 8  CM rằng trong 100 số nguyên bất kỳ có thể chọn ra được hai số hiệu của chúng chia hết cho 57. 16
17. Bài tập 8  Số hộp = 57 (số dư của phép chia cho 57) Số vật = 100 Sắp số vào hộp “số dư của phép chia số đó cho 57” Nguyên lý Dirichlet => có hộp chứa 100/57 = 2 số, => 2 số đồng dư trong phép chia cho 57 => hiệu của 2 số này chia hết cho 57 17