Luận văn Thạc sĩ Khoa học: Một số bài toán số học - Tổ hợp

Các bài toán số học tổ hợp từ lâu đóng một vai trò quan trọng trong việc rèn luyện tư duy toán học và kỹ năng giải toán. Bài toán số học tổ hợp có một số đặc điểm quan trọng mang tính khác biệt sau: Có thể giảng dạy tại các bậc, lớp khác nhau, không có khuôn mẫu nhất định cho việc giải (Không giống như việc giải phương trình, khảo sát hàm số, tính tích phân...). Do vậy đòi hỏi sự sáng tạo từ phía học sinh. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học: Một số bài toán số học - Tổ hợp ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ Trần Thanh NhãMỘT SỐ BÀI TOÁN SỐ HỌC - TỔ HỢP LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.01.13 Người hướng dẫn khoa học GS. TSKH. HÀ HUY KHOÁI HÀ NỘI, NĂM 2013 1Mục lụcLời mở đầu 3Lời cảm ơn 51 Một số kiến thức chuẩn bị 6 1.1 Kiến thức tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.6 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.7 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.8 Khai triển nhị thức Newton . . . . . . . . . . . . . . . . . . . 8 1.2 Kiến thức số học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Tính chia hết . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Biểu diễn cơ số . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Số nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.4 Ước chung lớn nhất, bội chung nhỏ nhất . . . . . . . . . . . 9 1.2.5 Thuật toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.6 Đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.7 Đồng dư tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.8 Thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.9 Một số định lý quan trọng . . . . . . . . . . . . . . . . . . . . 132 Một số bài toán Số học - Tổ hợp 14 2.1 Tính chất số học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Tính chia hết . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Biểu diễn số . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.1.3 Thuật toán Euclid và một số bài toán liên quan đến ước chung lớn nhất . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2 Bài toán chia kẹo Euler. . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.3 Bất biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.4 Cực trị trên tập hợp rời rạc . . . . . . . . . . . . . . . . . . . . . . . 61 2.5 Số phức - Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 23 Một số bài toán trò chơi 86 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3Lời mở đầu Toán rời rạc đóng một vai trò quan trọng trong toán học bởi vì nó có nộidung rất phong phú và có nhiều ứng dụng trong đời sống và thực tiễn. Trong các kì thi đại học, thi học sinh giỏi quốc gia, quốc tế, các bài toántổ hợp xuất hiện nhiều và thường có nội dung rất khó. Nhìn chung, nếu nhưviệc phân loại bài toán nào là số học, đại số, giải tích, hình học là tương đốirõ ràng thì việc phân loại các bài toán tổ hợp khá mơ hồ. Chính vì sự đadạng này nên việc giảng dạy và học tập chúng là một vấn đề khó khăn. Hơnnữa, trong chương trình toán phổ thông, tài liệu tham khảo về lĩnh vực tổhợp rất ít, nên luận văn này nhằm góp một phần kiến thức nhỏ bé để hổ trợcho việc học tập và giảng dạy, và bổ sung thêm tài liệu tham khảo về tổ hợp. Luận văn nhằm mục tiêu giới thiệu một số bài toán có thể gọi thuộc loạisố học - tổ hợp. Thực ra không có một định nghĩa nào cho loại bài toánnày. Nên luận văn này chỉ giới hạn ở việc đưa ra một số bài toán thường gặptrong các kì thi học sinh giỏi, mà việc giải chúng đòi hỏi những phương phápcủa số học và tổ hợp. Bố cục luận văn được chia thành ba chương: Chương 1 : Một số kiến thức chuẩn bịTrong chương này, chúng tôi trình bày một số kiến thức cơ bản về số học(tính chia hết, biểu diễn số, số nguyên tố, bội chung nhỏ nhất, ước chunglớn nhất, đồng dư, thặng dư, một số định lý quan trọng bao gồm: định lýWilson, định lý Fermat, định lý phần dư Trung Hoa) và một số kiến thứccơ bản về tổ hợp (quy tắc cộng, quy t ...