Tủ sách Khoa học: Tổ hợp và các dạng toán rời rạc liên quan

Ngay từ năm 1736, nhà toán học nổi tiếng 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ỏnigsberg,Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel. Bài toán đặt ra là “ Có thể đi theo một tuyến đường mà chỉ đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát được hay không?”. Kể từ thời điểm đó, trải qua nhiều thăng trầm của lịch sử, lý thuyết tổ hợp vẫn tiếp tục phát triển mạnh mẽ và có nhiều ứng dụng trong khoa học và trong cuộc sống.

Thường nhật, chúng ta rất hay gặp các bài toán tổ hợp xuất hiện trong thực tiễn như: Lập thời khóa biểu, lập lịch công tác cho cơ quan, tìm vị trí tối ưu để đặt các trạm xe bus cho một thành phố, xây dựng thuật toán tìm kiếm và tra cứu của Google, Yahoo,.. .hay thiết lập các phần mềm ứng dụng mà hàng ngày chúng ta cần sử dụng. Chính vì lẽ đó mà 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 trẻ yêu thích môn toán rời rạc.

Có thể nói rằng dạng toán tổ hợp là dạng toán thuộc loại khó, thường xuyên 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, Olympic khu vực và quốc tế. Mặc dù toán tổ hợp quan trọng như vậy nhưng không có các giáo trình chính thống dễ đọc về nó.

Các vấn đề liên quan đến lý thuyết tổ hợp luôn được xem là một bộ phận quan trọng, hấp dẫn và lý thú của Toán học. Nó có nội dung rất phong phú về dạng toán cũng như thuật toán, có nhiều ứng dụng trong đời sống và trong khoa học kỹ thuật. Khi tiếp cận giải các bài toán tổ hợp những người quan tâm luôn cảm thấy hấp dẫn và hữu ích. Những ai mới bắt đầu làm quen với khái niệm tỗ hợp thường khó hình dung hết về độ phức tạp về cấu trúc trên các tập có cấu trúc đặc biệt,...

Tổ hợp và các dạng toán rời rạc liên quan

Trong những năm cuối của thế kỉ XX, ở Mỹ cũng như nhiều nước Tây Âu đã đưa Toán rời rạc vào chương trình giảng dạy trong nhà trường phổ thông. Tuy nhiên, ở nước ta, các dạng toán liên quan đến Tổ hợp và toán rời rạc vẫn chưa được giảng dạy hệ thống ở phổ thông và cả ở bậc cao đẳng và đại học.

Để đáp ứng cho nhu cầu bồi dưỡng giáo viên và bồi dưỡng học sinh giỏi, chúng tôi viết cuốn chuyên đề nhỏ này nhằm cung cấp một số kiến thức sơ cấp về tổ hợp và một số vấn đề thực hành liên quan. Đồng thời cũng cho phân loại một số dạng toán rời rạc theo dạng cũng như thuật toán giải chúng.

Đây cũng là nội dung bài giảng mà nhiều tác giả đã trình bày tại Trường Hè các năm từ 2003 đến 2009 cho các cán bộ và giáo viên các Trường THPT chuyên và không chuyên trong cả nước và một số tư liệu trong ’’Chuyên đề chọn lọc Tổ hợp và Toán rời rạc”, NXB Giáo dục 2008.

Trong tài liệu này, chúng tôi đã sử dụng một số bài tập mang tính hệ thống đã được các học viên cao học chuyên ngành "Phương pháp toán sơ cấp" thực hiện theo một lôgic nhất định dưới dạng các chuyên đề nghiệp vụ cho các đồng nghiệp quan tâm đến tổ hợp và toán rời rạc. Một số kiến thức bổ trợ tuy trùng lặp nhưng vẫn được
trình bày lại ở các mục khác nhau nhằm mô tả các đặc trưng riêng biệt để dễ đọc và dễ vận hành trong áp dụng.

Ngoài ra, chúng tôi cũng đưa vào xét một số vấn đề liên quan đến ứng dụng của tổ hợp trong Số học và Hình học. Một số dạng bài tập (cuối chương) được chọn lọc là các đề toán từ các kỳ thi học sinh giỏi các tỉnh, quốc gia và Olympic quốc tế nên không trình bày lời giải chi tiết ở đây. Một số dạng toán minh họa khác được trích từ
các tạp chí Toán học và Tuổi trẻ, Toán học trong nhà trường, Kvant, Mathematica, Krux, các sách giáo trình cơ bản về tổ hợp, các chuyên đề từ Trại hè Hùng Vương, Trại hè Phương Nam, các kỳ thi học sinh giỏi quốc gia và Olympic quốc tế cũng như một số đề thi Olympic sinh viên trong những năm gần đây.

Nội dung cuôn sách gồm phần mở đầu và 7 chương:

Chương 1. Một số tính chất cơ bản của tập rời rạc

Chương 2. Logic hình thức và áp dụng

Chương 3. Một số phương pháp thông dụng giải các bài toán đếm

Chương 4. Một số vấn đề thực hành giải toán rời rạc

Chương 5. Đẳng thức, bất đẳng thức và cực trị trong tổ hợp

Chương 6. Các dạng toán đếm trong hình học tổ hợp

Chương 7. Một số dạng toán tổ hợp trong số học

Tác giả xin chân thành cảm ơn các học viên cao học, các giáo viên bộ môn Toán từ các tỉnh, thành đã nghe giảng và đọc bản thảo, đã gửi những ý kiến đóng góp quan trọng cho nội dung cũng như cách trình bày thứ tự các chuyên đề. Đặc biệt, tác giả cảm ơn PGS.TSKH Vũ Hoàng Linh, GS.TS Đặng Huy Ruận, TS Trần Nam Dũng, PGS.TS Nguyễn Minh Tuấn, PTS.TS Nguyễn Thủy Thanh, PGS.TS Nguyễn Hữu Điển, PGS.TS Đàm Văn Nhỉ, Ths Nguyễn Duy Liên và nhiều thành viên trong Sem-inar liên trường - viện "Các chuyên đề Olympic" tại Trường Đại học Khoa học Tự nhiên, ĐHQGHN trong nhiều năm qua đã cổ vũ và giúp đỡ nhiệt tình để cuốn chuyên đề này được hoàn thành. Tác giả cũng xin bày tỏ lòng biết ơn tới các đồng nghiệp và các độc giả có ý kiến đóng góp để cuốn sách chuyên đề này được hoàn thiện.