Bất đẳng thức và các bài toán cực trị trong đại số tổ hợp

Bài viết "Bất đẳng thức và các bài toán cực trị trong đại số tổ hợp" trình bày một số vấn đề liên quan tính chất và các dạng toán ứng dụng liên quan đến tổ hợp nhằm thể hiện rõ vai trò quan trọng của tổ hợp trong các dạng toán thi học sinh giỏi và Olympic quốc gia và quốc tế. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bất đẳng thức và các bài toán cực trị trong đại số tổ hợp Hội thảo khoa học, Ninh Bình 15-16/09/2018BẤT ĐẲNG THỨC VÀ CÁC BÀI TOÁN CỰC TRỊ TRONG ĐẠI SỐ TỔ HỢP Bùi Thị Lợi Trường THPT Yên Khánh A, Ninh Bình Tóm tắt nội dung Tổ hợp có vị trí rất quan trọng trong Toán học vì nó không những là một đối tượngnghiên cứu trọng tâm của Đại số và Giải tích mà còn là một công cụ đắc lực của toán rờirạc và lý thuyết trò chơi. Ngoài ra, tổ hợp còn được sử dụng nhiều trong tính toán và ứng dụng. Trong các kìthi học sinh giỏi toán quốc gia và Olympic toán quốc tế thì các bài toán về tổ hợp cũngthường được đề cập đến và được xem như những bài toán rất khó của bậc phổ thông. Việc khảo sát sâu hơn về các vấn đề tính toán tổ hợp và các dạng toán liên quan chota hiểu sâu sắc về lý thuyết cũng như các ứng dụng liên quan đến tổ hợp và toán rời rạc. Báo cáo này nhằm trình bày một số vấn đề liên quan tính chất và các dạng toán ứngdụng liên quan đến tổ hợp nhằm thể hiện rõ vai trò quan trọng của tổ hợp trong các dạngtoán thi HSG và Olympic quốc gia và quốc tế.1 Một số đẳng thức tổ hợp Trong phần này, để tính tổng liên quan đến tổ hợp hoặc chứng minh một đẳng thứctổ hợp, ta phải quan sát các số hạng trong tổng để tìm nhị thức cần khai triến, kết hợpvới các phép toán đạo hàm, tích phân hoặc các phép toán về số phức để giải bài toán.1.1 Tính chia hết của biểu thức tổ hợpBài toán 1 (Hungarian MO 2001). Cho m và n là các số nguyên. Chứng minh rằng m là m −1một ước của n ∑ (−1)k Cnk . k =0 114 Hội thảo khoa học, Ninh Bình 15-16/09/2018Lời giải. Ta có thể viết lại biểu thức đã cho như sau: m −1 m −1 n ∑ (−1)k Cnk = n ∑ (−1)k (Cnk −1 + Cnk− 1 −1 ) k =0 k =0 m −1 m −1 =n ∑ (−1)k Cnk −1 + n ∑ (−1)k Cnk− −1 1 k =0 k =0 m −1 m −2 =n ∑ (−1)k Cnk −1 − n ∑ (−1)k Cnk −1 k =0 k =0 m −1 = n(−1) Cnm−−11 = m(−1)m−1 Cnm . m −1Vậy m|n ∑ (−1)k Cnk . k =0Bài toán 2 (Chinese MO 1998). Xác định tất cả các số nguyên dương n ≥ 3 sao cho 22000chia hết cho 1 + Cn1 + Cn2 + Cn3 .Lời giải. Vì 2 là số nguyên tố nên Cn1 + Cn2 + Cn3 = 2k , với 0 ≤ k ≤ 2000.Ta có (n + 1)(n2 − n + 6) 1 + Cn1 + Cn2 + Cn3 = . 6Khi đó (n + 1)(n2 − n + 6) = 3.2k+1 .Đặt m = n + 1, thì m ≥ 4 và m(m2 − 3m + 8) = 3.2k+1 . Xét các trường hợp sau: +) Nếu m = 2s . Từ m ≥ 4, s ≥ 2 ta có 22s − 3.2s + 8 = m2 − 3m + 8 = 3.2t với mọi số nguyên dương t. . Nếu s ≥ 4 thì 8 − 3.2t ..16. Suy ra 2t = 8 ⇒ m2 − 3m + 8 = 24 ⇒ m(m − 3) = 16 (điều này không thể xảy ra).Như vậy hoặc s = 3, m = 8, t = 4, n = 7 hoặc s = 2, m = 4, t = 2, n = 3 . +) Nếu m = 3.2u . Từ m ≥ 4 và u ≥ 1 ta có 9.22u − 9.2u + 8 = m2 − 3m + 8 = 2v với mọi số nguyêndương v.Dễ dàng kiểm tra được rằng không có nghiệm nào của v khi u = 1; 2. . Nếu u ≥ 4 ta có 8 − 2v ..16, suy ra v = 3 và m(m − 3) = 0, điều này không thể xảy ra.Vì vậy u = 3, m = 3.23 = 24, v = 9, n = 23. Tóm lại, n = 3; 7; 23.Bài toán 3 (Gặp gỡ Toán học 2014). Cho p ≥ 5 là số nguyên tố và m, k ∈ Z+ . Chứng p −1minh rằng pk+2 |Cmpk −1 − 1.Lời giải. Để giải quyết tốt bài toán này chúng ta cần sử dụng những kiến thức hỗ trợ:Định lý 1 (Định lí Lagrange (về đa thức đồng dư)). Cho P( x ) là một đa thức hệ số nguyên bậcn và các hệ số của P( x ) không đồng thời chia hết cho p. Khi đó phương trình đồng dư P( x ) ≡ 0(mod p) có min{n, p} nghiệm. 115 ...