Xem mẫu
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- f ( x j )
- ≥ n! .
-
-
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
- 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
- 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
- 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
- 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
nguon tai.lieu . vn
