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

4 phương trình sau liên quan đến bài này. 1 + 1 3 + 1 5 = 23 15 , 1 + 1 3 + 1 5 + 1 7 = 11× 16 105 , (1.58) 1 + 1 3 + 1 9 = 13 9 , 1 5 + 1 7 + 1 9 = 11× 13 315 . Vì vậy các phần tử của A không chia hết cho các số nguyên tố p ≤ 17, ngoại trừ có thể p = 23, và Ta cũng tìm thấy rằng 23, 27, 49, 75, 81, 125 /∈ A. Bây giờ ta kí hiệu A1 = 23 {1, 3, 5} , A2 = 11 {1, 3, 5, 7} , A3 = 13 {1, 3, 9} , A4 = 11 {5, 7, 9} , A5 = 13 {5, 7, 9} (1.59) trong đó p {a, b, c} nghĩa là {pa, pb, pc}. Đặt A0 = {d : 1 < d < h, d|h} , h = 315, (1.60) Tập hợp đúng 10 ước của h = 325× 7, sao cho A0 = {3, 5, 7, 9, 15, 21, 35, 45, 63, 105} , và chú ý rằng a ∈ A0 nếu và chỉ nếu h a ∈ A0. Theo lập luận của ta A phải là hợp của các tập hợp con của A0 và toàn bộ của 1 hoặc nhiều hơn các tập Ai trong (1.59). Ta chú ý rằng Ai∩Aj là rỗng, ngoại trừ đối với {i, j} ; i = 2, 4, {2, 4} , {3, 5} . Do đó năm tập hợp Ai trong (1.59) có dạng 17 phép hợp dời nhau, mỗi một trong số các phép hợp đó ta ghép thêm tập A0. Sáu phân số Ai Cập f(Ai) có giá trị sau đây f(Ai) = 44 45 , 1 15 , 16 105 , 1 9 , 13 315 , 11 315 , i = 0, 1, 2, 3, 4, 5, (1.61) và tổng của sáu số này là 1 + 121 h . Các phân số Ai Cập tương ứng với 17 phép hợp rời nhau có giá trị là 1 + r h , trong đó 1 < r < 121. Ta gọi r là thặng dư liên quan một phép hợp này hoặc tương ứng phân số Ai Cập, và ta định nghĩa các giá trị của r là số cách mà r có thể phân tích thành tổng các phần tử phân biệt của A0 trong (1.61). 19 Tất cả các lời giải với al ≤ 133 bây giờ có thể được tìm thấy, và số các lời giải là tổng của 17 giá trị. Ta bắt đầu tìm kiếm cho lời giải với al ≤ 105. Bằng (1.53) bất kì lời giải nào thu được từ một hợp của các tập hợp liên quan đến A1, A3, A5 phải chứa mẫu số có giá trị 23 × 5 = 105 hoặc 13 × 9 = 117. Do đó nếu có một lời giải với al ≤ 105 nó chỉ có thể thu được từ một phép hợp của A0 cùng với một trong hai tập hợp A2 hoặc A4. Từ (1) phép hợp của A0 ∪ A2 có thặng dư là 41, với một cách phân tích thành tổng các phần tử phân biệt của A0. Trên thực tế ta có f (A0 ∪ A2) = 44 45 + 16 105 = 1 + 5 + 15 + 21 315 = 1 + 1 63 + 1 21 + 1 15 . Vì 41 có duy nhất một cách phân tích thành tổng của a = 5, 15, 21 ∈ A0, với các ước liên hợp của chúng h a = 63, 21, 15 ∈ A0. Do đó Ta có một lời giải cho (1.53), cụ thể là f(A0 ∪ A2\ {15, 21, 63}) = 1 3 + 1 5 + 1 7 + 1 9 + 1 35 + 1 45 + 1 105 + 1 11 ( 1 + 1 3 + 1 5 + 1 7 ) = 1, mà là (1.55). Hơn nữa, khi các thặng dư của A0 ∪ A4 là 6, mà có một cách. Lời giải ở đây là chỉ có 1 với al ≤ 105. Định lý được chứng minh. Phép hợp của A0 ∪A5 có thặng dư là 4, mà 4 không có cách nào phân tích thành tổng các phần tử phân biệt của A0. Thặng dư r tương ứng với 14 phép hợp rời nhau còn lại thỏa mãn 14 ≤ r ≤ 97, với tất cả giá trị 1, 2 hoặc 3. Tổng của tất cả 17 giá trị là 29, số lời giải cho (1.53) với al ≤ 133. Cho một ví dụ của một phép hợp với thặng dư có 2 cách phân tích thành tổng các phần tử phân biệt của A0, ta lấyA0 ∪A1 ∪A4 mà có thặng dư là 27, với các phép phân tích 27 = 5 + 7 + 15 = 3 + 9 + 15. Có hai lời giải tương ứng là 1 3 + 1 5 + 1 7 + 1 9 + 1 15 + 1 35 + 1 105 + 1 23 ( 1 + 1 3 + 1 5 ) + 1 11 ( 1 5 + 1 7 + 1 9 ) = 1, và 1 3 + 1 5 + 1 7 + 1 9 + 1 15 + 1 45 + 1 63 + 1 23 ( 1 + 1 3 + 1 5 ) + 1 11 ( 1 5 + 1 7 + 1 9 ) = 1. Định lý 1.3. Mọi lời giải của phương trình (1.53) đều có dạng l ≥ 9. Các lời giải (1.56) là ứng với l = 9. Rõ ràng là, đối với biểu diễn phân số Ai Cập của một số nguyên, lũy thừa của một số nguyên tố mà chia hết cho một số mẫu số cũng phải chia hết cho mẫu số khác. Đây là điều kiện Diophantine quan trọng, mà Ta sử dụng để phát triển thành một phương pháp xây dựng theo đó tất cả các lời giải với al được cho dưới một giới hạn có thể được tìm thấy. Khi cố gắng để cho thấy rằng lời giải (1.54) đưa ra bởi Leech là tối ưu, Ta phát hiện ra rằng có 29 lời giải 20 với al < 135, một lời giải là tối ưu, đó là (1.55). Chứng minh. Dễ thấy (1.53) không có lời giải nếu l = 7. Cho nên a7 ≤ 23 thì 1 3 + 1 5 + 1 7 + 1 9 + 1 11 + 1 13 + 1 23 < 1, và rõ ràng rằng không có lời giải nếu a7 = 15, 17, 19, 21. Bây giờ Ta cố định l = 9 trong (1.53), vì vậy a9 ≤ 105 bởi Định lý 1.2; thực tế a9 ≤ 135 nếu Ta xem xét chứng minh của Định lý 1.2, nhưng bị chặn dưới nhỏ hơn là quá đủ. Đầu tiên, từ 1 3 + 1 5 + 1 9 + 1 11 + 1 13 + 1 15 + 1 17 + 1 19 + 1 105 < 1. Ta suy ra ngay rằng a1 = 3, a2 = 5, a3 = 7. Tương tự Ta thấy rằng a4 = 9 hoăc 11, và từ 1 3 + 1 5 + 1 7 + 1 9 + 1 11 + 1 13 + 1 67 + 1 69 + 1 105 < 1. Ta cũng suy ra rằng a7 ≤ 65. Tiếp theo, mỗi một trong C328 + C 3 27 = 6201 tập hợp của các số lẻ (a4, a5, a6, a7) thỏa mãn a4 = 9, 11, a4 < a5 < a6 < a7 ≤ 65. Ta viết 2m n = 1− ( 1 3 + 1 5 + 1 7 ) − ( 1 a4 + 1 a5 + 1 a6 + 1 a7 ) . (1.62) Đó một điều kiện cần thiết (1.62) có thể được giải thích là 0 < 2m n ≤ 1 a7 + 2 + 1 105 , mà được thỏa mãn bởi chỉ 78 giá trị 2m n cho bởi (1.62). Hơn nữa (1.53) viết lại là 1 a8 + 1 a9 = 2m n , (1.63) điều kiện a8 < a9 bây giờ có nghĩa là a8 < m n . Việc tìm kiếm tất cả các lời giải cho (1.53) không còn là lựa chọn hợp lý, bởi vì giá trị nhỏ nhất có thể có trong (1.62) là 1438 1036035 tương ứng với (a4, a5, a6, a7) = (9, 11, 13, 23), sao cho a8 < 1441 cho trường hợp xấu nhất của 78 trường hợp. Nó chỉ ra rằng chỉ có 3 giá trị trong (1.62) mà trong đó (1.63) là giải được. Đặc biệt hơn, Ta cần có a4 = 9, a5 = 11, a6 = 15, và a7 = 21, 33, 35 đưa ra chỉ với giá trị n = 3465 = 3 25× 7× 11 và ba giá trị tương ứng m = 13, 43, 46. Lời giải cho (1.63) được cho như sau. Khi a7 = 21,m = 13,Ta có (a8, a9) = (135, 10395), (165, 693), (231, 315). Khi a7 = 33,m = 43,Ta có (a8, a9) = (45, 385). Khi a7 = 35,m = 46,Ta có (a8, a9) = (45, 231). Năm lời giải tương ứng cho (1.53) cũng được đưa ra trong (1.56). Định lý được chứng minh. 21 1.5 Một số dạng toán thi Olympic liên quan 1.5.1 Tính chia hết của biểu thức tổ hợp Bài toán 1.8 (Hungarian MO 2001). Cho m và n là các số nguyên. Chứng minh rằng m là một ước của n m−1∑ k=0 (−1)kCkn. Lời giải. Ta có thể viết lại biểu thức đã cho như sau: n m−1∑ k=0 (−1)kCkn = n m−1∑ k=0 (−1)k(Ckn−1 + Ck−1n−1) = n m−1∑ k=0 (−1)kCkn−1 + n m−1∑ k=0 (−1)kCk−1n−1 = n m−1∑ k=0 (−1)kCkn−1 − n m−2∑ k=0 (−1)kCkn−1 = n(−1)m−1Cm−1n−1 = m(−1)m−1Cmn . Vậy m|n m−1∑ k=0 (−1)kCkn. Bài toán 1.9 (Chinese MO 1998). Xác định tất cả các số nguyên dương n ≥ 3 sao cho 22000 chia hết cho 1 + C1n + C 2 n + C 3 n. Lời giải. Vì 2 là số nguyên tố nên C1n + C 2 n + C 3 n = 2 k, với 0 ≤ k ≤ 2000. Ta có 1 + C1n + C 2 n + C 3 n = (n+ 1)(n2 − n+ 6) 6 . Khi đó (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 . 22 +) 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ên dươ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 1.10 (Gặp gỡ Toán học 2014). Cho p ≥ 5 là số nguyên tố và m, k ∈ Z+. Chứng minh rằng pk+2|Cp−1 mpk−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.4 (Định lí Lagrange (về đa thức đồng dư)). Cho P (x) là một đa thức hệ số nguyên bậc n 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. Bổ đề 1.4. Nếu phương trình P (x) ≡ 0 (mod p) có số nghiệm nhiều hơn bậc của P (x) thì tất cả các hệ số của P (x) đều chia hết cho p. Quay trở lại bài toán Xét đa thức P (x) = (x− 1)(x− 2) . . . (x− (p− 1))− (xp−1 + (p− 1)!). Đa thức P (x) có thể được viết lại như sau: P (x) = S1x p−2 + · · ·+ Sp−2x. Tập nghiệm của đa thức P (x) gồm p− 1 phần tử là tập hợp {1; 2; ...; p− 1} , mà degP = p− 2 cho nên Si ...p, ∀i = 1, p− 2. Mặt khác, ta có P (p) = −pp−1 ⇒ p3|P (p)⇒ p3|pSp−2, hay p2|Sp−2. Để ý rằng Cp−1 mpk−1 = (mpk − 1)(mpk − 2) . . . (mpk − (p− 1)) (p− 1)! , và gcd((p− 1)!, p) = 1. Nên bài toán quy về việc chứng minh pk+2|(Cp−1 mpk−1 − 1)(p− 1)!. Suy ra pk+2|(mpk − 1) . . . (mpk − (p− 1))− (p− 1)! 23 ⇔ pk+2|P (mpk) + (mpk)p−1 ⇔ pk+2|S1(mpk)p−2 + · · ·+ Sp−2mpk + (mpk)p−1. (1.64) Kết quả (1.64) hoàn toàn đúng do p2|Sp−2 và p|Si,∀i = 1, p− 3. 1.5.2 Quan hệ đồng dư giữa các biểu thức tổ hợp Bài toán 1.11 (Putnam 1996). Cho số nguyên tố p ≥ 5 và k = ⌊ 2p 3 ⌋ . Chứng minh rằng k∑ i=0 Cip ≡ 1 (mod p2). Lời giải. Ta có k∑ i=0 Cip ≡ 1 (mod p2)⇔ k∑ i=1 p i Ci−1p−1 ≡ 0 (mod p2), hay k∑ i=1 1 i Ci−1p−1 ≡ 0 (mod p)⇔ k∑ i=1 (−1)i−1 i ≡ 0 (mod p). Do p ≥ 5 là số nguyên tố nên p có dạng 6m± 1. • Xét p = 6m− 1, k = 4m− 1 ta có k∑ i=1 (−1)i−1 i = 4m−1∑ i=1 1 i − 2 2m−1∑ j=1 1 2j = 4m−1∑ i=1 1 i − 2m−1∑ i=1 1 j = 4m−1∑ i=2m 1 i . Lại có 2 4m−1∑ i=2m 1 i = 2m∑ i=1 ( 1 2m− 1 + i + 1 4m− i ) = 2m∑ i=1 6m− 1 (2m− 1 + i)(4m− i) = 2m∑ i=1 p (2m− 1 + i)(4m− i) ≡ 0 (mod p). Vì gcd(p, (2m− 1 + i)(4m− i)) = 1,∀i = 1, 2m nên 4m−1∑ i=2m 1 i ≡ 0 (mod p). 24 • Xét p = 6m+ 1, k = 4m ta có k∑ i=1 (−1)i−1 i = 4m∑ i=1 1 i − 2 2m∑ j=1 1 2j = 4m∑ i=1 1 i − 2m∑ j=1 1 j = 4m∑ i=2m+1 1 i . Lại có 2 4m∑ i=2m+1 1 i = 2m∑ i=1 ( 1 2m+ i + 1 4m+ 1− i ) = 2m∑ i=1 6m+ 1 (2m+ i)(4m+ 1− i) = 2m∑ i=1 p (2m+ i)(4m+ 1− i) ≡ 0 (mod p). Vì gcd(p, (2m+ i)(4m+ 1− i)) = 1,∀i = 1, 2m nên 4m∑ i=2m+1 1 i ≡ 0 (mod p). Bài toán 1.12 (Putnam 1991). Cho p là số nguyên tố lẻ. Chứng minh rằng p∑ j=0 CjpC j p+j ≡ 2p+1 (mod p2). Lời giải. Sử dụng đẳng thức Vandermonde ta có p∑ j=0 CjpC j p+j = ∑ j≥0 Cjp ∑ h≥0 Chj C p−h p = ∑ h≥0 Cp−hp p! h!(p− h)! ∑ j≥0 (p− h)! (p− j)!(j − h)! = ∑ h≥0 (Chp ) 2 2p−h ≡ 2p + 1 (mod p2). (Do số nguyên tố p là ước của Chp với 0 < h < p). Bài toán 1.13 (Thi chọn đội tuyển VMO 2012, tỉnh Nghệ An). Cho p > 3 là số nguyên tố và tập hợp M = {1; 2; . . . ; p}. Với mỗi số nguyên k thỏa mãn 1 ≤ k ≤ p ta đặt Ek = {A ⊂M : |A| = k}, và xk = ∑ A∈Ek (minA+ maxA). 25 Chứng minh rằng p−1∑ k=1 xkC k p ≡ 0 (mod p3). Lời giải. Giả sử A = {a1; a2; . . . ; ak} ∈ Ek. Khi ấy B = {p+ 1− a1; . . . ; p+ 1− ak} ∈ Ek. • Nếu a1 = minA thì p+ 1− a1 = maxB. • Nếu ak = maxA thì p+ 1− ak = minB. Bây giờ, ta có 2xk = ∑ A∈Ek (a1 + ak + p+ 1 + p+ 1− ak − a1) = ∑ A∈Ek 2(p+ 1) = 2(p+ 1)Ckp , hay xk = (p+ 1)C k p . Ta sẽ chứng minh (p+ 1) p−1∑ k=1 (Ckp ) 2 ≡ 0 (mod p3), hay p−1∑ k=1 (Ckp ) 2 ≡ 0 (mod p3). (1.65) Thật vậy, Ckp ...p⇒ 1 p Ckp = (p− 1)! k!(p− k)! . Do đó (1.65)⇔ p−1∑ k=1 ( (p− 1)! k!(p− k)! )2 ≡ 0 (mod p). Đặt αk = (p− 1)! k!(p− k)! ⇒ k!αk = (p− 1)(p− 2) . . . (p− k + 1) ≡ (−1)k−1(k − 1)! (mod p) ⇒ kαk ≡ (−1)k−1 (mod p). Lại đặt βk = (p− 1)! k ⇒ kβk = (p− 1)! ≡ −1 (mod p), ⇒ αk ≡ (−1)kβk (mod p). 26 Ta có mệnh đề sau: “∀k ∈ {1; 2; . . . ; p− 1}, ∃ duy nhất j ∈ {1; 2; . . . ; p− 1} sao cho jk ≡ 0 (mod p)”. Khi đó p−1∑ k=1 β2k ≡ p−1∑ k=1 β2k(kj) 2 ≡ p−1∑ k=1 (bkk) 2j2 ≡ p−1∑ j=1 j2 ≡ (p− 1)(2p− 1)p 6 (mod p). Mặt khác, do p > 3 nên (p− 1)...2 và (p− 1)(2p− 1) = 2p2 + 1− 3p ≡ 2.1 + 1 ≡ 0 (mod 3). Suy ra (p− 1)(2p− 1)...6. Cuối cùng ta đi đến p−1∑ k=1 α2k ≡ p−1∑ k=1 β2k ≡ 0 (mod p). Vậy ta hoàn tất việc chứng minh p−1∑ k=1 xkC k p ≡ 0 (mod p3). Bài toán 1.14 (VMO 2017). Chứng minh rằng a) 1008∑ k=1 kCk2017 ≡ 0 (mod 20172). b) 504∑ k=1 (−1)kCk2017 ≡ 3 ( 22016 − 1) (mod 20172). Lời giải. a) Ta có 1008∑ k=1 kCk2017 ≡ 1008∑ k=1 k.2017! k!(2017− k)! ≡ 2017 1008∑ k=1 2016! (k − 1)!(2017− k)! ≡ 2017 1007∑ k=0 2016! k!(2016− k)! ≡ 2017 1007∑ k=0 Ck2016 ≡ 2017 1007∑ k=0 Ck2016 27 ≡ 2017 2 ( 2016∑ k=0 Ck2016 − C10082016 ) ≡ 2017 2 (22016 − C10082016) (mod 20172). Do 2017 là số nguyên tố nên áp dụng định lí Fermat nhỏ ta có 22016 ≡ 1 (mod 2017). Mặt khác, ta có C10082016 − 1 = 1009.1010 . . . 2016− 1008! 1008! = (2017− 1)(2017− 2) . . . (2017− 1008)− 1008! 1008! . Tử số chia hết cho 2017 và gcd(1008!, 2017) = 1 nên C10082016 ≡ 1 ≡ 22016 (mod 2017). Do đó 1008∑ k=1 kCk2017 ≡ 0 (mod 20172). b) Ký hiệu x y ≡ z t (modm) với x, y, z, t ∈ Z, y 6= 0, t 6= 0 và m ∈ Z,m > 1 nếu dạng tối giản của phân số xt− zy yt chia hết cho m. Nhận xét 1.5. Với mọi số nguyên tố p thì Ckp ≡ (−1)k−1 p k (mod p2). Thật vậy, ta có Ckp = p! k!(p− k)! = p k . (p− k + 1)(p− k + 2) . . . (p− 1) (k − 1)! . Suy ra Ckp − (−1)k−1 p k = p k . (p− k + 1)(p− k + 2) . . . (p− 1)− (−1)k−1(k − 1)! (k − 1)! . Để ý rằng thừa số thứ nhì trong tích này chia hết cho p2 cho nên khẳng định trên được chứng minh. Đến đây, ta có 1 p Ckp ≡ (−1)k−1 k (mod p). 28 Khi đó 504∑ k=1 (−1)kCk2017 ≡ 504∑ k=1 (−1)k(−1)k−12017 k ≡ 504∑ k=1 (−1)2k−12017 k ≡ −2017 504∑ k=1 1 k (mod 20172). Bài toán quy về −2017 504∑ k=1 1 k ≡ 3(22016 − 1) (mod 20172), hay − 504∑ k=1 1 k ≡ 3(2 2016 − 1) 2017 (mod 2017). Đặt Sn = 1 1 + 1 2 + 1 3 + · · ·+ 1 n , n ∈ Z+. Khi đó 1 1 − 1 2 + · · · − 1 2n = S2n − Sn. Ta có S504 = S1008 − 1008∑ k=1 (−1)k−1 k = S2016 − 2016∑ k=1 (−1)k−1 k − 1008∑ k=1 (−1)k−1 k . Do S2016 = 1008∑ k=1 ( 1 k + 1 2017− k ) ≡ 0 (mod 2017). nên ta cần chứng minh 2016∑ k=1 (−1)k−1 k + 1008∑ k=1 (−1)k−1 k ≡ 3(2 2016 − 1) 2017 (mod 2017). Sử dụng nhận xét trên một lần nữa, ta đưa quan hệ đồng dư trên về 1 2017 ( 2016∑ k=1 Ck2017 + 1008∑ k=1 Ck2017 ) ≡ 3(2 2016 − 1) 2017 (mod 2017). 29 Điều này là hợp lý bởi vì 2016∑ k=1 Ck2017 + 1008∑ k=1 Ck2017 ≡ 2016∑ k=1 Ck2017 + 1 2 2016∑ k=1 Ck2017 ≡ 3 2 ( 2017∑ k=0 Ck2017 − 2 ) ≡ 3(2 2017 − 2) 2 ≡ 3(22016 − 1) (mod 2017). 30 Chương 2. Bất đẳng thức trong tính toán tổ hợp Trong chương này, tác giả nhắc lại một số bất đẳng thức cơ bản trong đại số. Tác giả sắp xếp và phân loại các bài toán chứng minh bất đẳng thức trong tính toán tổ hợp theo từng phương pháp là sử dụng phép biến đổi tương đương, phương pháp làm trội, làm giảm hay sử dụng các bất đẳng thức cơ bản trong đại số để chứng minh. Trong chương 2, tác giả sử dụng các tài liệu tham khảo [1], [2], [4] và [6]. 2.1 Các bất đẳng thức cơ bản trong đại số Định lý 2.1 (xem [1]). (Định lí về các giá trị trung bình cộng và nhân). Giả sử x1, x2, . . . , xn là các số không âm. Khi đó x1 + x2 + · · ·+ xn n ≥ n√x1x2 · · · xn. (2.1) Dấu đẳng thức xảy ra khi x1 = x2 = · · · = xn. Bất đẳng thức 2.1 còn gọi tắt là bất đẳng thức AM-GM. Hệ quả trực tiếp của bất đẳng thức AM-GM là bất đẳng thức giữa trung bình nhân và trung bình điều hòa (gọi tắt là bất đẳng thức GM-HM). Hệ quả 2.1 (Bất đẳng thức GM-HM). Với mọi bộ số dương a1, a2, · · ·, an, ta đều có n √ a1a2 · · · an ≥ n1 a1 + 1 a2 + · · ·+ 1 an . Chứng minh. Sử dụng bất đẳng thức AM-GM đối với bộ số xk = 1 ak với k = 1, 2, 3, . . . , n, ta có ngay bất đẳng thức GM-HM. Dấu đẳng thức xảy ra khi a1 = a2 = · · · = an. Chứng minh Định lí 2.1 (Quy nạp kiểu Cauchy) Từ hệ thức bậc hai u21 + u 2 2 ≥ 2u1u2, ∀u1, u2 ∈ R. (2.2) ta có 31 x1 + x2 2 ≥√x1x2, ∀x1, x2 ≥ 0. (2.3) Thay x1, x2 lần lượt bằng các biến mới x1 + x2 2 và x3 + x4 2 , từ (2.3) ta nhận được x1 + x2 + x3 + x4 4 ≥ √ x1 + x2 2 x3 + x4 2 ≥ √√ x1x2. √√ x3x4 = 4 √ x1x2x3x4. Bây giờ ta thực hiện quy trình quy nạp theo hướng xuống phía dưới. Ta chứng minh rằng khi bất đẳng thức (2.1) đúng với n, (n > 1) thì nó cũng đúng với xn−1. Thay xn trong (2.1) bởi x1+x2+···+xn−1 n−1 , và giữ nguyên các biến xi khác ta thu được x1 + x2 + · · ·+ xn−1 + x1+x2+···+xn−1n−1 n ≥ (x1x2 · · · xn) 1 n ( x1 + x2 + · · ·+ xn−1 n− 1 ) 1 n , hay x1 + x2 + · · ·+ xn−1 n− 1 ≥ (x1x2 · · · xn) 1 n−1 ( x1 + x2 + · · ·+ xn−1 n− 1 ) 1 n . Rút gọn biểu thức trên ta thu được x1 + x2 + · · ·+ xn−1 n− 1 ≥ n−1√x1x2 · · · xn−1. Từ các kết quả chứng minh theo cặp hướng (lên - xuống), ta thu được phép chứng minh quy nạp của định lí (2.1). Định lý 2.2 (xem [1]). (Bất đẳng thức AM - GM suy rộng). Giả sử cho trước hai dãy số dương x1, x2, . . . , xn; p1, p2, . . . , pn. Khi đó xp11 · xp21 · · · xpn1 ≥ ( x1p1 + x2p2 + · · ·+ xnpn p1 + p2 + · · ·+ pn )p1+p2+···+pn . Dấu đẳng thức xảy ra khi x1 = x2 = · · · = xn. Hệ quả 2.2. Giả sử cho trước hai cặp dãy số dương x1, x2, . . . , xn;α1, α2, . . . , αn; với xβ11 x β2 2 · · · xβnn = M. Khi đó n∑ k=1 αkxk ≥ (β1 + β2 + · · ·+ βn) [ M n∏ k=1 ( αk βk )βk] 1β1+β2+···+βn . Dấu đẳng thức xảy ra khi và chỉ xk = βkA αkB . 32 Định lý 2.3 (xem [1]). (Bất đẳng thức Cauchy-Schwarz). Giả sử a1, a2, · · ·, an và b1, b2, · · · , bn là các số thực bất kì, khi đó ta có (a1b1 + a2b2 + · · ·+ anbn)2 ≤ ( a21 + a 2 2 + · · ·+ a2n ) ( b21 + b 2 2 + · · ·+ b2n ) . (2.4) Đẳng thức xảy ra khi tồn tại một số k sao cho ai = kbi với mọi i = 1, 2, · · · , n. Hệ quả 2.3 (Bất đẳng thức Cauchy-Schwarz dạng Engel). Giả sử a1, a2, · · ·, an là các số thực bất kì và b1, b2, · · · , bn là các số thực dương, khi đó ta có a21 b1 + a22 b2 + · · ·+ a 2 n bn ≥ (a1 + a2 + · · ·+ an) 2 b1 + b2 + · · ·+ bn . (2.5) Đẳng thức xảy ra khi a1 b1 = a2 b2 = · · · = an bn . Định lý 2.4 (xem [1]). (Bất đẳng thức Chebyshev). Giả sử a1, a2, · · ·, an là các số thực sao cho a1 ≤ a2 ≤ · · · ≤ an, b1, b2, · · · , bn là các số thực. +) Nếu b1 ≤ b2 ≤ · · · ≤ bn thì ta có a1b1 + a2b2 + · · ·+ anbn ≥ 1 n (a1, a2, · · · , an) (b1, b2, · · · , bn) . (2.6) +) Nếu b1 ≥ b2 ≥ · · · ≥ bn thì ta có a1b1 + a2b2 + · · ·+ anbn ≤ 1 n (a1, a2, · · · , an) (b1, b2, · · · , bn) . (2.7) Tiếp theo, ta xét một số dạng đa thức đối xứng cơ bản Đa thức P (x1, x2, · · · , xn) với bộ n biến số thực x1, x2, ·, xn được hiểu là hàm số (biểu thức) có dạng P (x1, x2, · · · , xn) = N∑ k=0 Mk(x1, x2, · · · , xn), trong đó Mk(x1, x2, · · · , xn) = ∑ j1+j2+···+jn=k aj1,j2,··· ,jnx j1 1 · · ·xjnn , ji ∈ N(i = 1, 2, · · · , n.) (2.8) Trong mục này ta quan tâm chủ yếu đến các dạng đa thức đồng bậc biến số thực và nhận giá trị thực, đặc biệt là các đa thức đối xứng sơ cấp quen thuộc liên quan đến các hằng đẳng thức đáng nhớ trong chương trình toán trung học phổ thông. Trước hết, ta nhắc lại công thức khai triển nhị thức Newton: (x+ a)n = n∑ k=0 Ckna n−kxk. 33 Nếu ta coi (x+ a)n như là tích của n thừa số (x+ a)(x+ a) · · · (x+ a), thì khi đó (x+ a1)(x+ a2) · · · (x+ an) cũng có thể viết dưới dạng một biểu thức tương tự như công thức khai triển nhị thức Newton sau (x+ a1)(x+ a2) · · · (x+ an) = n∑ k=0 Cknp n−k j x k, trong đó  p1 = a1 + a2 + · · ·+ an n p22 = ∑ 1≤i<j≤n aiaj C2n . . . . . . . . . . . . . . . . . . pnn = a1a2 · · · an. (2.9) Vậy nên, nếu các số a1, a2, · · · , an đều dương (hoặc không âm) và không đồng thời bằng 0 thì không mất tính tổng quát, ta có thể coi các số p1, p2, · · · , pn đều dương (hoặc không âm). Từ (2.9), ta thu được  p1 = a1 + a2 + · · ·+ an n p2 = √√√√ ∑1≤i<j≤n aiaj C2n . . . . . . . . . . . . . . . . . . pn = n √ a1a2 · · · an. (2.10) Định nghĩa 2.1 (xem [1]). (Bất đẳng thức Newton). Cho a¯ là bộ n số dương {a1, a2, . . . , an} , (n ≥ 1, n ∈ N). Khi đó f(x) = (x+ a1)(x+ a2) · · · · · · · (x+ an) = xn + E1(a¯)x n−1 + E2(a¯)xn−2 + · · ·+ En(a¯), trong đó E1(a¯) = n∑ i=1 ai, E2(a¯) = ∑ 1≤i<j≤n aiaj, . . . , E1(a¯) = a1a2 . . . an. Đặt E0(a¯) = 1. Ta gọi Er(a¯) = 1 là các hàm (đa thức) đối xứng sơ cấp thứ r(Er(a¯) là tổng của tất cả các tích r số khác nhau của bộ số (a¯).) Ký hiệu Pr(a¯) = r!(n− r)! n! Er(a¯). 34 Định nghĩa 2.2 (xem [1]). Giả sử x1, x2, . . . , xn là các bộ n số thực không âm (ký hiệu bởi (x¯)) và y1, y2, . . . , yn là bộ các số thực không âm khác nhau (được kí hiệu bởi (y¯)) Hai dãy (x¯) và (y¯) được gọi là đồng dạng (và ký hiệu x¯ y¯) nếu tồn tại λ ∈ R(λ 6= 0) sao cho ta có xj = λyj(j = 1, 2, . . . , n). Bài toán 2.1. Cho a¯ là bộ (a1, a2, . . . , an) các số thực dương. Đặt P0 = 1, Pk = Pk(a¯), Er = Er(a¯). Chứng minh rằng Pk−1Pk+1 ≤ P 2k (k = 1, 2, . . . , n− 1) . (Nếu các ai đều dương và không đồng thời bằng nhau thì ta có dấu bất đẳng thức thực sự). Chứng minh. Giả sử f(x, y) = (x+ a1y)(x+ a2y) · · · (x+ any) = E0xn +E1xn−1y+ · · ·+Enyn Ei là tổng tất cả các tích i số khác nhau, Pr(a¯) = r!(n− r)! n! Er(a¯) Vì tất cả các số ai đều dương và t := x y = 0 và v := y x = 0 không phải là nghiệm của phươnng trình f(t, 1) = 0 và f(v, 1) = 0, tương ứng, nên x y = 0 và y x = 0 không phải là nghiệm bội trong các phương trình nhận từ đạo hàm của nó. Từ đó ta có thể kết luận rằng các số Pi dương, tức là phương trình Pk−1x2 + 2Pkxy + Pk+1y2 = 0. nhận được từ f(x, y) = 0 bằng cách lấy vi phân liên tiếp theo x và y. Do đó phương trình này có nghiệm thực nên Pk−1Pk + 1 ≤ P 2k . Bài toán 2.2. Cho các số ai > 0 (i ∈ {1, 2, 3, . . . , n}) và không đồng thời bằng nhau. Chứng minh bất đẳng thức P1 > P 1 2 2 P 1 3 3 > · · · > P 1 3 n . (2.11) Chứng minh. Ta có P0P2 < P 2 1 , (P1P3) 2 < P, . . . . . . . . . . . . ., (Pr−1Pr+1)r < P 2rr . Suy ra (P0P2)(P1P3) 2 · · · (Pr−1Pr+1)r < P 21P 42P 2rr , hay P rr+1 < Pr r+1 ⇒ Pr 1r>P 1 r+1 r+1 . 35 Nhận xét 2.1. Ta dễ dàng chứng minh được Pr−1Pr+1 < P 2r bằng phương pháp quy nạp Thật vậy, giả sử bất đẳng thức đúng với n− 1 số dương a1, a2, . . . , an−1 và E ′r, P ′r là các Er, Pr tạo bởi n− 1 số ấy và giả sử tất cả các số đấy không đồng thời bằng nhau. Khi đó E ′r = anE ′ r−1 ⇒ Pr = r n P ′r + r n anP ′ r−1. Từ đó suy ra n2(Pr−1Pr+1 − P 2r ) = A+Ban + Ca2n. trong đó A = [ (n− r)2 − 1]P ′r−1P ′r+1 − (n− r)2P ′r−1. B = (n− r + 1)(r + 1).P ′r−1P ′r+1 + (n− r − 1)(r − 1)P ′r−2P ′r+1 − 2(r − 1)P ′r−2P ′r+1. C = (r2 − 1)P ′r−2P ′r − r2P ′r−1. Vì các ai không đồng thời bằng nhau nên theo giả thiết ta có P ′r−1P ′ r+1 < P ′ r−2P ′ r − P ′r. P ′r−2P ′ r+1 < P ′ r−1P ′ r ⇒ A < −P ′r, B < 2P ′r−1P ′r, C < P ′r−1. n2(Pr−1Pr − P ′r) < −(P ′r − anP ′r−1) ≤ 0. Điều này vẫn đúng khi a1 = a2 = · · · = an. Khi đó an 6= a1. Từ bất đẳng thức (2.11), ta thu được bất đẳng thức sau p1 ≥ p2 ≥ · · · ≥ pn, trong đó  p1 = a1 + a2 + · · ·+ an n p2 = √√√√ ∑1≤i<j≤n aiaj C2n . . . . . . . . . . . . . . . . . . pn = n √ a1a2 · · · an. Đặc biệt, p1 ≥ pn. Đó chính là bất đẳng thức giữa trung bình cộng và trung bình nhân. 36 2.2 Một số bài toán về bất đẳng thức trong tính toán tổ hợp 2.2.1 Phép biến đổi tương đương, phương pháp làm trội, làm giảm Bài toán 2.3. Chứng minh rằng nếu n và k là hai số tự nhiên thỏa mãn 0 ≤ k ≤ n thì Cn2n+k.C n 2n−k ≤ (Cn2n)2 . Nhận xét 2.2. Để chứng minh bất đẳng thức này ta sử dụng phép biến đổi tương đương. Chứng minh. Đặt uk = C n 2n+k.C n 2n−k với 0 ≤ k ≤ n, n, k ∈ N. Ta chứng minh dãy (uk) giảm. Ta có uk = C n 2n+k.C n 2n−k = (2n+ k)! n!(n+ k)! . (2n− k)! n!(n− k)! , uk+1 = C n 2n+k+1.C n 2n−k = (2n+ k + 1)! n!(n+ k + 1)! . (2n− k − 1)! n!(n− k − 1)! . Do đó uk+1 uk = (2n+ k + 1)(n− k) (n+ k + 1)(2n− k) ≤ 1 . Thật vậy uk+1 uk ≤ 1⇔ (2n+ k + 1)(n− k) ≤ (n+ k + 1)(2n− k) ⇔ 2nk + n ≥ 0 (hiển nhiên đúng) vì 0 ≤ k ≤ n. Do đó dãy (uk) giảm. Từ đó suy ra với k ≥ 0 thì uk ≤ u0 ⇔ Cn2n+k.Cn2n−k ≤ (Cn2n)2 . Bài toán 2.4. Chứng minh rằng C2n + 2C 3 n + · · ·+ (n− 1)Cnn > (n− 2)2n−1. Nhận xét 2.3. Để chứng minh bất đẳng thức này ta phải tính tổng ở vế trái để làm gọn bất đẳng thức cần chứng minh. Chứng minh. Ta có (1 + x)n = n∑ k=0 Ckn.x k. (2.12) Đạo hàm hai vế của đẳng thức (2.12), ta có n(1 + x)n−1 = n∑ k=1 Ckn.kx k−1. (2.13) 37 Thay x = 2 vào bất đẳng thức (2.13), ta được n2n−1 = n∑ k=1 kCkn. (2.14) Thay x = 1 vào (2.12) 2n = n∑ k=0 Ckn. (2.15) Trừ từng vế (2.14) cho (2.15), ta có n2n−1 − 2n = −C0n + C2n + 2C3n + · · ·+ (n− 1)Cnn ⇔ C2n + 2C3n + · · ·+ (n− 1)Cnn = n2n−1 − 2n + 1 = (n− 2)2n−1 + 17(n− 2)2n−1. Vậy C2n + 2C 3 n + · · ·+ (n− 1)Cnn > (n− 2)2n−1. Bài toán 2.5. Chứng minh rằng C1n + 2C 2 n + 3C 3 n + · · ·+ nCnn n 3. Nhận xét 2.4. Để chứng minh bất đẳng thức này ta phải tính tổng ở tử của vế trái