Tuyển tập các chuyên đề tổ hợp

LỜI NÓI ĐẦU

Ngay 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ây cầu ởthành phốK¨onigsberg, Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel, bao gồm hai 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 hay khô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át triể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 ta thườ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ất trong 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ần mề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ụng mà 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ựquan tâ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ấp tỉ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ắc chắ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án tổ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ài liệ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 sinh tố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ền củ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ẻtri thứ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ững cá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ới bạ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ác bạ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ều nhậ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ính với bạn đọc.

3