intTypePromotion=1
ADSENSE
 » 
 » 

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

Chia sẻ: AtaruMoroboshi _AtaruMoroboshi | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST
Báo xấu
15
lượt xem 1
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. Hội thảo khoa học, Ninh Bình 15-16/09/2018 BẤ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ượng nghiê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ời rạ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ũng thườ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 cho ta 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 ứ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 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ức tổ 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ợp vớ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ợp Bà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 −1 một ước của n ∑ (−1)k Cnk . k =0 114
  2. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Lờ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 −1 Vậy m|n ∑ (−1)k Cnk . k =0 Bài toán 2 (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 + 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 = . 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 . +) 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 3 (Gặp gỡ Toán học 2014). Cho p ≥ 5 là số nguyên tố và m, k ∈ Z+ . Chứng p −1 minh 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ậ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. 115
  3. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Bổ đề 1. 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)) − ( x p−1 + ( p − 1)!). Đa thức P( x ) có thể được viết lại như sau: P( x ) = S1 x p−2 + · · · + S p−2 x. 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à deg P = . p − 2 cho nên S ..p, ∀i = 1, p − 2. Mặt khác, ta có i P( p) = − p p−1 ⇒ p3 | P( p) ⇒ p3 | pS p−2 , hay p2 |S p−2 . Để ý rằng p −1 (mpk − 1)(mpk − 2) . . . (mpk − ( p − 1)) Cmpk −1 = , ( p − 1) ! và gcd(( p − 1)!, p) = 1. Nên bài toán quy về việc chứng minh p −1 pk+2 |(Cmpk −1 − 1)( p − 1)!. Suy ra pk+2 |(mpk − 1) . . . (mpk − ( p − 1)) − ( p − 1)! p −1 ⇔ pk+2 | P(mpk ) + (mpk ) p −2 p −1 ⇔ pk+2 |S1 (mpk ) + · · · + S p−2 mpk + (mpk ) . (1.1) Kết quả (1.1) hoàn toàn đúng do p2 |S p−2 và p|Si , ∀i = 1, p − 3. 1.2 Quan hệ đồng dư giữa các biểu thức tổ hợp   2p Bài toán 4 (Putnam 1996). Cho số nguyên tố p ≥ 5 và k = . Chứng minh rằng 3 k ∑ Cip ≡ 1 (mod p2 ). i =0 Lời giải. Ta có k k p i −1 ∑ Cip ≡ 1 (mod p2 ) ⇔ ∑ C i p −1 ≡0 (mod p2 ), i =0 i =1 hay k 1 k (−1)i−1 ∑ i Cip−−11 ≡ 0 (mod p) ⇔ ∑ i ≡ 0 (mod p). i =1 i =1 116
  4. Hội thảo khoa học, Ninh Bình 15-16/09/2018 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 (−1)i−1 4m−1 1 2m−1 1 ∑ i = ∑ i − 2 ∑ 2j i =1 i =1 j =1 4m−1 1 2m−1 1 = ∑ i − ∑ j i =1 i =1 4m−1 1 = ∑ i . i =2m Lại có 4m−1 2m   1 1 1 2 ∑ i =∑ + 2m − 1 + i 4m − i i =2m i =1 2m 6m − 1 = ∑ (2m − 1 + i)(4m − i) i =1 2m p = ∑ (2m − 1 + i)(4m − i) ≡ 0 (mod p). i =1 Vì gcd( p, (2m − 1 + i )(4m − i )) = 1, ∀i = 1, 2m nên 4m−1 1 ∑ i ≡0 (mod p). i =2m • Xét p = 6m + 1, k = 4m ta có k (−1)i−1 4m 1 2m 1 4m 1 2m 1 4m 1 ∑ i = ∑i − 2 ∑ 2j ∑ i ∑ j = − = ∑ i. i =1 i =1 j =1 i =1 j =1 i =2m+1 Lại có 4m 2m   1 1 1 2 ∑ =∑ + i =2m+1 i i =1 2m + i 4m + 1 − i 2m 6m + 1 = ∑ (2m + i)(4m + 1 − i) i =1 2m p = ∑ (2m + i)(4m + 1 − i) ≡ 0 (mod p). i =1 Vì gcd( p, (2m + i )(4m + 1 − i )) = 1, ∀i = 1, 2m nên 4m 1 ∑ i ≡0 (mod p). i =2m+1 p j j Bài toán 5 (Putnam 1991). Cho p là số nguyên tố lẻ. Chứng minh rằng ∑ C p C p+ j ≡ 2 p + 1 j =0 (mod p2 ). 117
  5. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Lời giải. Sử dụng đẳng thức Vandermonde ta có p ∑ Cp Cp+ j = ∑ Cp ∑ Cjh Cp j j j p−h j =0 j ≥0 h ≥0 p! ( p − h)! ∑ Cp ∑ ( p − j)!( j − h)! p−h = h ≥0 h!( p − h)! j ≥0 2 = ∑ (C hp ) 2 p−h h ≥0 p ≡ 2 + 1 (mod p2 ). (Do số nguyên tố p là ước của C hp với 0 < h < p). Bài toán 6 (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 = ∑ (min A + max A). A∈ Ek p −1 Chứng minh rằng ∑ xk C kp ≡ 0 (mod p3 ). k =1 Lời giải. Giả sử A = {a1 ; a2 ; . . . ; ak} ∈ Ek . Khi ấy B = {p + 1 − a1 ; . . . ; p + 1 − ak} ∈ Ek . • Nếu a1 = min A thì p + 1 − a1 = max B. • Nếu ak = max A thì p + 1 − ak = min B. Bây giờ, ta có 2xk = ∑ ( a1 + a k + p + 1 + p + 1 − a k − a1 ) = ∑ 2( p + 1) = 2( p + 1)C kp , A∈ Ek A∈ Ek hay xk = ( p + 1)C kp . Ta sẽ chứng minh p −1 2 ( p + 1) ∑ (Ckp ) ≡ 0 (mod p3 ), k =1 hay p −1 2 ∑ (Ckp ) ≡ 0 (mod p3 ). (1.2) k =1 Thật vậy, . 1 ( p − 1) ! C kp ..p ⇒ C kp = . p k!( p − k)! Do đó p −1  2 ( p − 1) ! (1.2) ⇔ ∑ k!( p − k )! ≡ 0 (mod p). k =1 118
  6. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Đặt ( p − 1) ! αk = 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 ( p − 1) ! βk = k ⇒ kβ k = ( p − 1)! ≡ −1 (mod p), ⇒ αk ≡ (−1)k β k (mod p). 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 p −1 p −1 p −1 ( p − 1)(2p − 1) p ∑ ∑ β2k (kj)2 ∑ ( bk k ) ∑ j2 ≡ 2 2 β2k ≡ ≡ j ≡ (mod p). k =1 k =1 k =1 j =1 6 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 p −1 ∑ α2k ≡ ∑ β2k ≡ 0 (mod p). k =1 k =1 Vậy ta hoàn tất việc chứng minh p −1 ∑ xk Ckp ≡ 0 (mod p3 ). k =1 Bài toán 7 (VMO 2017). Chứng minh rằng 1008 a) ∑ kC2017 k ≡0 (mod 20172 ). k =1 504   b) ∑ (−1)k C2017 k ≡3 22016 − 1 (mod 20172 ). k =1 119
  7. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Lời giải. a) Ta có 1008 1008 k.2017! ∑ k kC2017 ≡ ∑ k!(2017 − k )! k =1 k =1 1008 2016! ≡ 2017 ∑ (k − 1)!(2017 − k)! k =1 1007 2016! ≡ 2017 ∑ k!(2016 − k )! k =0 1007 ≡ 2017 ∑ C2016 k k =0 1007 ≡ 2017 ∑ C2016 k k =0 ! 2016 2017 ≡ 2 ∑ k C2016 1008 − C2016 k =0 2017 2016 1008 ≡ (2 − C2016 ) (mod 20172 ). 2 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ó 1008 1009.1010 . . . 2016 − 1008! C2016 −1 = 1008! (2017 − 1)(2017 − 2) . . . (2017 − 1008) − 1008! = . 1008! Tử số chia hết cho 2017 và gcd(1008!, 2017) = 1 nên 1008 C2016 ≡ 1 ≡ 22016 (mod 2017). Do đó 1008 ∑ kC2017 k ≡0 (mod 20172 ). k =1 x z b) Ký hiệu ≡ ( 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 y t xt − zy giản của phân số chia hết cho m. yt Nhận xét 1. Với mọi số nguyên tố p thì k −1 p C kp ≡ (−1) (mod p2 ). k Thật vậy, ta có p! p ( p − k + 1)( p − k + 2) . . . ( p − 1) C kp = = . . k!( p − k )! k ( k − 1) ! 120
  8. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Suy ra p p ( p − k + 1)( p − k + 2) . . . ( p − 1) − (−1)k−1 (k − 1)! C kp − (−1)k−1 = . . k k ( 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 k (−1)k−1 Cp ≡ (mod p). p k Khi đó 504 504 k −1 2017 ∑ (−1) C2017 ∑ (−1) (−1) k k k ≡ k =1 k =1 k 504 2k−1 2017 ≡ ∑ (−1) k k =1 504 1 ≡ −2017 ∑ (mod 20172 ). k =1 k Bài toán quy về 504 1 −2017 ∑ ≡ 3(22016 − 1) (mod 20172 ), k =1 k hay 504 1 3(22016 − 1) −∑ ≡ (mod 2017). k =1 k 2017 Đặt 1 1 1 1 Sn = + + + · · · + , n ∈ Z+ . 1 2 3 n Khi đó 1 1 1 − +···− = S2n − Sn . 1 2 2n Ta có 1008 (−1)k−1 S504 = S1008 − ∑ k k =1 2016 (−1)k−1 1008 (−1)k−1 = S2016 − ∑ k −∑ k . k =1 k =1 Do 1008   1 1 S2016 = ∑ + k 2017 − k ≡ 0 (mod 2017). k =1 121
  9. Hội thảo khoa học, Ninh Bình 15-16/09/2018 nên ta cần chứng minh 2016 (−1)k−1 1008 (−1)k−1 3(22016 − 1) ∑ k +∑ k ≡ 2017 (mod 2017). k =1 k =1 Sử dụng nhận xét trên một lần nữa, ta đưa quan hệ đồng dư trên về ! 2016 1008 1 3(22016 − 1) 2017 k=1 ∑ C2017 + ∑ C2017 ≡ k k 2017 (mod 2017). k =1 Điều này là hợp lý bởi vì 2016 1008 2016 1 2016 ∑ C2017 k + ∑ C2017 k ≡ ∑ C2017 k + ∑ C2017 2 k k =1 k =1 k =1 k =1 ! 2017 3 ≡ 2 ∑ C2017 k −2 k =0 3(22017 − 2) ≡ ≡ 3(22016 − 1) (mod 2017). 2 2 Bất đẳng thức trong tính toán tổ hợp 2.1 Một số bài toán về bất đẳng thức trong tính toán tổ hợp Xét các phép biến đổi tương đương, phương pháp làm trội, làm giảm. Bài toán 8. Chứng minh rằng nếu n và k là hai số tự nhiên thỏa mãn 0 ≤ k ≤ n thì n n n 2 C2n +k .C2n−k ≤ (C2n ) . Nhận xét 2. Để chứng minh bất đẳng thức này ta sử dụng phép biến đổi tương đương. +k .C2n−k với 0 ≤ k ≤ n, n, k ∈ N. Chứng minh. Đặt uk = C2nn n Ta chứng minh dãy (uk ) giảm. Ta có n n (2n + k)! (2n − k)! uk = C2n +k .C2n−k = . , n!(n + k )! n!(n − k )! n n (2n + k + 1)! (2n − k − 1)! u k +1 = C2n +k+1 .C2n−k = . . n!(n + k + 1)! n!(n − k − 1)! Do đó u k +1 (2n + k + 1)(n − k) = . uk (n + k + 1)(2n − k) ≤ 1 Thật vậy u k +1 ≤ 1 ⇔ (2n + k + 1)(n − k) ≤ (n + k + 1)(2n − k) uk ⇔ 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ì n n n 2 uk ≤ u0 ⇔ C2n +k .C2n−k ≤ (C2n ) . 122
  10. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Bài toán 9. Chứng minh rằng Cn2 + 2Cn3 + · · · + (n − 1)Cnn > (n − 2)2n−1 . Nhận xét 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ó n (1 + x ) n = ∑ Cnk .xk . (2.1) k =0 Đạo hàm hai vế của đẳng thức (2.1), ta có n n (1 + x ) n −1 = ∑ Cnk .kxk−1 . (2.2) k =1 Thay x = 2 vào bất đẳng thức (2.2), ta được n n2n−1 = ∑ kCnk . (2.3) k =1 Thay x = 1 vào (2.1) n 2n = ∑ Cnk . (2.4) k =0 Trừ từng vế (2.3) cho (2.4), ta có n2n−1 − 2n = −Cn0 + Cn2 + 2Cn3 + · · · + (n − 1)Cnn ⇔ Cn2 + 2Cn3 + · · · + (n − 1)Cnn = n2n−1 − 2n + 1 = (n − 2)2n−1 + 17(n − 2)2n−1 . Vậy Cn2 + 2Cn3 + · · · + (n − 1)Cnn > (n − 2)2n−1 . Bài toán 10. Chứng minh rằng Cn1 + 2Cn2 + 3Cn3 + · · · + nCnn < n!, với n ∈ N, n > 3. n Nhận xét 4. Để chứng minh bất đẳng thức này ta phải tính tổng ở tử của vế trái để làm gọn bất đẳng thức cần chứng minh, rồi sử dụng phương pháp qui nạp toán học để chứng minh. Chứng minh. Ta có Cn1 + 2Cn2 + 3Cn3 + · · · + nCnn = n2n−1 . Suy ra Cn1 + 2Cn2 + 3Cn3 + · · · + nCnn = 2n −1 . n Vậy ta phải chứng minh 2n−1 < n!. (2.5) Thật vậy, ta đi chứng minh (2.5) bằng phương pháp quy nạp. Khi n = 3, ta có 2n−1 = 22 = 4 < 3!. Vậy (2.5) đúng. Giả sử (2.5)đúng với n = k, k ∈ N, k > 3, nghĩa là, ta có 2k−1 < k!. 123
  11. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Ta chứng minh (2.5) đúng khi n = k + 1, tức là phải chứng minh 2k < (k + 1)!. (2.6) Ta có (2.5)⇔ 2k < 2k!. Vì 2 < 3 ≤< k + 1 nên ta có 2k! < (k + 1)k! = (k + 1)! ⇒ 2k < (k + 1)!. Vậy (2.6) đúng. Theo nguyên lý qui nạp ta có 2n < n!, ∀n ∈ N, n ≥ 3. Suy ra điều phải chứng minh. Bài toán 11. Chứng minh rằng  n 1 2< 1+ < 3, n ∈ Z, n > 1. n Nhận xét 5. Để chứng minh bất đẳng thức này, ta sử dụng công thức khai triển nhị thức Newton ở vế trái, rồi sử dụng phương pháp làm trội, làm giảm để chứng minh. Chứng minh. Theo công thức nhị thức Newton, ta có  n  2  n 1 1 1 1 1+ = Cn0 + Cn1 + Cn2 + · · · + Cnn . n n n n 1 1 Ta có Cn0 = 1; Cn1 = n. = 1. Do đó n n  n 1 1+ > 2. (2.7) n Mặt khác, ta có  2 1 n ( n − 1) 1 1 1 Cn2 = < = = , n 2!n2 2! 2 1.2  3 3 1 n(n − 1)(n − 2) 1 1 Cn = < < , n 3!n3 3! 2.3 . . . . . . . . . . . . .,  p p 1 n ( n − 1) . . . ( n − p + 1) 1 1 Cn = p < < , n p!n p! ( p − 1).p . . . . . . . . . . . . .,  p n 1 n! 1 1 Cn = n < < . n n!n n! (n − 1).n Do đó, ta có  n 1 1 1 1 1+ < 2+ + +···+ . (2.8) n 1.2 2.3 (n − 1).n 124
  12. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Nhưng 1 1 1 = − , 1.2 1 2 1 1 1 = − , 2.3 2 3 . . . . . . . . . . . . . . . ., 1 1 1 = − . (n − 1).n n−1 n Suy ra 1 1 1 1 + +···+ = 1 − < 1. (2.9) 1.2 2.3 (n − 1).n n Từ (2.8) và (2.9), suy ra  n 1 1+ < 3. (2.10) n Kết hợp (2.7) và (2.10), ta có điều phải chứng minh. 2.2 Sử dụng các bất đẳng thức cơ bản để chứng minh Bài toán 12. Cho n + 1 số nguyên đôi một khác nhau x0 , x1 , . . . xn . Xét các đa thức dạng P ( x ) = x n + a n −1 x n −1 + · · · + a 1 x + a 0 . (2.11) Chứng minh rằng
  13. f ( x j )
  14. ≥ n! .
  16. max (2.12) j∈{0,1,...,n} 2n Chứng minh. Không mất tính tổng quát ta có thể coi x0 < x1 < · · · < xn thì xn − x0 ≥ n, . . . , xn − xn−1 ≥ 1. Khi đó theo công thức nội suy Lagrange thì có thể viết (2.11) dưới dạng " # n n x − xj P( x ) = ∑ P( xk ) ∏ . k =0 x − xj j6=i;j=0 i So sánh hệ số của x n ta được " # n n 1 1= ∑ P( xk ) ∏ xi − x j . k =0 j6=i;j=0 Nếu (2.12) không đúng thì " # n n 1 1= ∑ | P( xk )| ∏ xi − x j k =0 j6=i;j=0   n! 1 1 1 1 ≤ n + +···+ +···+ 2 n! (n − 1)!1! (n − k)!k! 0!n! 1  0  1 = n Cn + Cn1 + · · · + Cnk + · · · + Cnn = n 2n = 1, (mâu thuẫn). 2 2 Vậy ta có điều phải chứng minh. 125
  17. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Nhận xét 6. Để giải bài toán trên, ta đã sử dụng công thức nội suy Lagrange và công thức tính tổng của các số tổ hợp. Bài toán 13. Cho x1 , x2 , . . . , xn > 0 và đặt: n n n S1 = ∑ x i ; S2 = ∑ x i x j ; S3 = ∑ xi x j x k ; . . . , i =1 1≤ i ≤ j ≤ n 1≤ i < j < k ≤ n và Sn = x1 x2 . . . xn là các hàm cơ bản của x1 , x2 , . . . , xn . Chứng minh rằng: s s s S1 S2 S 3 Sn 1 ≥ 2 ≥ 3 3 ≥ ... ≥ n n. (2.13) Cn Cn Cn Cn Nhận xét 7. Để chứng minh bất đẳng thức (2.13), ta sử dụng phương pháp quy nạp kết hợp với bất đẳng thức AM-GM. Chứng minh. Ta chứng minh bằng quy nạp: Với n = 1, bất đẳng thức (2.13) đúng. Giả sử bất đẳng thức (2.13) đúng với n − 1. Ta giả thiết 0 < x1 < x2 < · · · < xn . Xét đa thức P( x ) = ( x − x1 )( x − x2 ) . . . ( x − xn ) = x n − S1 x n−1 + S2 x n−2 + . . . , (−1)n .Sn . Vì P( x ) có nghiệm x1 , x2 , . . . , xn nên theo định lí Lagrăng thì: P0 ( x ) = n.x n−1 − (n − 1).S1 x n−2 + (n − 2).S2 x n−3 − (n − 3).S3 x n−4 + . . . + (−1)n−1 .Sn−1 có n − 1 nghiệm y1 , y2 , . . . , yn−1 . Xen kẽ: x1 < y1 < x2 < y2 < . . . < xn−1 < yn−1 < xn . Suy ra n−1 n−2 n−3 S n −1 S1 ; S2 ; S3 ; . . . ; là các hàm cơ bản của y1 , y2 , . . . , yn−1 . n n n n Theo giả thiết quy nạp, ta có: s s s s ( n − 1) ( n − 2) S n −1 S S S ≥ . . . ≥ n−1 nn−1 . 2 1 S1 ≥ 2 S2 ≥ . . . ≥ n − 1 n − 1 ⇒ 11 ≥ 2 nCn−1 nCn−2 nCn−1 Cn Cn Cn−1 Ta lại có 1 1 1 x1 + x2 +···+ xn 1 ≥ √ AM-GM) n n x1 x2 . . . x n Suy ra 1 1 1 ! x1 + x2 +···+ xn ( x1 .x2 . . . xn ) n q ≥ n ( x 1 x 2 . . . x n ) n −1 . n Do đó: s s n −1 S n −1 n Sn ≥ ⇒ đpcm. Cnn−1 Cnn 126
  18. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Đây là bất đẳng thức xen kẽ của Cauchy. Chẳng hạn với a, b, c, d > 0 : r a+b+c+d ab + ac + ad + bc + bd + cd ≥ 4 6 + bcd √ r 3 abc + abd + acd 4 ≥ ≥ abcd. 4 3 Các dạng toán cực trị liên quan đến tổ hợp trong dãy số 3.1 Một số bài toán cực trị liên quan đến tổ hợp trong dãy số Bài toán 14. Cho đa thức P( x ) = (1 + 2x )n = a0 + a1 x + a2 x2 + · · · + an x n , a1 a2 an biết a0 + + 2 + · · · + n = 4096. 2 2 2 Xét dãy số ( ak ), k = 0, 1, 2, . . . , n. Tìm số hạng lớn nhất của dãy số ( ak ). Nhận xét 8. Để giải bài toán này trước hết ta phải tìm ra n, rồi tìm số hạng tổng quát của dãy số ak . Lời giải. Ta có   1 a a2 an f = a0 + 1 + 2 + · · · + n 2 2 2 2 ⇔ 2n = 4096 ⇔ 2n = 212 ⇔ n = 12. Khi đó, ta có 12 12 P( x ) = ∑ Cnk (2x)k = ∑ C12k xk . k =0 k =0 Suy ra k k ak = C12 2 , k = 0, 1, 2, . . . , n. Số hạng ak lớn nhất khi và chỉ khi ( a k ≥ a k +1 a k ≥ a k −1 12!  12! 2k ≥ 2k +1 ( k 2k k +1 k +1  C12 ≥ C12 2 k!(12 − k )!  ( k + 1)!(11 − k )! ⇔ k 2k ⇔ k −1 k −1 12! 12! C12 ≥ C12 2   2k ≥ 2k −1 k!(12 − k )! (k − 1)!(13 − k)! 1 2     ≥ k ≥ 22  ⇔ 212 − k 1 k + 1 ⇔ 3 26  ≥  k ≤  . k 13 − k 3 Vì k ∈ Z nên k = 8. Vậy a8 = 28 C12 8 = 126720 là số hạng lớn nhất của dãy ( a ) k 127
  19. Hội thảo khoa học, Ninh Bình 15-16/09/2018 Bài toán 15. Cho số nguyên dương N. Tìm giá trị lớn nhất trong dãy số CN n (n = 0, 1, . . . , N ).   n N −n n N Lời giải. Do CN = CN nên ta chỉ cần xét dãy {CN } với n = 0, 1, . . . , . Mặt khác    2 N n −1 n , nên max {C n } = C p , p = N . thì với n = 0, 1, . . . , , ta có CN < CN N N 2 0≤ n ≤ N 2 Bài toán 16 (Olympic 30/4/2009). Với mỗi bộ n số nguyên dương a1 , a2 , . . . , an có tổng bằng 2009. Đặt A là tổng tất cả các số hạng có dạng 1 , a1 ( a1 + a2 )( a1 + a2 + a3 ) . . . ( a1 + a2 + · · · + an ) trong đó k1 , k2 , . . . , k n là một hoán vị bất kì của {1, 2, . . . , n} . Tìm giá trị nhỏ nhất của A. Lời giải. Xét một bộ bất kì n số nguyên dương a1 , a2 , . . . , an có tổng bằng 2009 Ta chứng minh bằng quy nạp 1 A= . (3.1) a1 a2 . . . a n +) Với n = 1, (3.1) đúng +) Giả sử (3.1) đúng đến n − 1 Với mỗi n số nguyên dương a1 , a2 , . . . , an 1 Trong A, đặt làm thừa số chung, ta được a1 + a2 + · · · + a n 1 A= , a1 + a2 + · · · + a n trong đó B gồm n! số hạng. Trong B ta nhóm các số hạng không chứa a1 thành tổng B1 gồm (n − 1)! số hạng ứng với (n − 1)! hoán vị của {2, 3 . . . , n} 1 Do đó theo giả thiết quy nạp thì B = . a2 a3 . . . a n Tiếp tục như thế với a2 , a3 , . . . , an ta được 1 1 1 a + a2 · · · + a n B= + +···+ = 1 . a2 a3 . . . a n a1 a3 . . . a n a 1 a 2 . . . a n −1 a1 a2 . . . a n 1 Từ đó suy ra A = . a1 a2 . . . a n Vậy theo nguyên lí quy nạp (3.1) đúng với mọi n ≥ 1. +) Nếu a1 = 1, loại a1 = 1, thế a2 = 1 bởi a20 = 1 + a2 thì tổng các số ai không đổi, còn tích tăng lên. +) Nếu ai ≥ 5 thế a1 bởi 2( a1 − 2) thì tổng các số ai không đổi, tích tăng lên vì 2( a1 − 2) = 2a1 − 4 > a1 . +) Nếu có một số ai = 4, thế số đó bởi 2 + 2 thì tổng và tích các số ai không đổi. +) Nếu có ba số 2, thế ba số đó bằng hai số 3 thì tổng không đổi, tích tăng lên. Vậy để tích p của các số ai lớn nhất thì phải chọn không quá hai số 2, các số khác bằng 3 1 Do 2009 = 3.669 + 2 nên maxP = 2.3669 . Suy ra minA = . 2.3669 128
  20. Hội thảo khoa học, Ninh Bình 15-16/09/2018 3.2 Một số bài toán cực trị liên quan qua các đề thi Olympic Bài toán 17 (Olympic 30/4/2011). Cho hàm số 2011 F(x) = ∑ (k − 2011x)2 C2011 k x k (1 − x )2011−k . k =0 Tìm giá trị nhỏ nhất của hàm số F ( x ) trên [0; 1] Nhận xét 9. Để giải bài toán này, trước hết ta phải sử dụng các tính chất của các số tổ hợp, công thức khai triển nhị thức Newton để rút gọn hàm số F ( x ). Lời giải. n ∑ (k − nx) Cnk x k (1 − x )n−k 2 A= k =0 n n n ∑ Cnk xk (1 − x) + ∑ ∑ kCnk xk (1 − x) n−k = (nx )2 k2 Cnk x k (1 − x )n−k − 2nx n−k k =0 k =0 k =0 Xét n ∑ kCnk xk (1 − x) n−k A1 = k =0 n n = n ∑ Cnk− 1 k −1 x (1 − x ) n−k = nx ∑ Cnk−−11 xk−1 (1 − x)n−k k =1 k =1 n −1 = nx [ x + (1 − x )] = nx n n−k A2 = ∑ k2 Cnk xk (1 − x) k =0 n = n ∑ kCnk− 1 k −1 x (1 − x ) n−k k =1 n n = nx ∑ Cnk−−11 xk−1 (1 − x)n−k + n ∑ (k − 1)Cnk−−11 xk (1 − x)n−k k =1 k =1 n = nx + n(n − 1) x2 ∑ Cnk−−22 xk−2 (1 − x)n−k = nx + n(n − 1)x2 . k =2 n n−k A3 = ∑ Cnk xk (1 − x) = [ x + (1 − x )]n = 1. k =0 Vậy A = (nx )2 + nx + n(n − 1) x2 − 2(nx )2 = nx (1 − x ). Áp dụng kết quả trên ta được F ( x ) = 2011x (1 − x ). Do x ∈ [0; 1] nên x ≥ 0, 1 − x ≥ 0. Áp dụng bất đẳng thức AM-GM, ta có x + (1 − x )   1 F ( x ) ≤ 2011 . Dấu đẳng thức xảy ra khi x = . 2 2 2011 1 Vậy max F ( x ) = ⇔x= . [0;1] 4 2 Nhận xét 10. Ta có thể thay số 2011 trong hàm số f ( x ) bởi một số thực dương bất kì. Xuất phát từ 129
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2