Tuyển tập các chuyên đề tổ hợp – Hoàng Minh Quân

Tài liệu cung cấp với một số dạng bài toán về sử dụng phép đếm để chứng minh các đẳng thức tổ hợp; phương pháp đếm bằng hai cách; phương pháp xây dựng mô hình trong giải toán tổ hợp; phương pháp hàm sinh; giải toán tổ hợp bằng đại lượng bất biến; một số bài toán tô màu; một số bài toán tổ hợp điển hình về bàn cờ.
Nội dung trích xuất từ tài liệu:
Tuyển tập các chuyên đề tổ hợp – Hoàng Minh Quân LỜI NÓI ĐẦUNgay từ năm 1736, nhà toán học Euler đã giải quyết thành công bài toán tổ hợp về bảy câycầu ở thành phố K¨onigsberg, Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel, bao gồmhai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Bài toán được đặt ra là “Có thểđi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát haykhông ?”. Và kể từ đó đến nay, trải qua nhiều thăng trầm của lịch sử, lí thuyết tổ hợp vẫn pháttriển mạnh mẽ, đóng góp nhiều cho sự phát triển của khoa học và kĩ thuật hiện đại. Chúng tathường gặp các bài toán tổ hợp trong các mô hình sản xuất như “Lập lịch cho một cơ quan”,xuất hiện trong giải pháp an toàn giao thông với các mô hình “Đặt các trạm xe bus tối ưu nhấttrong một thành phố”, vào quản lí con người với mô hình “Lập thời khoá biểu và phân việc”,. . . ,hoặc có thể ứng dụng gián tiếp trong các thuật toán giải các bài toán tối ưu trong các phầnmềm máy tính như thuật toán tìm kiếm của Google, Yahoo,. . . , hay các phần mềm ứng dụngmà chúng ta vẫn đang sử dụng hàng ngày. Chính vì vậy toán tổ hợp luôn dành được sự quantâm rất lớn từ các nhà toán học, các thầy, cô giáo và các bạn học sinh yêu thích môn toán.Toán tổ hợp là một lớp các bài toán khó, thường xuất hiện trong các kì thi học sinh giỏi cấptỉnh, thành phố, cấp quốc gia, quốc tế. Do đó, giải quyết thành thạo và có vốn kiến thức chắcchắn, sâu rộng về toán tổ hợp là niềm mong ước của nhiều giáo viên và học sinh. Mặc dù toántổ hợp quan trọng như vậy nhưng các tài liệu về toán tổ hợp, rời rạc dành cho học sinh giỏi ởViệt Nam vẫn còn rất ít và hạn chế. Xuất phát từ thực tế trên và với mục đích cung cấp tàiliệu chất lượng gồm nhiều chuyên đề toán tổ hợp nâng cao giúp cho việc học tập của học sinhtốt hơn và các thầy, cô giáo có thêm tài liệu giảng dạy, nhóm biên soạn bao gồm các giáo viên,các sinh viên hệ cử nhân tài năng toán, các học sinh giỏi quốc gia, quốc tế đến từ mọi miềncủa Tổ quốc đã cùng nhau viết nên các chuyên đề, các bài giảng về toán tổ hợp nâng cao.“Tuyển tập các chuyên đề tổ hợp” ra đời đánh dấu cho thành công lớn trong việc chia sẻ trithức cho cộng đồng các bạn yêu thích môn toán, mà ở đó những kinh nghiệm làm bài, nhữngcách giải hay và sáng tạo có được từ sự đúc kết trong thời gian học tập của nhiều thành viênđã và đang là học sinh giỏi quốc gia, quốc tế hay đầy tính sư phạm của các giáo viên tích lũyđược trong quá trình tham gia học tập, giảng dạy. Tuyển tập được hoàn thành và gửi tới bạnđọc trong dịp Tết Nguyên Đán, hi vọng nó sẽ là một món quà năm mới thực sự hữu ích vớibạn đọc trên khắp đất nước.Để hoàn thành cuốn sách, nhóm biên tập xin gửi lời cảm ơn sâu sắc tới các thầy giáo, cácbạn học sinh, sinh viên đã tham gia gửi các chuyên đề, các bài toán trên diễn đàn MathScope.Đồng thời cũng xin gửi lời cảm ơn sâu sắc tới ban quản trị diễn đàn MathScope và thầy giáo,TS. Trần Nam Dũng - ĐHKHTN - ĐHQG TP. Hồ Chí Minh đã cổ vũ, động viên và cho nhiềunhận xét có giá trị để cuốn sách vừa có giá trị chuyên môn cao mà lại miễn phí về tài chínhvới bạn đọc. 34Do thời gian gấp rút và trình độ có hạn, dù rất cố gắng nhưng sai sót là khó tránh khỏi. Mọiý kiến đóng góp để cuốn sách hoàn thiện hơn xin gửi về địa chỉ hoangquan9@gmail.com hoặcalephvn@gmail.com.Hà Nội, ngày 22 tháng 1 năm 2012 (ngày Tất niên năm Nhâm Thìn) Đại diện nhóm biên soạn Chủ biên Hoàng Minh Quân – Phan Đức Minh MỤC LỤCLời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Sử dụng phép đếm để chứng minh các đẳng thức tổ hợpNguyễn Tất Thu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Phương pháp đếm bằng hai cáchPhan Đức Minh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Phương pháp xây dựng mô hình trong giải toán tổ hợpLê Phúc Lữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Phương pháp hàm sinhHoàng Minh Quân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Phương pháp hàm sinhLê Hữu Phước, Trần Nguyễn Quốc Cường . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Giải toán tổ hợp bằng đại lượng bất biếnTrần Gia Huy . . . . . . . . . . . . . . . . . . . . ...