Chương 1: Cơ sở lí luận và thực tiễn Chương 2: Xây dựng hệ thống bài tập Chương 3: Thực nghiệm sư phạm 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1 CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN 1. Tổ hợp và vai trò trong chƣơng trình chuyên toán 1. Tổ hợp Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán học có đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy tính. Nó còn được gọi là toán học dành cho máy tính.
Người ta thường kể đến trong Toán học rời rạc Lý thuyết Tổ hợp, Lý thuyết Đồ thị, Lý thuyết độ phức tạp, Đại số Boole. Một quan điểm rộng rãi hơn, gộp tất cả các ngành toán học làm việc với các tập hữu hạn hoặc đếm được vào toán học rời rạc như Số học modulo m, Lý thuyết nhóm hữu hạn, Lý thuyết mật mã,. Toán học Tổ hợp (hay Giải tích Tổ hợp, Đại số Tổ hợp, Lý thuyết Tổ hợp) là một ngành Toán học rời rạc, nghiên cứu về các cấu hình kết hợp các phần tử của một tập hữu hạn phần tử. Các cấu hình đó là các hoán vị, chỉnh hợp, tổ hợp,.
các phần tử của một tập hợp. Vai trò của Tổ hợp trong chương trình chuyên toán Trong phạm vi ở trường trung học phổ thông chuyên, Toán rời rạc nói chung và Toán Tổ hợp nói riêng bao gồm các bài toán có đặc trưng phát biểu và cách giải rất đơn giản, không cần nhiều kỹ thuật. Việc giải các bài toán này đòi hỏi sự sắc bén trong tư duy, sự trong sáng trong cách suy nghĩ. Mỗi bài toán rời rạc, Tổ hợp thường mang tính "riêng biệt", khó có thể hệ thống chúng lại với nhau.
Và rất nhiều bài toán đem lại cho người đọc một cảm giác thú vị vì lời giải của chúng rất đẹp, đơn giản và đầy bất ngờ. Tổ hợp là chủ đề khó trong chương trình trung học phổ thông chuyên. Trong các kì thi học sinh giỏi Toán các cấp, Tổ hợp thường chiếm tới 20 – 30 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com phần trăm tổng số bài. Tuy nhiên, học sinh Việt Nam nói chung còn tương đối yếu về mảng toán này.
Nguyên nhân chính là các bài toán này thường không yêu cầu nhiều kiến thức nhưng mỗi bài toán lại đòi hỏi những suy luận, sáng tạo riêng để giải quyết vấn đề. Ngoài ra cũng còn là vì Tổ hợp thường là các bài toán khó nhất, mang tính phân loại học sinh nên học sinh của chúng ta cũng thường có tư tưởng "sợ" Tổ hợp, coi Tổ hợp như một con "ngáo ộp" và vì vậy không dám dành thời gian thỏa đáng để nghiên cứu, học tập và giải toán Tổ hợp. Điều này gây nên sự lãng phí trong rất nhiều trường hợp. Một số dạng bài tập và phương pháp trong Tổ hợp Thực tế cho thấy, cả giáo viên lẫn học sinh hiện nay khi dạy và học Tổ hợp thường mới chỉ dừng lại ở mức độ tổng hợp bài tập và lời giải chứ chưa xây dựng được một hệ thống các phương pháp để phát triển tư duy sáng tạo và sự chủ động của học sinh trong chủ đề này.
Điều này dẫn đến khi học sinh gặp một bài toán Tổ hợp được phát biểu hơi khác những gì đã được học sẽ gặp những lúng túng nhất định, thậm chí là không phát hiện ra sự liên kết với các bài toán có liên quan. Trong mục này tác giả xin giới thiệu sơ lược một số dạng bài tập Tổ hợp, rời rạc và các phương pháp giải chúng: Phương pháp đếm bằng các quy tắc cơ bản Đây là các bài toán đếm số lượng các phần tử thỏa mãn một điều kiện cho trước nào đó mà các kiến thức cần huy động chỉ xoay quanh các quy tắc cộng, quy tắc nhân, hoán vị, tổ hợp, chỉnh hợp, chỉnh hợp lặp, quy tắc cộng tổng quát. Trong phần này điều quan trọng trong thực hành là học sinh phải biết cách phân chia công việc của mình thành các công đoạn đếm đơn giản với một thứ tự thực hiện tối ưu. Phương pháp đếm bằng truy hồi Phương pháp này thường xuất hiện trong các bài toán có số liệu là các số nguyên dương lớn hoặc số nguyên dương bất kỳ (điều này cũng hay gặp vì 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com nhiều đề toán hay có xu hướng ra số liệu phù hợp với năm thi).
Khi đó học sinh có thể tìm cách đưa bài toán đã cho về bài toán với số liệu nhỏ hơn 1, 2 đơn vị hoặc cũng có thể là nhỏ hơn nữa (tương ứng với bài toán truy hồi cấp 1, 2 hoặc cấp cao hơn). Phương pháp đếm bằng song ánh Phương pháp này đòi hỏi học sinh phải biết cách xây dựng một ánh xạ hợp lý để so sánh số phần tử của tập hợp này với một tập hợp khác mà việc đếm số phần tử của tập mới đơn giản hơn tập ban đầu. Hoặc trong nhiều trường hợp cũng có thể phải thay đổi cách nhìn của bài toán, chẳng hạn có khá nhiều bài toán có thể có cách nhìn đơn giản hơn bằng cách sử dụng xâu nhị phân. Phương pháp sử dụng hàm sinh Đây là một phương pháp khá đặc biệt và cũng tương đối "nhạy cảm" khi sử dụng sự hội tụ của chuỗi lũy thừa "hình thức" để đếm số phần tử hoặc tính toán rút gọn một tổng có nhiều, thậm chí là vô hạn phần tử.
Phương pháp sử dụng lý thuyết đồ thị Phương pháp này chuyển cách phát biểu của bài toán về cách phát biểu theo ngôn ngữ đồ thị. Ở dạng đơn giản nhất thì chỉ cần sử dụng các khái niệm, kết quả khá hiển nhiên xoay quanh bậc của các đỉnh. Ở các mức độ cao hơn có thể sử dụng các định lý, kết quả kinh điển như Euler, Hamilton, Ramsey, Ore, Dirac,. Phương pháp sử dụng số phức Số phức là một công cụ đặc biệt, một công cụ ảo nhưng có giá trị rất thật, không những được áp dụng có hiệu quả trong Hình học, Đại số, Lượng giác, Số học,.
mà trong Tổ hợp cũng có thể được sử dụng để đếm, chứng minh. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Phương pháp đếm bằng hai cách Đây là phương pháp sử dụng nguyên lý Fubini, hiểu nôm na giống như ta đếm số phần tử của một bảng ô vuông hình chữ nhật theo hai cách: cộng theo dòng hoặc cộng theo cột, từ đó có thể sử dụng để đếm kết quả bài toán hoặc để chứng minh các đẳng thức Tổ hợp. Phương pháp tô màu Tô màu thực chất là phân chia các đối tượng thành các nhóm có các tính chất khác nhau để từ đó chứng minh một đối tượng không thỏa mãn điều kiện đề bài yêu cầu hoặc là tìm ra tính chất của đối tượng thỏa mãn. Đương nhiên điều quan trọng nhất ở đây là nên chia các đối tượng này theo tính chất nào, cũng có nghĩa là nên tô màu như thế nào? Phương pháp sử dụng đại lượng bất biến, đơn biến Đây là phương pháp ta cần tìm ra các đại lượng không thay đổi hoặc là thay đổi theo chiều hướng đơn điệu trong suốt quá trình biến đổi mà bài toán đề cập đến.
Thông thường là xoay quanh tính đối xứng, tính chẵn lẻ, số dư khi chia cho một số nào đó, tổng, tích của các phần tử. Phương pháp sử dụng đại lượng cực biên Phương pháp này nghiên cứu tính chất của các đại lượng lớn nhất hoặc bé nhất theo một nghĩa nào đấy để giải bài toán. Phương pháp này có ý nghĩa trong cả các bài toán Đại số Tổ hợp cũng như Hình học Tổ hợp. Phương pháp sử dụng nguyên lý Dirichlet Phương pháp này xoay quanh nội dung rất đơn giản về chuồng và thỏ, tuy nhiên ứng dụng của nó rất đa dạng trong việc xây dựng đâu là chuồng và đâu là thỏ.
Mạng lưới nguyên Bài toán trên mạng lưới nguyên có liên quan đến bài toán về bảng ô vuông hay bài toán trên bàn cờ. Một kết quả hay sử dụng của phần này là định lý Pic về diện tích đa giác nguyên. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bài toán trên bàn cờ Cũng có nét giống bài toán trên mạng lưới nguyên, tuy nhiên các bài toán ở phần này còn đa dạng hơn do còn có cách di chuyển đặc trưng rất khác nhau của các quân cờ. Các bài toán về hình lồi Mảng bài tập phần này bao gồm nhiều bài toán khó về hình lồi, bao lồi.
Một kết quả hay sử dụng của phần này là định lý Helly về giao của các hình lồi. Các bài toán về trò chơi Phần này chỉ ra các đặc tính chung về tình huống thắng, tình huống thua, cách suy nghĩ đi tìm chiến thuật trong trò chơi, chẳng hạn: chiến thuật đối xứng, chiến thuật bất biến, chiến thuật tính ngược từ cuối. Các bài toán về phủ hình Các bài toán về phần này khá tổng hợp và liên quan nhiều đến các bài toán mạng lưới nguyên, bất biến, Dirichlet,. và đặc biệt là bài toán tô màu khi có rất nhiều bài toán phủ hình giải được bằng phương pháp này.
Các bài toán khác Với đặc thù của hai từ "rời rạc" thì cũng còn có rất nhiều bài toán có những lời giải đặc biệt khác mà khó có thể tổng hợp hay hệ thống chúng một cách tối ưu nhất. Đây cũng là điều làm nên sự thú vị và khó của các bài toán Tổ hợp, rời rạc. Phƣơng pháp dạy học phát triển tƣ duy sáng tạo trong Tổ hợp 1. Phương pháp dạy học phát triển tư duy sáng tạo Dạy học phát triển tư duy sáng tạo là phương pháp nhằm tìm ra các phương án, biện pháp thích hợp để kích hoạt khả năng sáng tạo và đào sâu khả năng tư duy của một cá nhân hay một tập thể về một đề tài hay lĩnh vực nào đó.
Phương pháp này giúp cá nhân hay tập thể thực hành tìm ra các phương án, các lời giải từ một phần cho đến toàn bộ cho các vấn đề nan giải. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Một số phương pháp giảng dạy mới nhằm phát triển tư duy sáng tạo cho học sinh: Phương pháp học theo dự án (Project Based Learning) Đây là mô hình học tập có nhiều khác biệt so với mô hình học tập truyền thống. Phương pháp học theo dự án yêu cầu các hoạt động học tập phải được thiết kế một cách cẩn thận, mang tính lâu dài và liên quan đến nhiều lĩnh vực học thuật. Đây là mô hình lấy người học làm trung tâm và hòa nhập với những vấn đề thực tiễn của thế giới thực tại.