TAILIEUCHUNG - Bài giảng Nhập môn lý thuyết tổng hợp: Chương 1 - Nguyễn Anh Thi
Bài giảng Nhập môn lý thuyết tổng hợp Chương 1 Mở đầu trình bày nội dung của bài học về: Nguyên lý chuồng bồ câu; Phương pháp quy nạp toán học (Quy nạp yếu và quy nạp mạnh),. . | Bài giảng Nhập môn Lý Thuyết Tổ Hợp Nguyễn Anh Thi ĐH KHTN, Tp HCM 2017 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 1 / 13 Chương 1 MỞ ĐẦU Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 2 / 13 Nội dung Nội dung 1 Nguyên lý chuồng bồ câu 2 Phương pháp quy nạp toán học Quy nạp yếu Quy nạp mạnh Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 3 / 13 Nguyên lý chuồng bồ câu Nguyên lý chuồng bồ câu (Derichlet) Gọi dxe là số nguyên nhỏ nhất lớn hơn hay bằng x. Giả sử có n chim bồ câu trong k chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ dn/ke bồ câu trở lên. Ví dụ Trong nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày. Ví dụ Chứng minh rằng trong 10 số tự nhiên bất kỳ có thể chọn 2 số có hiệu chia hết cho 9. HD: Khi chia 10 số bất kỳ cho 9 ta sẽ có mỗi số có một số dư trong 9 số dư: 0, 1, 2, . . . , 8. Do đó theo nguyên lý chuồng bồ câu phải tồn tại ít nhất hai số có cùng số dư. Hiệu của hai số đó sẽ chia hết cho 9. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 4 / 13 Nguyên lý chuồng bồ câu Ví dụ Trong một lớp học phải có ít nhất bao nhiêu học sinh để cho có ít nhất 6 học sinh chơi cùng một nhạc cụ, biết rằng có 5 loại nhạc cụ các học sinh được chọn học là A, B, C, D và E. HD: Gọi số học sinh của lớp là N. Theo nguyên lý chuồng bồ câu ta có d N5 e = 6. Khi đó 25 < N ≤ 30 Do đó ta có thể chọn N = 26. Vậy lớp phải có ít nhất 26 học sinh. Ví dụ Cho tập X = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có hai phần tử có tổng là 10. HD: Ta lập các chuồng như sau: {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Do A có 6 phần tử nên trong 6 phần tử đó sẽ
đang nạp các trang xem trước
