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ẽ

Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.