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

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------

BÙI THỊ LỢI

BẤT ĐẲNG THỨC VÀ CÁC BÀI TOÁN

CỰC TRỊ TRONG ĐẠI SỐ TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2017

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------

BÙI THỊ LỢI

BẤT ĐẲNG THỨC VÀ CÁC BÀI TOÁN

CỰC TRỊ TRONG ĐẠI SỐ TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN 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. NGUYỄN VĂN MẬU

THÁI NGUYÊN - 2017

i MỤC LỤC

LỜI CẢM ƠN ii

MỞ ĐẦU iii

Chương 1. Nhị thức Newton và một số đẳng thức tổ hợp liên quan 1

1.1 Các tính chất của nhị thức Newton . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Các tính chất của các số tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Một số đẳng thức tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Đa thức Newton và ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4.1 Đa thức Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4.2 Biểu diễn đơn vị thành tổng các phân số Ai Cập với mẫu số lẻ . . . . . . 16

1.5 Một số dạng toán thi Olympic liên quan . . . . . . . . . . . . . . . . . . . . . . 21

1.5.1 Tính chia hết của biểu thức tổ hợp . . . . . . . . . . . . . . . . . . . . . 21

1.5.2 Quan hệ đồng dư giữa các biểu thức tổ hợp . . . . . . . . . . . . . . . . 23

Chương 2. Bất đẳng thức trong tính toán tổ hợp 30

2.1 Các bất đẳng thức cơ bản trong đại số . . . . . . . . . . . . . . . . . . . . . . . 30

2.2 Một số bài toán về bất đẳng thức trong tính toán tổ hợp . . . . . . . . . . . . . 36

2.2.1 Phép biến đổi tương đương, phương pháp làm trội, làm giảm . . . . . . . 36

2.2.2 Sử dụng các bất đẳng thức cơ bản để chứng minh . . . . . . . . . . . . . 39

Chương 3. Các dạng toán cực trị liên quan đến tổ hợp trong dãy số 42

3.1 Bất đẳng thức trong dãy số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.1.1 Dãy sinh bởi hàm số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.1.2 Ước lượng tích và tổng của một số dãy số . . . . . . . . . . . . . . . . . . 44

3.1.3 Bất đẳng thức trong tập rời rạc . . . . . . . . . . . . . . . . . . . . . . . 47

3.2 Một số bài toán cực trị liên quan đến tổ hợp trong dãy số . . . . . . . . . . . . . 49

3.3 Một số bài toán cực trị liên quan qua các đề thi Olympic . . . . . . . . . . . . . 51

KẾT LUẬN 56

TÀI LIỆU THAM KHẢO 57

LỜI CẢM ƠN

Luận văn này được thực hiện tại trường Đại học Khoa học - Đại học Thái Nguyên và hoàn

thành dưới sự hướng dẫn nhiệt tình của Giáo sư - Tiến sĩ khoa học Nguyễn Văn Mậu. Tác giả

xin trân trọng bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy, người đã tận tình chỉ bảo,

hướng dẫn, động viên khích lệ và tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học

tập và nghiên cứu luận văn.

Qua bản luận văn này, tác giả xin gửi lời cảm ơn tới Ban Giám hiệu trường Đại học Khoa

học - Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán - Tin, cùng các giảng viên đã tham gia

giảng dạy và tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu trong suốt thời gian

qua.

Tác giả xin cảm ơn Sở Giáo dục Đào tạo Ninh Bình và Trường THPT Yên Khánh A, nơi tôi

đang công tác, đã tạo mọi điều kiện tốt nhất để tôi hoàn thành nhiệm vụ học tập.

Tác giả cũng xin cảm ơn gia đình, bạn bè, đồng nghiệp và tất cả mọi người đã quan tâm,

động viên và giúp đỡ để tác giả có thể hoàn thành luận văn của mình.

Tác giả xin chân thành cảm ơn!

Thái Nguyên, ngày 22 tháng 5 năm 2017

Tác giả

Bùi Thị Lợi

MỞ ĐẦU

iii

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.

Hiện nay các tài liệu tham khảo về tổ hợp tuy có nhiều nhưng không được đề cập đầy đủ

và hệ thống trong chương trình chính khóa bậc phổ thông. Vì vậy, 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.

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" 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.

Mục đích của luận văn 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ế.

Luận văn gồm phần mở đầu, kết luận và 3 chương.

Chương 1. Nhị thức Newton và một số đẳng thức tổ hợp liên quan.

Chương 2. Bất đẳng thức trong tính toán tổ hợp.

Chương 3. Các dạng toán cực trị liên quan đến tổ hợp trong dãy số.

Tiếp theo, trong các chương đều trình bày một hệ thống bài tập áp dụng giải các đề thi

HSG và Olympic liên quan.

Chương 1. Nhị thức Newton và một số

đẳng thức tổ hợp liên quan

Trong chương này, tác giả nhắc lại công thức nhị thức Newton, các tính chất cơ bản của

nhị thức Newton, các tính chất cơ bản của các số tổ hợp. Từ đó xây dựng và chứng minh được

một số đẳng thức tổ hợp. Trình bày kết quả về đa thức Newton và ứng dụng. Tác giả cũng nêu

một số dạng toán thi Olympic liên quan đến tính chia hết và quan hệ đồng dư giữa các biểu

thức tổ hợp.

Các kết quả trong chương 1 được trích dẫn từ các tài liệu tham khảo [2], [3], [4], [7], [8] và

1.1 Các tính chất của nhị thức Newton

[9].

n (cid:88)

Với a, b là các số thực và n là số tự nhiên lớn hơn hoặc bằng 2, ta luôn có

nan−kbk,

k=0

(a + b)n = C k (1.1)

trong đó

n =

. C k n! k!(n − k)!

n = C n

n = 1; C 1

n = C n−1

n = n.

Quy ước: C 0

Công thức (1.1) gọi là công thức nhị thức Newton.

2 (cid:88)

Chứng minh. Với n = 2, ta có

2 a2−kbk.

k=0

C k (a + b)2 = a2 + 2ab + b2 =

m (cid:88)

Vậy (1.1) đúng với n = 2. Giả sử (1.1) đúng với n = m; m ∈ N; m ≥ 2. Nghĩa là, ta có

mam−kbk.

k=0

(a + b)m = C k (1.2)

m+1 (cid:88)

Ta phải chứng minh (1.1) đúng với n = m + 1, tức là phải chứng minh

m+1am+1−kbk.

k=0

(a + b)m+1 = C k (1.3)

Thật vậy, ta có

mam−kbk.(a + b)

k=0 m (cid:88)

m (cid:88)

(a + b)m+1 = (a + b)m . (a + b) m (cid:88) = C k theo (1.2)

mam+1−kbk.

mam−kbk+1

k=0

m−1 (cid:88)

= C k C k

m bm+1

mam+1 +

m + C k−1

k=1

m−1 (cid:88)

= C 0 (cid:2)(cid:0)C k (cid:1) am+1−kbk(cid:3) + C m

m+1 bm+1

m+1am+1 +

m+1am+1−kbk(cid:1) + C m+1

k=1

m+1 (cid:88)

= C 0 (cid:0)C k

m+1am+1−kbk.

k=0

= C k

Vậy (1.3) đúng.

Suy ra (1.1) đúng với mọi số tự nhiên n ≥ 2 (điều phải chứng minh).

Tính chất 1.1. Số số hạng của công thức khai triển (1.1) bằng n + 1.

Tính chất 1.2. Các hệ số tổ hợp của nhị thức cách đều hai số hạng đầu và cuối thì bằng nhau.

Tính chất 1.3. Số hạng tổng quát của khai triển nhị thức là số hạng thứ k + 1 và bằng

nan−kbk (cid:0)k ∈ N; k = 0; n(cid:1) .

Tk+1 = C k

n (cid:88)

Tính chất 1.4. Với a = b = 1, ta có

n = 2n.

k=0

C k

n (cid:88)

Tính chất 1.5. Với a = 1, b = −1, ta có

n = 0.

k=0

(−1)kC k

Tính chất 1.6 (Đẳng thức Vandermonde (Vandermonde’s equality)).

m+n.

m = C k

nC 0

m + · · · + C k

nC k−2

m + C 2

nC k−1

m + C 1

nC k

(1.4) C 0

(0 ≤ k ≤ m; 0 ≤ k ≤ n)

n (cid:88)

Chứng minh. Xét đa thức

nxk.

k=0

P (x) = (1 + x)n = C k

m (cid:88)

mxk.

k=0

m+n (cid:88)

Q(x) = (1 + x)m = C k

m+nxk.

k=0

R(x) = (1 + x)m+n = C k

Hệ số của xk trong đa thức P (x).Q(x) bằng

nC k

m + C 1

nC k−1

m + C 2

nC k−2

m + · · · + C k

nC 0 m.

C 0

Hệ số của xk trong đa thức R(x) bằng C k

m+n. m + C 2

nC k

m + C 1

nC k−1

nC k−2

m + · · · + C k

nC 0

m = C k

m+n.

Vì R(x) = P (x)Q(x) nên C 0

Vậy đẳng thức (1.4) được chứng minh.

Nhận xét 1.1. Áp dụng đẳng thức (1.4) với k = m = n, ta có đẳng thức

n )2 = C n 2n.

(cid:0)C 0 (cid:1)2 + (cid:0)C 1 (cid:1)2 + (cid:0)C 2 (cid:1)2 + · · · + (C n

Tính chất 1.7 (Đẳng thức Vandermonde mở rộng). Cho n1, n2, . . . , nr ∈ N và

k = k1 + k2 + · · · + kr. Khi đó

nr = C k

n1C k2

n2 . . . C kr

n1+n2+···+nr.

k1+k2+···+kr=k

1.2 Các tính chất của các số tổ hợp

(cid:88) C k1

Tính chất 1.8 (Tính chất đối xứng). Với mọi số tự nhiên n, k ∈ N thỏa mãn 0 ≤ k ≤ n ta có:

n = C n−k

C k .

Tính chất 1.9 (Tính chất tam giác Pascal).

n + C k+1

n = C k+1 n+1.

C k

n (cid:88)

Tính chất 1.10 (Công thức tính tổng theo cột).

k = C m+1 n+1 .

k=0

C m

n (cid:88)

Chứng minh. Áp dụng công thức Pascal, ta có:

k =

n+1 − C m+1

k+1 − C m+1

k=0

C m (C m+1 ) = C m+1 = C m+1 n+1 .

Nhận xét 1.2. Từ Tính chất1.4, Tính chất 1.9 và Tính chất 1.10 ta có đẳng thức

n + C 2

n + · · · = C 1

n + C 3

n + · · · = 2n−1.

C 0

n (cid:88)

Tính chất 1.11 (Công thức tính tổng theo đường chéo chính).

m+k = C n

m+n+1

k=0

C k

n (cid:88)

Chứng minh.

m+k =

m+k (sử dụng Tính chất 1.8)

k=0

k=0 = C m+1

m+n+1 (sử dụng Tính chất 1.10)

C k C m

m+n+1 (sử dụng Tính chất 1.8).

= C n

n (cid:88)

Tính chất 1.12 (Công thức tính tổng theo đường chéo phụ liên quan đến số Fibonacci).

n−k = Fn+1.

k=0

C k

n = 0, với k > n.

Qui ước C k

Chứng minh.

0 = 1 = F1, C 0

1 + C 0

1 = 1 = F2.

Với n = 0, n = 1 thì C 0

n (cid:88)

n−1−k (sử dụng Tính chất 1.9)

n−k =

n−1−k +

k=0

n−1 (cid:88)

k=0 n−2 (cid:88)

Giả sử công thức trên đúng đến n − 1. Khi đó n (cid:88) C k−1 C k C k

n−k

n−k +

k=0

C k C k =

= Fn−1 + Fn (sử dụng giả thiết quy nạp)

= Fn+1 (sử dụng công thức truy hồi của dãy Fibonacci).

Tính chất 1.13 (Quy tắc hút). Với n, k ∈ N thỏa mãn 0 < k ≤ n ta có:

n =

C k C k−1 n−1. n k

n =

Chứng minh. Ta có C k = . = C k−1 n−1. n! k!(n − k)! n k (n − 1)! (k − 1)!(n − k)! n k

Tính chất 1.14 (Công thức lùi cơ số). Với n, k ∈ N thỏa mãn 0 ≤ k < n ta có:

n =

n−1.

C k C k

n =

n−1.

Chứng minh. Ta có C k . = = C k n n − k n n − k n! k!(n − k)! (n − 1)! k!(n − 1 − k)! n n − k

(cid:37)

   

   +1

Tính chất 1.15 (Tính đơn điệu (monotonicity)).

(cid:36) n 2

n < C 1

n < · · · < C n

1.3 Một số đẳng thức tổ hợp

n − 1 2 C 0 = C > · · · > C n n .

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 tính chất của

các số 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.

Bài toán 1.1. Tính tổng

2n + α2C 2

2n + α4C 4

2n + · · · + α2nC 2n 2n .

(1.5) S1 = C 0

2n + α3C 3

2n + α5C 5

2n + · · · + α2n−2C 2n−1

. (1.6) S2 = αC 1

2n (cid:88)

Lời giải. Xét khai triển

2nαk.

k=0 2n (cid:88)

C k (1.7) (1 + α)2n =

2n.(−1)kαk.

k=0

C k (1.8) (1 − α)2n =

Cộng từng vế hai đẳng thức (1.7) và (1.8), ta được

. 2S1 = (1 + α)2n + (1 − α)2n ⇔ S1 = (1 + α)2n + (1 − α)2n 2

Trừ từng vế đẳng thức (1.7) cho đẳng thức (1.8), ta được

. 2S2 = (1 + α)2n − (1 − α)2n ⇔ S2 = (1 + α)2n − (1 − α)2n 2

Bài toán 1.2. Tính tổng

n + 2αC 2

n + 3α2C 3

n + · · · + nαn−1C n n .

(1.9) S3 = C 1

2n + · · · + (2n − 1)C 2n−1

2n + 5C 5

2n + 3C 3

. (1.10) S4 = C 1

Lời giải. Theo Tính chất 1.13, ta có

n =

n−1 ⇔ kC k

n = nC k−1 n−1.

C k C k−1 n k

n−1 (cid:88)

Do đó

n−1 = n (1 + α)k−1 .

k=0

n−1 (cid:88)

αkC k S3 = n

2n−1 = 2n · 22n−2.

k=0

C 2k S4 = 2n

2n (cid:88)

Bài toán 1.3. Chứng minh rằng

2n =

k=1

(−1)k+1C k . (1.11) k k + 1 1 2n + 1

Lời giải. Biến đổi vế trái đẳng thức (1.11), ta có

2n (cid:88)

2n =

k=1

k=1 2n (cid:88)

2n (cid:88)

(cid:18) (cid:19) (−1)k+1C k 1 − (−1)k+1C k 2n k k + 1 1 k + 1

2n −

k=1

2n (cid:88)

(−1)k+1C k = (−1)k+1C k 2n 1 k + 1

2n −

k=0

k=1

(−1)kC k = C 0 (−1)k+1C k+1 2n+1 1 2n + 1

2n+1 − 1(cid:3)

· (cid:2)(1 − 1)2n+1 + C 1 = 1 − (1 − 1)2n −

= 1 − · (cid:0)C 1 1 2n + 1

= 1 − 1 + = . 1 2n + 1 1 2n + 1 2n+1 − 1(cid:1) 1 2n + 1

2n+1).

2n =

(Vì theo Tính chất 1.13, thì C k C k+1 1 k + 1 1 2n + 1 Vậy (1.11) được chứng minh.

n có thể tính bằng cách sử dụng phép tính đạo hàm.

n (cid:80) k=1

Nhận xét 1.3. Tổng kC k

2n (cid:80) k=0

Tổng (−1)k+1C k+1 có thể tính bằng cách sử dụng phép tính tích phân. 1 k + 1

Sử dụng phép tính đạo hàm, phép tính tích phân, ta có thể giải được bài toán sau đây.

Bài toán 1.4. Chứng minh rằng

n )2 = nC n

2n−1.

1) (cid:0)C 1 (cid:1)2 + 2 (cid:0)C 2 (cid:1)2 + 3 (cid:0)C 3 (cid:1)2 + · · · + n (C n (1.12)

n = n(n + 1)2n−2.

n + · · · + n2C n

n + 32C 3

(1.13)

2n =

n + 22C 2 22k+1 − 1 2k + 1

k=0

2) 12C 1 n (cid:88) 3) C 2k . (1.14) 32n+1 − 22n+1 + 1 2(2n + 1)

Lời giải.

n (cid:88)

1) Ta có

n.xk.

k=0

C k (1.15) (1 + x)n =

n (cid:88)

Đạo hàm hai vế của đẳng thức (1.15), ta có

n.xk−1.

k=1

n(1 + x)n−1 = kC k (1.16)

n (cid:88)

Nhân từng vế của (1.15) với (1.16), ta có

n.xk ·

n.xk−1.

k=0

k=1

n(1 + x)2n−1 = (1.17) C k kC k

2n−1.

Hệ số của xn−1 trong đa thức ở vế trái của (1.17) là nC n

Hệ số của xn−1 trong đa thức ở vế phải của (1.17) là

n )2 .

(cid:0)C 1 (cid:1)2 + 2 (cid:0)C 2 (cid:1)2 + 3 (cid:0)C 3 (cid:1)2 + · · · + n (C n

Do đó, ta có

n )2 = nC n

2n−1.

(cid:0)C 1 (cid:1)2 + 2 (cid:0)C 2 (cid:1)2 + 3 (cid:0)C 3 (cid:1)2 + · · · + n (C n

Vậy (1.12) được chứng minh.

n (cid:88)

2) Ta có

n.xk.

k=0

(1 + x)n = C k (1.18)

n (cid:88)

Đạo hàm hai vế của đẳng thức (1.18), ta có

n.xk−1.

k=1

n(1 + x)n−1 = kC k (1.19)

n (cid:88)

Nhân hai vế của (1.19) với x, ta được

n.xk.

k=1

nx(1 + x)n−1 = kC k (1.20)

n (cid:88)

Đạo hàm hai vế của đẳng thức (1.20), ta thu được đẳng thức

n.xk−1.

k=1

n(1 + x)n−1 + n(n − 1)x(1 + x)n−2 = k2C k (1.21)

Thay x = 1, vào đẳng thức (1.21), ta được

n + 22C 2

n + 32C 3

n + · · · + n2C n

n = n(n + 1)2n−2.

12C 1

Vậy (1.13) được chứng minh.

2n (cid:88)

3) Ta có

2n.xk.

k=0 2n (cid:88)

(1 + x)2n = C k (1.22)

2n.(−x)k.

k=0

(1 − x)2n = C k (1.23)

n (cid:88)

Cộng từng vế của hai đẳng thức (1.22) và (1.23) rồi chia hai vế cho 2, ta được

2n.x2k =

k=0

. (1.24) C 2k (1 + x)2n + (1 − x)2n 2

2 (cid:90)

n (cid:88)

Lấy tích phân từ 1 đến 2 hai vế của đẳng thức (1.24), ta có

2nxkdx =

k=0

n (cid:88)

C k dx (1 + x)2n + (1 + x)2n 2

1 x2k+1 2k + 1

1 (1 + x)2n+1 − (1 − x)2n+1 2(2n + 1)

k=0 n (cid:88)

= ⇔ C 2k 2n (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

2n =

k=0

C 2k . ⇔ 22k+1 − 1 2k + 1 32n+1 − 22n+1 + 1 2(2n + 1)

Vậy đẳng thức (1.14) được chứng minh.

Kết hợp với kiến thức về số phức, ta có các bài toán sau:

Bài toán 1.5. Tính tổng

0≤2k

(cid:88) S5 = (−1)kC 2k n .

1≤2k+1

(−1)kC 2k+1 . S6 =

0≤4k

S7 = C 4k n .

1≤4k+1

. S8 = C 4k+1 n

n (cid:88)

Lời giải. Với i là đơn vị ảo (i2 = −1), ta có

n.ik

k=0

n (cid:88)

(1 + i)n = C k (1.25)

n .i2k +

0≤2k

1≤2k+1

⇔ (1 + i)n = C 2k .i2k+1 C 2k+1 n

n (cid:88)

n + i.

0≤2k

1≤2k+1

(cid:88) ⇔ (1 + i)n = (−1)kC 2k .i2k C 2k+1 n

n + i.

0≤2k

1≤2k+1

⇔ (1 + i)n = (−1)kC 2k (−1)kC 2k+1 . (1.26)

Lại có

(cid:16) (cid:17)(cid:105)n (cid:104)√ + i sin (1 + i)n = π 4 π 4 2 (cid:16)√ (cid:17) ⇔ (1 + i)n = cos (cid:17)n (cid:16) 2 cos + i sin . (1.27) nπ 4 nπ 4

Đồng nhất phần thực với phần thực ở vế phải của hai đẳng thức (1.26) và (1.27), ta được

n =

0≤2k

(cid:88) . (1.28) (−1)kC 2k (cid:16)√ (cid:17)n 2 cos nπ 4

2(cid:1)n . cos Vậy S5 = (cid:0)√ nπ 4 Đồng nhất phần ảo với phần ảo ở vế phải của hai đẳng thức (1.26) và (1.27), ta được

1≤2k+1

(cid:16)√ (cid:88) (−1)kC 2k+1 = (cid:17)n 2 sin . (1.29) nπ 4

2(cid:1)n sin . Vậy S6 = (cid:0)√ nπ 4

n, 2n =

n (cid:80) k=0

Mặt khác 0 = (1 − 1)n = (−1)kC k C k n.

Suy ra

n = 2n−1.

0≤2k

(cid:88) (1.30) C 2k

0≤2k+1

(1.31) = 2n−1. C 2k+1 n

Cộng từng vế đẳng thức (1.28) và (1.30) rồi chia hai vế cho 2, ta được

(cid:0)√ 2(cid:1)n cos + 2n−1 nπ 4 . S7 = 2

Cộng từng vế đẳng thức (1.29) và (1.31) rồi chia hai vế cho 2, ta được

(cid:0)√ 2(cid:1)n sin + 2n−1 nπ 4 . S8 = 2

Bài toán 1.6. Tính tổng

0≤3k

(cid:88) (1.32) S9 = C 3k n .

n (cid:88)

Lời giải. Xét đa thức

nxk.

k=0

P (x) = (1 + x)n = C k

√

+ i là một căn nguyên thủy bậc ba của đơn vị. Gọi ω = − 3 2 1 2 Ta có

ω2 + ω + 1 = 0.

Suy ra

  ω2k + ωk + 1 = ...3 0 khi k (cid:54) ...3 3 khi k 

n (cid:88)

Vì thế

n(1 + ωk + ω2k)

k=0

C k P (1) + P (ω) + P (ω2) =

0≤3k

(cid:88) = 3 C 3k n .

Suy ra

(cid:2)P (1) + P (w) + P (w2)(cid:3) . S9 = 1 3

Mà

P (1) = (1 + 1)n = 2n. √ (cid:33)n (cid:32)

+ i P (ω) = 1 − 1 2 √ 3 2 (cid:33)n (cid:32)

= + i 3 2 1 2

(cid:17)n (cid:16) + i sin = cos

+ i sin .

= cos  π 3 nπ 3 (cid:32)

P (ω2) = − + i (cid:33)2 n  1 + 1 2 π 3 nπ 3 √ 3 2

√ (cid:32) (cid:33)n

= − i 1 2

(cid:17) (cid:16) (cid:16) (cid:17)(cid:105)n (cid:104) cos − = + i sin − 3 2 π 3 π 3

+ i sin . = cos −nπ 3 −nπ 3

Nên

(cid:16) (cid:17) 2n + 2 cos . S9 = 1 3 nπ 3

Nhận xét 1.4. Công thức Euler eiϕ = cos ϕ + i sin ϕ có thể đưa các tổng lượng giác thành các

cấp số nhân hoặc công thức Nhị thức Niutơn, cụ thể xét bài toán sau.

n (cid:88)

Bài toán 1.7.

n cos kx.

k=0

m−1 (cid:88)

C k a) Tính tổng S10 =

2m.

2m cos(2m − 2k) +

k=0

b) Chứng minh rằng 22m−1 cos2m x = C k C m 1 2

Lời giải.

n sin kx, ta có

n (cid:80) k=0

n (cid:88)

a) Xét T = C k

n(cos kx + i sin kx) =

neikx

k=0

C k C k S10 + iT =

= (1 + eix)n = (1 + cos x + i sin x)n

(cid:16) (cid:17)n (cid:16) (cid:17)n cos + i sin

(cid:16) (cid:17) cos + i sin . x = 2 cos 2 = 2n cosn x 2 x 2 nx 2 x 2 nx 2

cos . So sánh phần thực, phần ảo ta được S10 = 2n cosn x 2 nx 2

b) Ta có eix = cos x + i sin x; e−ix = cos x − i sin x ⇒ cos x = . eix + e−ix 2 Do đó

2m (cid:88)

22m cos2m x = (2 cos x)2m = (eix + e−ix)2m

2m(eix)k(e−ix)2m−k

k=0 2m (cid:88)

= C k

2me2(k−m)ix

2m (cid:88)

k=0 m−1 (cid:88)

= C k

2me2(k−m)ix +

2me2(k−m)ix + C m 2m

k=m+1

k=0

m−1 (cid:88)

C k C k =

2me−2(m−k)ix +

2m e2(m−t)ix + C m 2m

t=0

k=0

= C k C 2m−t

m−1 (cid:88)

2me−2(m−k)ix +

2m e2(m−k)ix + C m 2m

k=0

k=0 m−1 (cid:88)

= C k C 2m−k

2m(e−2(m−k)ix + e2(m−k)ix) + C m 2m

k=0

m−1 (cid:88)

= C k

2m cos(2m − 2k)x + C m 2m.

k=0

m−1 (cid:88)

= 2 C k

2m, (đpcm).

2m cos(2m − 2k)x +

k=0

C m Suy ra 22m−1 cos2m x = C k 1 2

n (cid:88)

Với cách làm tương tự như trên, ta cũng chứng minh được đẳng thức

2n+1 cos(2n + 1 − 2k)x.

k=0

22n cos2n+1 x = C k

Sử dụng công thức 2i sin x = eix − e−ix và biến đổi tương tự như trên, ta chứng minh được các

đẳng thức sau

2n cos(2n − 2k)x +

k=0

n (cid:88)

(cid:33) (cid:32)n−1 (cid:88) . 22n−1 sin2n x = (−1)n (−1)kC k C n 2n (−1)n 2

2n+1 sin(2n + 1 − 2k)x.

k=0

1.4 Đa thức Newton và ứng dụng

1.4.1 Đa thức Newton

22n sin2n+1 x = (−1)n (−1)kC k

Bổ đề 1.1 (Khai triển Newton). Cho n và m là các số nguyên dương. Với bất kỳ x = (x1, x2, · · · , xn) trong Rn, ta có

|α|=m

2 . . . xαn

n và tổng chạy

(cid:88) xα, (1.33) (x1 + x2 + · · · + xn)m = m! α!

trong đó α! = α1!α2! · · · αn! với α = (α1, α2, · · · , αn) trong Nn, xα = xα1 1 xα2 qua tất cả α có thể có trong Nn thỏa mãn |α| = α1 + α2 + · · · + αn = m.

Chứng minh.

m (cid:88)

Với n = 2, theo nhị thức Newton ta có

1xm−j xj

j=0 m (cid:88)

(x1 + x2)m = m! j!(m − j)!

2 , α1 = j, α2 = m − j.

|α|=m

= xα1 1 xα2 m! α1!.α2!

Giả sử đẳng thức (1.33) đã đúng cho đến n-1.

Đặt

X = x1 + x2 + · · · + xn−1, α(cid:48) = (α1, α2, . . . , αn).

m (cid:88)

Khi đó ta có

αn=0

m (cid:88)

(x1 + x2 + · · · + xn)m = (X + xn)m = X m−αnxαn n m! (m − αn)!.αn!

n .(x1 + x2 + · · · + xn−1)m−αn xαn

αn=0 m (cid:88)

= m! (m − αn)!.αn!

αn=0

|α(cid:48)|=m−αn

(cid:88) = xα(cid:48) xαn n . m! (m − αn)!.αn! (m − αn)! α1!α2! . . . αn−1!

1 xα2 xα1

2 . . . .xαn n .

|α|=m

(cid:88) = m! α1!α2! . . . αn!

Bổ đề được chứng minh.

n (cid:88)

Bổ đề 1.2 (Khai triển Taylor). Cho một đa thức

j=0

f (x) = (1.34) ajxj.

Khi đó, hệ số thứ j của f (x) có thể được biểu diễn bởi

f (j)(0), (1.35) aj = 1 j!

trong đó f (j)(0) ứng với đạo hàm cấp j tại 0.

Chứng minh. f là hàm khả vi vô hạn. Đạo hàm lần thứ j của xk là

(cid:19)j xk−j. (1.36) xk = (cid:18) d dx k! (k − j)!

Nếu j ≤ k và

(cid:19)j xk = 0. (1.37) (cid:18) d dx

Nếu j > k, ta có

n (cid:88)

k=j

k=0

(cid:19)j xk = (1.38) f (x) = akxk−j, ak (cid:18) d dx k! (k − j)!

với bất kì j nằm giữa 0 và n. Khi đó

(1.39) f j(0) = j!aj.

Suy ra

f (j)(0). (1.40) aj = 1 j!

Bổ đề dược chứng minh.

Bổ đề 1.3. Cho n là một số nguyên dương. Ta đặt

(cid:19)n (cid:18) x2 + · · · + xn g(x) = x + . (1.41) 1 2 1 n

Khi đó g(n)(0) = n!

Chứng minh. Ta có

(cid:18) (cid:19)n 1 + = xnh(x), (1.42) g(x) = xn x + · · · + xn−1 1 2 1 n

trong đó

(cid:18) (cid:19)n h(x) = 1 + x + · · · + xn−1 . (1.43) 1 2 1 n

Áp dụng công thức Leibniz

n (cid:88)

j=0 n (cid:88)

j=0

(cid:19)n−j (cid:19)j xn. h(x) g(n)(x) = n! (n − j)!j! (cid:18) d dx (cid:18) d dx (1.44) (cid:19)j = xj. h(x). n!n! (n − j)!j!j! (cid:18) d dx

Do đó, ta thu được

g(n)(0) = n!h(0) = n!. (1.45)

Bổ đề được chứng minh.

Định lý 1.1. Với bất kỳ số nguyên dương n, ta có đẳng thức

n (cid:89)

j=1

α∈Sn

(cid:88) = 1, (1.46) 1 αj!jαj

n (cid:88)

trong đó tổng trên Sn chạy qua tất cả α = (α1, α2, · · · , αn) có thể có trong Nn thỏa mãn điều kiện

j=1

(1.47) jαj = n.

Chứng minh. Theo Bổ đề 1.1, ta có

|α|=m

(cid:18) (cid:19)m (cid:19)α2 (cid:19)αn (cid:88) . · · · . = x1 + xα1 1 . x2 2 + · · · + xn n x2 2 xn n 1 2 1 n m! α! (cid:18) 1 2 (cid:18) 1 n

n (cid:89)

j=1

|α|=m

(1.48) (cid:88) = m! . xjαj j 1 αj!jαj

Cho m = n và xj = t với j = 1, 2, · · · , n dẫn đến

n (cid:89)

j=1

|α|=n

(cid:19)n (cid:18) (cid:88) t2 + · · · + tn (1.49) = n! tjαj . t + 1 2 1 n 1 αj!jαj

So sánh hệ số của tn trong cả hai đồng nhất thức. Theo các Bổ đề 1.2 và 1.3 ta thu được n! đối

với vế trái. Mặt khác hệ số tn trong vế phải là tổng của tất cả số hạng với tn mà được viết bởi

n (cid:89)

j=1

α∈Sn

(cid:88) (1.50) , 1 αj!jαj

trong đó tổng chạy qua tất cả α có thể có trong Sn xác định bởi

(1.51) Sn = {α ∈ Nn; α1 + 2α2 + · · · + nαn = n} .

Do đó ta thu được

n (cid:89)

j=1

α∈Sn

(cid:88) (1.52) = 1, 1 αj!jαj

và ta có điều phải chứng minh.

Ví dụ 1.1. Xét phương trình vô định sau đây

α1 + 2α2 + 3α3 + 4α4 = 4.

Lời giải. Dễ thấy rằng phương trình đã cho có các nghiệm nguyên không âm chỉ là

α = (α1, α2, α3, α4) = (4, 0, 0, 0), (0, 0, 0, 1), (1, 0, 1, 0), (0, 2, 0, 0), (2, 1, 0, 0).

Tiếp theo, ta tính các đại lượng

Πα = α1!1α1.α2!2α2.α3!3α3.α4!4α4, α = (α1, α2, α3, α4).

Ta có

Π1 = 4!14.0!20.0!30.0!40 = 24,

Π2 = 0!10.0!20.0!30.1!41 = 4,

Π3 = 1!11.0!20.1!31.0!40 = 3,

Π4 = 0!10.2!22.0!30.0!40 = 8,

Π5 = 2!12.1!21.0!30.0!40 = 4.

Suy ra

+ + + = + + + + = 1. 1 24 1 4 1 3 1 8 1 4 1 Π1 1 Π2 1 Π3 1 Π4

Ví dụ 1.2. Xét phương trình vô định sau đây

α1 + 2α2 + 3α3 + 4α4 + 5α5 = 5.

Lời giải. Dễ thấy rằng phương trình đã cho có các nghiệm nguyên không âm chỉ là

α = (α1, α2, α3, α4, α5) = (5, 0, 0, 0, 0), (0, 0, 0, 0, 1), (0, 1, 1, 0, 0),

(1, 2, 0, 0, 0), (2, 0, 1, 0, 0), (1, 0, 0, 1, 0), (3, 0, 1, 0, 0).

Tiếp theo, ta tính các đại lượng

Πα = α1!1α1.α2!2α2.α3!3α3.α4!4α4.α5!5α5, α = (α1, α2, α3, α4, α5).

Ta có

Π1 = 5!15.0!20.0!30.0!40.0!.50 = 120,

Π2 = 0!10.0!20.0!30.1!40.1!51 = 5,

Π3 = 0!11.1!21.1!31.0!40.0!50 = 6,

Π4 = 1!11.2!22.0!30.0!40.0!50 = 8,

Π5 = 2!12.0!20.1!31.0!40.0!50 = 4,

Π6 = 1!11.0!20.0!30.1!41.0!50 = 4,

Π7 = 3!13.0!20.1!31.0!40.0!50 = 18.

Suy ra

1.4.2 Biểu diễn đơn vị thành tổng các phân số Ai Cập với mẫu số

lẻ

+ + + + + + = + + + + + + = 1. 1 120 1 5 1 6 1 8 1 4 1 4 1 18 1 Π1 1 Π2 1 Π3 1 Π4 1 Π5 1 Π6 1 Π7

Hai bài toán tối ưu hóa liên quan đến biểu diễn của 1 bằng tổng các phân số Ai Cập với

mẫu số lẻ đã được giải quyết. Lời giải duy nhất với các mẫu số lẻ lên tới 105 được cho bởi 3,

5, 7, 11, 33, 35, 45, 55,7 7, 105. Có 5 lời giải khi chỉ có 9 mẫu số được sử dụng.

Bằng phân số Ai Cập với độ dài l nghĩa là Ta có một biểu diễn có dạng

+ + · · · + , 1 a1 1 a2 1 an

trong đó ai là các số nguyên dương phân biệt. Ta xem xét biểu diễn của 1 bởi các phân số với

các mẫu số lớn hơn 1, đơn giản là

+ + = 1. 1 2 1 3 1 6

Bài toán trở lên phức tạp hơn nhiều nếu Ta thêm điều kiện rằng các mẫu số được sử dụng

không chia hết cho một vài số nguyên tố đầu tiên. Đặc biệt, bài toán tìm một biểu diễn với

mẫu số lẻ cũng rất thú vị. Vấn đề trên đây liên quan đến lời giải của phương trình

+ + · · · + (1.53) = 1, 3 ≤ a1 < a2 < · · · < an; (ai, 2) = 1, 1 a1 1 a2 1 an

trong đó l là số lẻ. John Leech đã tìm thấy lời giải

+ + + + + + + + + + = 1, (1.54) 1 3 1 15 1 21 1 27 1 35 1 63 1 105 1 135 1 5 1 7 1 9

trong đó có l = 11 và al = 135. Ông cũng thấy rằng bất kỳ lời giải nào phải có al ≥ 105 và

l ≥ 9. Ta đưa ra lời giải của hai bài toán tối ưu được đưa ra bởi Leech. Ta có lời giải sau đây

+ + + + + + + + + = 1, (1.55) 1 11 1 33 1 45 1 55 1 77 1 105 1 5 1 7 1 9 1 3

với al = 105 và cũng có năm lời giải sau với l = 9

 + + + + + + + + = 1, 1 3 1 21 1 7 1 5 1 9 1 11 1 15

+ + + + + + + + = 1,

(1.56) + + + + + + + + = 1,

+ + + + + + + + = 1,

+ + + + + + + + = 1.   1 3 1 3 1 3 1 3 1 5 1 5 1 5 1 5 1 7 1 7 1 7 1 7 1 9 1 9 1 9 1 9 1 11 1 11 1 11 1 11 1 15 1 15 1 15 1 15 1 135 1 165 1 231 1 45 1 45 1 21 1 21 1 33 1 35 1 10395 1 693 1 315 1 385 1 231

Ta sẽ chứng minh hai định lý sau đây

Định lý 1.2. Mọi lời giải của phương trình (1.53) đều có dạng al ≥ 105. Lời giải (1.55) là duy

nhất với al = 105.

Chứng minh. Ta lấy A ⊂ {3, 5, 7, . . . , 133} , viết f (A) là phân số được biểu diễn bằng tổng

các phân số Ai Cập với các mẫu số a ∈ A và tiến hành đi tìm tất cả các tập hợp A với f (A) = 1.

Cho giới hạn là 133, có thể chấp nhận bội lẻ lớn nhất của số nguyên tố p được cho bởi b = 1

với 47 ≤ p ≤ 133, b = 3 cho 29 ≤ p ≤ 43; b = 5 cho p = 23; b = 7 với p = 17, 19; và b = 9 với

p = 13.

Đối với mỗi một trong 31 vec-tơ khác không ((cid:15)1, (cid:15)2, (cid:15)3, (cid:15)4, (cid:15)5),trong đó (cid:15)i = 1 hoặc 0, Ta đặt

+ + + = , (L, M ) = 1. (1.57) (cid:15)1 + (cid:15)2 3 (cid:15)3 5 (cid:15)4 7 (cid:15)5 9 L M

Nếu một số nguyên tố p ≤ 13 không chia hết bất kì một trong 31 giá trị của L trong (1.57)

bằng điều kiện Diophantine, không có phần tử nào của A có thể là một bội số của p. Lập luận

cũng áp dụng cho lũy thừa của một số nguyên tố với một thay đổi rõ ràng. Trong số 31 phương

trình của (1.57) chỉ có 4 phương trình sau liên quan đến bài này.

(1.58) + = , 1 + + + = , 1 + 1 3

1 + = , + + = . + 1 5 1 3 23 15 1 9 13 9 1 3 1 5 1 5 1 7 1 7 1 9 11 × 16 105 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} , (1.59) A4 = 11 {5, 7, 9} , A5 = 13 {5, 7, 9}

trong đó p {a, b, c} nghĩa là {pa, pb, pc}. Đặt

(1.60) A0 = {d : 1 < d < h, d|h} , h = 315,

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} ,

∈ A0. Theo lập luận của ta A phải là hợp của các tập và chú ý rằng a ∈ A0 nếu và chỉ nếu h a 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

, , , , , , i = 0, 1, 2, 3, 4, 5, (1.61) f (Ai) = 44 45 1 15 16 105 1 9 13 315 11 315

. Các phân số Ai Cập tương ứng với 17 phép hợp rời nhau có 121 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 giá trị là 1 + và tổng của sáu số này là 1 + r h 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).

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ó

+ = 1 + = 1 + + + . f (A0 ∪ A2) = 44 45 16 105 5 + 15 + 21 315 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 = 63, 21, 15 ∈ A0. Do đó Ta có một lời giải cho (1.53), cụ thể là h a

(cid:18) (cid:19) + + + + + + + 1 + + + = 1, f (A0 ∪ A2\ {15, 21, 63}) = 1 3 1 5 1 7 1 9 1 35 1 45 1 105 1 11 1 3 1 5 1 7

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à

(cid:18) (cid:19) (cid:19) + + + + + + + + + + 1 + + = 1, 1 15 1 35 1 105 1 23 1 5 1 11 (cid:18) 1 5 1 3 1 7 1 9 1 3 1 5 1 7 1 9

và (cid:18) (cid:19) (cid:19) + + + + + + + 1 + + + + + = 1. 1 15 1 45 1 63 1 23 1 5 1 11 (cid:18) 1 5 1 3 1 7 1 9 1 3 1 5 1 7 1 9

Đị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

với al < 135, một lời giải là tối ưu, đó là (1.55).

Chứng minh.

< 1, + + + + + + Dễ thấy (1.53) không có lời giải nếu l = 7. Cho nên a7 ≤ 23 thì 1 5 1 11 1 23 1 9 1 3 1 7

1 13 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. 1 3 1 5 1 9 1 11 1 13 1 15 1 17 1 19 1 105

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. 1 3 1 5 1 7 1 9 1 11 1 13 1 67 1 69 1 105

Ta cũng suy ra rằng a7 ≤ 65.

27 = 6201 tập hợp của các số lẻ (a4, a5, a6, a7) thỏa mãn

28 + C 3

Tiếp theo, mỗi một trong C 3

a4 = 9, 11, a4 < a5 < a6 < a7 ≤ 65.

Ta viết (cid:19) (cid:19) = 1 − + + − + + + . (1.62) 2m n (cid:18) 1 3 1 5 1 7 (cid:18) 1 a4 1 a5 1 a6 1 a7

Đó một điều kiện cần thiết (1.62) có thể được giải thích là

0 < ≤ + , 1 105 1 a7 + 2

cho bởi (1.62). Hơn nữa (1.53) viết lại là mà được thỏa mãn bởi chỉ 78 giá trị 2m n 2m n

(1.63) , = + 2m n 1 a8 1 a9

. Việc tìm kiếm tất cả các lời giải cho (1.53) không điều kiện a8 < a9 bây giờ có nghĩa là a8 < m n

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à tương ứng với 1438 1036035 (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 = 325 × 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.

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−1 (cid:80) k=0

một ước của n (−1)kC k n.

m−1 (cid:88)

Lời giải. Ta có thể viết lại biểu thức đã cho như sau:

n = n

n−1 + C k−1 n−1)

k=0

k=0 m−1 (cid:88)

m−1 (cid:88)

n (−1)kC k (−1)k(C k

n−1 + n

k=0 m−1 (cid:88)

k=0 m−2 (cid:88)

= n (−1)kC k (−1)kC k−1 n−1

n−1 − n

n−1

k=0

= n (−1)kC k (−1)kC k

= n(−1)m−1C m−1 n−1

= m(−1)m−1C m n .

m−1 (cid:80) k=0

Vậy m|n (−1)kC k n.

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

n + C 3 n.

n + C 2

chia hết cho 1 + C 1

Lời giải. Vì 2 là số nguyên tố nên

n + C 2

n + C 3

n = 2k, với 0 ≤ k ≤ 2000.

C 1

Ta có

n + C 2

n + C 3

n =

. 1 + C 1 (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 .

+) 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.

mpk−1 − 1.

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|C p−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) = S1xp−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à deg P = p − 2

...p, ∀i = 1, p − 2. Mặt khác, ta có cho nên Si

P (p) = −pp−1 ⇒ p3|P (p) ⇒ p3|pSp−2,

hay p2|Sp−2. Để ý rằng

mpk−1 =

C p−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

mpk−1 − 1)(p − 1)!.

pk+2|(C p−1

Suy ra

pk+2|(mpk − 1) . . . (mpk − (p − 1)) − (p − 1)!

p−1

p−2

p−1

⇔ pk+2|P (mpk) + (mpk)

. (1.64) ⇔ pk+2|S1(mpk) + · · · + Sp−2mpk + (mpk)

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 (cid:23) (cid:22) 2p 3

k (cid:88)

. Chứng minh rằng Bài toán 1.11 (Putnam 1996). Cho số nguyên tố p ≥ 5 và k =

p ≡ 1

i=0

(mod p2). C i

k (cid:88)

Lời giải. Ta có

p ≡ 1

p−1 ≡ 0

i=1

i=0

C i (mod p2) ⇔ C i−1 (mod p2), p i

k (cid:88)

hay

p−1 ≡ 0

i=1

C i−1 ≡ 0 (mod p). (mod p) ⇔ (−1)i−1 i 1 i

Do p ≥ 5 là số nguyên tố nên p có dạng 6m ± 1.

2m−1 (cid:88)

4m−1 (cid:88)

k (cid:88)

• Xét p = 6m − 1, k = 4m − 1 ta có

j=1

i=1

2m−1 (cid:88)

4m−1 (cid:88)

− 2 = (−1)i−1 i 1 2j 1 i

i=1

i=1 4m−1 (cid:88)

− = 1 j 1 i

i=2m

= . 1 i

Lại có

4m−1 (cid:88)

2m (cid:88)

i=2m

i=1 2m (cid:88)

(cid:18) (cid:19) 2 + = 1 i 1 2m − 1 + i 1 4m − i

i=1 2m (cid:88)

= 6m − 1 (2m − 1 + i)(4m − i)

i=1

= ≡ 0 (mod p). p (2m − 1 + i)(4m − i)

4m−1 (cid:88)

Vì gcd(p, (2m − 1 + i)(4m − i)) = 1, ∀i = 1, 2m nên

i=2m

≡ 0 (mod p). 1 i

k (cid:88)

4m (cid:88)

2m (cid:88)

4m (cid:88)

2m (cid:88)

4m (cid:88)

• Xét p = 6m + 1, k = 4m ta có

i=1

j=1

i=1

j=1

i=2m+1

= − 2 = − = . (−1)i−1 i 1 i 1 2j 1 i 1 j 1 i

Lại có

4m (cid:88)

2m (cid:88)

i=2m+1

i=1

2m (cid:88)

(cid:19) (cid:18) 1 2 + = 1 i 2m + i 1 4m + 1 − i

i=1 2m (cid:88)

= 6m + 1 (2m + i)(4m + 1 − i)

i=1

= ≡ 0 (mod p). p (2m + i)(4m + 1 − i)

4m (cid:88)

Vì gcd(p, (2m + i)(4m + 1 − i)) = 1, ∀i = 1, 2m nên

i=2m+1

≡ 0 (mod p). 1 i

pC j

p+j ≡ 2p +1

p (cid:80) j=0

Bài toán 1.12 (Putnam 1991). Cho p là số nguyên tố lẻ. Chứng minh rằng C j

(mod p2).

p (cid:88)

Lời giải. Sử dụng đẳng thức Vandermonde ta có

pC j

j C p−h p

p+j =

j=0

j≥0

h≥0

(cid:88) (cid:88) C j C h C j p

j≥0

h≥0 (cid:88)

(cid:88) (cid:88) = C p−h p p! h!(p − h)! (p − h)! (p − j)!(j − h)!

h≥0 ≡ 2p + 1

= 2p−h (C h p )

(mod p2).

p với 0 < h < p).

(Do số nguyên tố p là ước của C h

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},

A∈Ek

và (cid:88) (min A + max A). xk =

p ≡ 0 (mod p3).

p−1 (cid:80) k=1

Chứng minh rằng xkC k

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ó

A∈Ek

(cid:88) (cid:88) 2xk = (a1 + ak + p + 1 + p + 1 − ak − a1) = 2(p + 1) = 2(p + 1)C k p ,

hay

xk = (p + 1)C k p .

p−1 (cid:88)

Ta sẽ chứng minh

2 (C k p )

k=1

≡ 0 (mod p3), (p + 1)

p−1 (cid:88)

hay

k=1

≡ 0 (mod p3). (1.65) (C k p )

Thật vậy,

p =

...p ⇒ C k . C k p 1 p (p − 1)! k!(p − k)!

p−1 (cid:88)

k=1

Do đó (cid:19)2 (1.65) ⇔ ≡ 0 (mod p). (cid:18) (p − 1)! k!(p − k)!

Đặt

αk = (p − 1)! k!(p − k)!

(mod p) ⇒ k!αk = (p − 1)(p − 2) . . . (p − k + 1) ≡ (−1)k−1(k − 1)!

(mod p). ⇒ kαk ≡ (−1)k−1

Lại đặt

βk = (p − 1)! k

(mod p), ⇒ kβk = (p − 1)! ≡ −1

(mod p). ⇒ αk ≡ (−1)kβk

Ta có mệnh đề sau:

“∀k ∈ {1; 2; . . . ; p − 1}, ∃ duy nhất j ∈ {1; 2; . . . ; p − 1} sao cho jk ≡ 0 (mod p)”.

p−1 (cid:88)

Khi đó

k(kj)2 ≡ β2

j=1

k=1

j2 ≡ (mod p). (bkk)2j2 ≡ β2 k ≡ (p − 1)(2p − 1)p 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.

p−1 (cid:88)

Cuối cùng ta đi đến

k ≡

k=1

(mod p). α2 β2 k ≡ 0

p−1 (cid:88)

Vậy ta hoàn tất việc chứng minh

p ≡ 0

k=1

(mod p3). xkC k

1008 (cid:88)

Bài toán 1.14 (VMO 2017). Chứng minh rằng

2017 ≡ 0

k=1 504 (cid:88)

a) kC k (mod 20172).

2017 ≡ 3 (cid:0)22016 − 1(cid:1)

k=1

(−1)kC k (mod 20172). b)

1008 (cid:88)

Lời giải. a) Ta có

2017 ≡

k=1

1008 (cid:88)

kC k k.2017! k!(2017 − k)!

k=1 1007 (cid:88)

≡ 2017 2016! (k − 1)!(2017 − k)!

k=0 1007 (cid:88)

≡ 2017 2016! k!(2016 − k)!

2016

k=0 1007 (cid:88)

≡ 2017 C k

2016

k=0

≡ 2017 C k

2016 − C 1008 2016

k=0

(cid:33) (cid:32)2016 (cid:88) ≡ C k 2017 2

≡ (mod 20172). (22016 − C 1008 2016 ) 2017 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ó

2016 − 1 =

C 1008 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

2016 ≡ 1 ≡ 22016

C 1008 (mod 2017).

1008 (cid:88)

Do đó

2017 ≡ 0

k=1

kC k (mod 20172).

b) Ký hiệu ≡ (modm) với x, y, z, t ∈ Z, y (cid:54)= 0, t (cid:54)= 0 và m ∈ Z, m > 1 nếu dạng tối giản z t

chia hết cho m. của phân số x y xt − zy yt

Nhận xét 1.5. Với mọi số nguyên tố p thì

p ≡ (−1)k−1 p C k k

(mod p2).

Thật vậy, ta có

p =

= . . C k p! k!(p − k)! p k (p − k + 1)(p − k + 2) . . . (p − 1) (k − 1)!

Suy ra

p − (−1)k−1 p C k 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ó

p ≡

C k (mod p). 1 p (−1)k−1 k

504 (cid:88)

Khi đó

2017 ≡

k=1

k=1 504 (cid:88)

(−1)kC k (−1)k(−1)k−1 2017 k

k=1

504 (cid:88)

≡ (−1)2k−1 2017 k

k=1

≡ −2017 (mod 20172). 1 k

504 (cid:88)

Bài toán quy về

k=1

−2017 ≡ 3(22016 − 1) (mod 20172), 1 k

504 (cid:88)

hay

k=1

≡ (mod 2017). − 1 k 3(22016 − 1) 2017

Đặt

+ + + · · · + , n ∈ Z+. Sn = 1 1 1 2 1 3 1 n

Khi đó

− + · · · − = S2n − Sn. 1 1 1 2 1 2n

1008 (cid:88)

Ta có

k=1 2016 (cid:88)

1008 (cid:88)

S504 = S1008 − (−1)k−1 k

k=1

− . = S2016 − (−1)k−1 k (−1)k−1 k

1008 (cid:88)

k=1

Do (cid:19) + ≡ 0 (mod 2017). S2016 = (cid:18) 1 k 1 2017 − k

2016 (cid:88)

1008 (cid:88)

nên ta cần chứng minh

k=1

+ ≡ (mod 2017). (−1)k−1 k (−1)k−1 k 3(22016 − 1) 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ề

1008 (cid:88)

2017 +

2017

k=1

(cid:33) (cid:32)2016 (cid:88) C k C k ≡ (mod 2017). 1 2017 3(22016 − 1) 2017

2016 (cid:88)

1008 (cid:88)

2016 (cid:88)

Điều này là hợp lý bởi vì

2017 +

2017 ≡

2017

2017 +

k=1

C k C k C k C k 1 2

2017 − 2

(cid:33) (cid:32)2017 (cid:88) C k ≡ 3 2

k=0 3(22017 − 2) 2

≡ 3(22016 − 1) (mod 2017). ≡

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.

2.1 Các bất đẳng thức cơ bản trong đại số

Trong chương 2, tác giả sử dụng các tài liệu tham khảo [1], [2], [4] và [6].

Đị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 đó

√ ≥ n (2.1) x1x2 · · · xn. x1 + x2 + · · · + xn n

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 √ n . a1a2 · · · an ≥ + + · · · + 1 a1 1 a2 1 an

với k = 1, 2, 3, . . . , n, ta Chứng minh. Sử dụng bất đẳng thức AM-GM đối với bộ số xk = 1 ak 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

1 + u2 u2

2 ≥ 2u1u2, ∀u1, u2 ∈ R.

(2.2)

ta có

√ (2.3) ≥ x1x2, ∀x1, x2 ≥ 0. x1 + x2 2

, từ (2.3) ta nhận được và Thay x1, x2 lần lượt bằng các biến mới x1 + x2 2 x3 + x4 2

≥ x1 + x2 + x3 + x4 4 (cid:114)x1 + x2 2 (cid:113)√ x3 + x4 2 (cid:113)√ ≥ 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

, và giữ nguyên các biến xi khác ta thu được 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

n−1

1 n

(cid:19) 1 , ≥ (x1x2 · · · xn) x1 + x2 + · · · + xn−1 + x1+x2+···+xn−1 n (cid:18) x1 + x2 + · · · + xn−1 n − 1

1 n−1

hay (cid:19) 1 . ≥ (x1x2 · · · xn) x1 + x2 + · · · + xn−1 n − 1 (cid:18) x1 + x2 + · · · + xn−1 n − 1

Rút gọn biểu thức trên ta thu được

√ ≥ n−1 x1x2 · · · xn−1. x1 + x2 + · · · + xn−1 n − 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 đó

1 · · · xpn

1 ≥

(cid:19)p1+p2+···+pn . xp1 1 · xp2 (cid:18) x1p1 + x2p2 + · · · + xnpn p1 + p2 + · · · + pn

Dấu đẳng thức xảy ra khi x1 = x2 = · · · = xn.

2 · · · xβn

1 xβ2 xβ1

n = M.

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

1 β1+β2+···+βn

n (cid:88)

n (cid:89)

k=1

Khi đó (cid:34) (cid:19)βk(cid:35) M . αkxk ≥ (β1 + β2 + · · · + βn) (cid:18) αk βk

Dấu đẳng thức xảy ra khi và chỉ

. xk = βkA αkB

Đị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ó

2 + · · · + b2 n

1 + b2

2 + · · · + a2 n

1 + a2

(cid:1) . (2.4) (cid:1) (cid:0)b2 (a1b1 + a2b2 + · · · + anbn)2 ≤ (cid:0)a2

Đẳ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ó

+ + · · · + ≥ . (2.5) a2 1 b1 a2 2 b2 a2 n bn (a1 + a2 + · · · + an)2 b1 + b2 + · · · + bn

Đẳng thức xảy ra khi = · · · = . = an bn a2 b2 a1 b1

Đị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ó

(2.6) a1b1 + a2b2 + · · · + anbn ≥ (a1, a2, · · · , an) (b1, b2, · · · , bn) . 1 n

+) Nếu b1 ≥ b2 ≥ · · · ≥ bn thì ta có

(2.7) (a1, a2, · · · , an) (b1, b2, · · · , bn) . a1b1 + a2b2 + · · · + anbn ≤ 1 n

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ó

N (cid:88)

dạng

k=0

Mk(x1, x2, · · · , xn), P (x1, x2, · · · , xn) =

trong đó

1 · · · xjn

n , ji ∈ N(i = 1, 2, · · · , n.)

j1+j2+···+jn=k

(cid:88) (2.8) Mk(x1, x2, · · · , xn) = aj1,j2,··· ,jnxj1

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.

n (cid:88)

Trước hết, ta nhắc lại công thức khai triển nhị thức Newton:

nan−kxk.

k=0

(x + a)n = C k

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

n (cid:88)

npn−k j

k=0

xk, C k (x + a1)(x + a2) · · · (x + an) =

trong đó

 p1 =

a1 + a2 + · · · + an n aiaj

p2 2 = (2.9)

(cid:80) 1≤i

  pn n = a1a2 · · · an.

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 aiaj (cid:118) (cid:117) (cid:117) (cid:116) p2 = (2.10) (cid:80) 1≤i

. . .

  a1a2 · · · an. . . . . . . . . . . . . . . . √ pn = n

Đị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)xn−1 + E2(¯a)xn−2 + · · · + En(¯a),

n (cid:88)

trong đó

i=1

1≤i

(cid:88) E1(¯a) = ai, E2(¯a) = 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) = Er(¯a). r!(n − r)! n!

Đị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(λ (cid:54)= 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).

k (k = 1, 2, . . . , n − 1) .

Chứng minh rằng Pk−1Pk+1 ≤ P 2

(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

= 0 cả các tích i số khác nhau, Pr(¯a) = Er(¯a) Vì tất cả các số ai đều dương và t := r!(n − r)! n! x y

và v := = 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, y x nên = 0 và = 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 y x x y 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−1P k + 1 ≤ P 2 k .

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

1 2

1 3

minh bất đẳng thức

n .

2 P

3 > · · · > P

(2.11) P1 > P

Chứng minh. Ta có

P0P2 < P 2 1 ,

(P1P3)2 < P,

. . . . . . . . . . . . .,

(Pr−1Pr+1)r < P 2r r .

Suy ra

1 P 4

2 P 2r r ,

(P0P2)(P1P3)2 · · · (Pr−1Pr+1)r < P 2

1 r+1

1 r >P

r+1 .

hay

r+1 ⇒ Pr

r+1 < Pr

P r

r bằng phương pháp quy nạp

Nhận xét 2.1. Ta dễ dàng chứng minh được Pr−1Pr+1 < P 2

r là các Er, Pr

r, P (cid:48)

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(cid:48)

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 đó

r−1 ⇒ Pr =

r = anE(cid:48)

r +

r−1.

E(cid:48) P (cid:48) anP (cid:48) r n r n

Từ đó suy ra

r ) = A + Ban + Ca2 n.

n2(Pr−1Pr+1 − P 2

trong đó

r−1P (cid:48)

r+1 − (n − r)2P (cid:48)

r−1.

A = (cid:2)(n − r)2 − 1(cid:3) P (cid:48)

r+1.

r−2P (cid:48)

r+1 − 2(r − 1)P (cid:48)

r−2P (cid:48)

r+1 + (n − r − 1)(r − 1)P (cid:48)

r−1P (cid:48)

B = (n − r + 1)(r + 1).P (cid:48)

r−2P (cid:48)

r − r2P (cid:48)

r−1.

C = (r2 − 1)P (cid:48)

Vì các ai không đồng thời bằng nhau nên theo giả thiết ta có

r−1P (cid:48)

r+1 < P (cid:48)

r−2P (cid:48)

r − P (cid:48) r.

P (cid:48)

r−2P (cid:48)

r+1 < P (cid:48)

r−1P (cid:48)

r ⇒ A < −P (cid:48)

r, B < 2P (cid:48)

r−1P (cid:48)

r, C < P (cid:48)

r−1.

P (cid:48)

r) < −(P (cid:48)

r − anP (cid:48)

r−1) ≤ 0.

n2(Pr−1Pr − P (cid:48)

Điều này vẫn đúng khi a1 = a2 = · · · = an. Khi đó an (cid:54)= 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 aiaj (cid:118) (cid:117) (cid:117) (cid:116) p2 = (cid:80) 1≤i

. . .

  . . . . . . . . . . . . . . . √ 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.

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ì

2n)2 .

2n−k ≤ (C n

2n+k.C n

C n

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.

2n−k với 0 ≤ k ≤ n, n, k ∈ N.

2n+k.C n Ta chứng minh dãy (uk) giảm. Ta có

Chứng minh. Đặt uk = C n

2n−k =

2n+k.C n

. , uk = C n (2n + k)! n!(n + k)! (2n − k)! n!(n − k)!

2n+k+1.C n

2n−k =

. . uk+1 = C n (2n + k + 1)! n!(n + k + 1)! (2n − k − 1)! n!(n − k − 1)!

Do đó

. = (2n + k + 1)(n − k) (n + k + 1)(2n − k) ≤ 1 uk+1 uk

Thật vậy

≤ 1 ⇔ (2n + k + 1)(n − k) ≤ (n + k + 1)(2n − k) uk+1 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ì

2n+k.C n

2n−k ≤ (C n

2n)2 .

uk ≤ u0 ⇔ C n

Bài toán 2.4. Chứng minh rằng

n + 2C 3

n + · · · + (n − 1)C n

n > (n − 2)2n−1.

C 2

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.

n (cid:88)

Chứng minh. Ta có

n.xk.

k=0

(1 + x)n = C k (2.12)

n (cid:88)

Đạo hàm hai vế của đẳng thức (2.12), ta có

n.kxk−1.

k=1

n(1 + x)n−1 = C k (2.13)

n (cid:88)

Thay x = 2 vào bất đẳng thức (2.13), ta được

k=1

n2n−1 = (2.14) kC k n.

n (cid:88)

Thay x = 1 vào (2.12)

k=0

2n = (2.15) C k n.

Trừ từng vế (2.14) cho (2.15), ta có

n + · · · + (n − 1)C n n

n + 2C 3

n + C 2

n2n−1 − 2n = −C 0

n = n2n−1 − 2n + 1 = (n − 2)2n−1 + 17(n − 2)2n−1.

n + · · · + (n − 1)C n

n + 2C 3

⇔ C 2

Vậy

n + 2C 3

n + · · · + (n − 1)C n

n > (n − 2)2n−1.

C 2

Bài toán 2.5. Chứng minh rằng

n + 2C 2

n + · · · + nC n n + 3C 3 n n

C 1 < n!, với n ∈ N, 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 để 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ó

n + 2C 2

n + 3C 3

n + · · · + nC n

n = n2n−1.

C 1

n + 2C 2

n + 3C 3 n + · · · + nC n n n

Suy ra C 1 = 2n−1.

Vậy ta phải chứng minh

2n−1 < n!. (2.16)

Thật vậy, ta đi chứng minh (2.16) bằng phương pháp quy nạp.

Khi n = 3, ta có 2n−1 = 22 = 4 < 3!. Vậy (2.16) đúng. Giả sử (2.16)đúng với n = k, k ∈ N, k > 3, nghĩa là, ta có

2k−1 < k!.

Ta chứng minh (2.16) đúng khi n = k + 1, tức là phải chứng minh

2k < (k + 1)!. (2.17)

Ta có (2.16)⇔ 2k < 2k!.

Vì 2 < 3 ≤< k + 1 nên ta có

2k! < (k + 1)k! = (k + 1)! ⇒ 2k < (k + 1)!.

Vậy (2.17) đú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 2.6. Chứng minh rằng

(cid:18) (cid:19)n < 3, n ∈ Z, n > 1. 2 < 1 + 1 n

Nhận xét 2.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 + C 1 n

(cid:19)n (cid:19)2 (cid:19)n (cid:18) = C 0 . 1 + + · · · + C n n + C 2 n 1 n 1 n (cid:18) 1 n (cid:18) 1 n

n = 1; C 1 n

Ta có C 0 = n. = 1. Do đó 1 n 1 n

(cid:19)n (cid:18) > 2. (2.18) 1 + 1 n

Mặt khác, ta có

(cid:19)2 n(n − 1) = = , = C 2 n 1 2 1 2! 1 1.2 (cid:19)3 < < , = C 3 n (cid:18) 1 n (cid:18) 1 n 2!n2 < n(n − 1)(n − 2) 3!n3 1 3! 1 2.3

. . . . . . . . . . . . ., (cid:19)p = < < , C p n n(n − 1) . . . (n − p + 1) p!np 1 p! 1 (p − 1).p (cid:18) 1 n

. . . . . . . . . . . . ., (cid:19)p = < . C n n (cid:18) 1 n n! n!nn < 1 n! 1 (n − 1).n

Do đó, ta có (cid:18) (cid:19)n 1 + < 2 + + + · · · + . (2.19) 1 n 1 1.2 1 2.3 1 (n − 1).n

Nhưng

= − , 1 1.2 1 1 1 2

, = − 1 2 1 3

= − . 1 2.3 . . . . . . . . . . . . . . . ., 1 n − 1 1 (n − 1).n 1 n

Suy ra

(2.20) + + · · · + = 1 − < 1. 1 1.2 1 2.3 1 (n − 1).n 1 n

Từ (2.19) và (2.20), suy ra (cid:18) (cid:19)n (2.21) 1 + < 3. 1 n

2.2.2 Sử dụng các bất đẳng thức cơ bản để chứng minh

Kết hợp (2.18) và (2.21), ta có điều phải chứng minh.

Bài toán 2.7. Cho n + 1 số nguyên đôi một khác nhau x0, x1, . . . xn. Xét các đa thức dạng

(2.22) P (x) = xn + an−1xn−1 + · · · + a1x + a0.

Chứng minh rằng

(2.23) |f (xj)| ≥ max j∈{0,1,...,n} 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.22) dưới dạng

n (cid:88)

n (cid:89)

(cid:34)

k=0

j(cid:54)=i;j=0

P (x) = (cid:35) . P (xk) x − xj xi − xj

So sánh hệ số của xn ta được

n (cid:88)

n (cid:89)

(cid:34) (cid:35)

k=0

j(cid:54)=i;j=0

1 = . P (xk) 1 xi − xj

Nếu (2.23) không đúng thì

n (cid:88)

n (cid:89)

(cid:34) (cid:35)

1 = |P (xk)| 1 xi − xj

j(cid:54)=i;j=0 1 (n − 1)!1!

k=0 n! 2n (cid:0)C 0

(cid:21) + + · · · + ≤ + · · · + (cid:20) 1 n!

n + C 1

n + · · · + C k

n + · · · + C n n

= 1 2n 1 1 (n − k)!k! 0!n! 1 (cid:1) = 2n 2n = 1, (mâu thuẫn).

Vậy ta có điều phải chứng minh.

Nhận xét 2.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.

n (cid:88)

Bài toán 2.8. Cho x1, x2, . . . , xn > 0 và đặt:

i=1

1≤i≤j≤n

1≤i

S1 = xi; S2 = xixj; S3 = xixjxk; . . . ,

và Sn = x1x2 . . . xn là các hàm cơ bản của x1, x2, . . . , xn. Chứng minh rằng:

(cid:115)

≥ (cid:115) ≥ 3 (cid:115) ≥ . . . ≥ n . (2.24) S1 C 1 n S3 C 3 n S2 C 2 n Sn C n n

Nhận xét 2.7. Để chứng minh bất đẳng thức (2.24), 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.24) đúng.

Giả sử bất đẳng thức (2.24) đú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)

= xn − S1xn−1 + S2xn−2 + . . . , (−1)n.Sn.

Vì P (x) có nghiệm x1, x2, . . . , xn nên theo định lí Lagrăng thì:

P (cid:48)(x) = n.xn−1 − (n − 1).S1xn−2 + (n − 2).S2xn−3 − (n − 3).S3xn−4 + . . . + (−1)n−1.Sn−1

có n − 1 nghiệm y1, y2, . . . , yn−1.

S3; . . . ; S1; S2; là các hàm cơ bản của y1, y2, . . . , yn−1. Xen kẽ: x1 < y1 < x2 < y2 < . . . < xn−1 < yn−1 < xn. Suy ra n − 1 n n − 3 n n − 2 n Sn−1 n Theo giả thiết quy nạp, ta có:

(cid:115) (cid:115)

n−1

n−2

n−1

⇒ ≥ (cid:115) ≥ . . . ≥ n−1 . S1 ≥ (cid:115) S2 ≥ . . . ≥ n−1 (n − 1) nC 1 (n − 2) nC 2 Sn−1 C n S1 C 1 n S2 C 2 n Sn−1 nC n−1 n−1

1 x1

Ta lại có

+ 1 x2 ≥ AM-GM) √ n + · · · + 1 xn n 1 x1x2 . . . xn

Suy ra (cid:33) (cid:32) 1 x1 + 1 x2 (x1.x2 . . . xn) + · · · + 1 xn n ≥ n(cid:112)(x1x2 . . . xn)n−1. n

Do đó:

(cid:115) n−1 (cid:115) ≥ n ⇒ đpcm. Sn−1 C n−1 n Sn C n n

Đây là bất đẳng thức xen kẽ của Cauchy. Chẳng hạn với a, b, c, d > 0 :

(cid:114) ≥ a + b + c + d 4 ab + ac + ad + bc + bd + cd 6

(cid:114) ≥ 3 √ ≥ 4 abcd. abc + abd + acd + bcd 4

Chương 3. Các dạng toán cực trị liên

quan đến tổ hợp trong dãy số

3.1 Bất đẳng thức trong dãy số

3.1.1 Dãy sinh bởi hàm số

Trong chương này, tác giả sử dụng các tài liệu tham khảo [1], [4], [5] và [7].

Trong phần này, ta đề cập đến một bài toán liên quan đến dãy số và dãy hàm thường xuất

hiện từ khai triển hàm số đã cho thành chuỗi (không nhất thiết là chuỗi lũy thừa hoặc chuỗi

lượng giác). Tuy nhiên, ta chỉ nêu một vài kỹ thuật chính thống gắn với ước lượng các biểu

thức giải tích và đại số đơn giản.

Từ khai triển hàm số thành chuỗi lũy thừa, ta có một số bất đẳng thức được kiểm chứng

thông qua khảo sát hàm số.

Định lý 3.1 (xem [1]). Với mọi hàm số f (x) có đạo hàm liên tục tới cấp 2n + 1, (n ∈ N∗) và

f (2n+1)(x) (cid:54)= 0 với mọi x ∈ (a, b), đều tồn tại đa thức P2n(x) bậc không quá 2n sao cho hàm số

h(x) := f (x) − P2n(x) đơn điệu trong khoảng (a, b).

Chứng minh. Cách chứng minh dựa vào khai triển Taylor tới cấp 2n + 1 đối với hàm f (x)

tại x0 ∈ (a, b).

(x − x0) + . . . + (x − x0)2n + (x − x0)2n+1, f (x) = f (x0) + f (2n)(x0) (2n)! f (2n+1)(x1) (2n + 1)! f (cid:48)(x0) 1!

với x1 ∈ (a, b).

Từ đây, ta chỉ cần chọn

P2n(x) = f (x0) + (x − x0) + · · · + (x − x0)2n là đủ. f (cid:48)(x0) 1! f (2n)(x0) (2n)!

Thật vậy, do f (2n+1)(x) liên tục và f (2n+1)(x) (cid:54)= 0 với x ∈ (a, b), nên f (2n+1)(x) hoặc luôn dương

hoặc luôn âm trong khoảng (a, b).

Do đó hàm số hn(x) := (x − x0)2n+1 tương ứng, sẽ là đồng biến hoặc nghịch biến f (2n+1)(x1) (2n + 1)! trong khoảng (a, b).

Tương tự ta có kết luận sau đây.

Định lý 3.2 (xem [1]). Với mọi hàm số f (x) có đạo hàm liên tục tới cấp 2n, (n ∈ N∗) và

f (2n)(x) (cid:54)= 0 với mọi x ∈ (a, b), đều tồn tại đa thức P2n−1(x) bậc không quá 2n − 1 sao cho hàm

số h(x) := f (x) − P2n−1(x) lồi hoặc lõm trong khoảng (a, b).

Chứng minh. Cách chứng minh dựa vào công thức khai triển Taylor tới cấp 2n đối với hàm

f (x) tại x0 ∈ (a, b).

f (x) = f (x0) + (x − x0) + . . . + (x − x0)2n−1 + (x − x0)2n+1 f (2n)(x0) (2n − 1)! f (2n)(x1) (2n)! f (cid:48)(x0) 1!

với x1 ∈ (a, b)

Tiếp theo ta chỉ cần chọn

P2n−1(x) = f (x0) + (x − x0) + · · · + (x − x0)2n−1 là đủ. f (cid:48)(x0) 1! f (2n−1)(x0) (2n − 1)!

Thật vậy, do do f (2n)(x) liên tục và f (2n)(x) (cid:54)= 0 với x ∈ (a, b) nên f (2n)(x) hoặc luôn dương

n(x) :=

(x − x0)2n có h(cid:48)(cid:48) (x − x0)2n−2 tương ứng, sẽ Do đó hàm số hn(x) := hoặc luôn âm trong khoảng (a, b). f (2n)(x1) (2n)! f (2n)(x1) (2n − 2)! luôn luôn không âm hoặc luôn luôn không âm trong khoảng (a, b). Do đó h(x) là hàm lồi hoặc

lõm trong khoảng (a, b).

Định lý 3.3 (xem [1]). Với mọi dãy số giảm a1, a2, . . . , an và với mọi hàm lồi f (x) trong

n (cid:80) i=1

(−∞; a1] ta đều có f (ai+1)ai ≤ f (ai)ai+1 trong đó an+1 := a1.

Chứng minh. Ta chứng minh bằng phương pháp quy nạp toán học.

Với n = 2 ta thu được đẳng thức hiển nhiên.

k−1 (cid:88)

Với n = k > 2, ta đặt

i=1

Sk = [f (ak)a1 − f (a1)ak] + [f (ai)ai+1 − f (ai+1)ai].

Ta sẽ chứng minh Sk+1 ≥ Sk ứng với mọi dãy giảm {ai}.

Từ giả thiết f (x) là hàm lồi, ta có:

(cid:19) ≤ f (ak) = f a1 + ak+1 f (a1) + f (ak+1). (cid:18) ak − ak+1 a1 − ak+1 a1 − ak a1 − ak+1 ak − ak+1 a1 − ak+1 a1 − ak a1 − ak+1

Do vậy

(ak+1 − a1)f (ak) + (ak − ak+1)f (a1) + (a1 − ak)f (ak+1) ≥ 0.

Suy ra

Sk+1 − Sk ≥ 0 và vì vậy Sn ≥ Sn−1 ≥ · · · ≥ S2 ≥ 0.

Bài toán 3.1. Cho dãy số {ak} sao cho ứng với mỗi số tự nhiên n cho trước thì đa thức sinh

bởi n phần tử đầu tiên của dãy số Pn(x) = xn + an−1xn−1 + . . . + a1x + a0 có n nghiệm thực

và không âm.

n)2|a0|, (k = 1, . . . , n).

Chứng minh rằng khi đó |an−kak| ≥ (C k

Lời giải. Theo định lí Viete thì

an−k = (−1)k (cid:88) xi1xi2 . . . xik, (k = 1, . . . , n),

n−1 lần).

n số hạng và x1, x2, . . . , xn xuất hiện C k−1

(tổng này có C k

Ck−1 n−1

Ck−1 n−1 i

i=1

Vậy nên  (cid:33) 1 (cid:32) n (cid:89) (cid:88) x |an−k| = xi1xi2 . . . xik ≥    C k n.

n (k = 1,

i=1 (cid:19) n−k

Suy ra (cid:33) k (cid:32) n (cid:89) C k . . . , n). |an−k| ≥ xi

n (cid:89)

, (k = 1, . . . , n). Thay k bởi n − k, ta có |ak| ≥ xi C n−k n (cid:18) n (cid:81) i=1 Từ đó suy ra

nC n−k n

i=1

, (k = 1, . . . , n), |an−kak| ≥ xiC k

hay

n)2, (k = 1, . . . , n).

|an−kak| ≥ |a0|, (C k

n (cid:88)

Bài toán 3.2. Cho đa thức P (x) bậc n và |P (k)(0)| ≤ 1, k = 0, 1, . . . n.. Chứng minh rằng

k=0

xk+1 ≤ e|x| − 1, ∀x ∈ R. (−1)k P (k)(x) (k + 1)! (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

n (cid:88)

Lời giải. Bằng phương pháp quy nạp, ta dễ dàng chứng minh đẳng thức

k=0

xk+1 = xk+1. (−1)k P (k)(x) (k + 1)! P (k)(0) (k + 1)!

n (cid:80) k=0

3.1.2 Ước lượng tích và tổng của một số dãy số

Tiếp theo sử dụng các bất đẳng thức xk+1 ≤ |x|k+1 và |x|k ≤ e|x|. P (k)(0) (k + 1)! 1 (k + 1)! 1 k! (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) Ta suy ra điều phải chứng minh.

Nội dung phần này nhằm trình bày một số bài toán về ước lượng cũng như tính tổng và

tích của một số dãy đặc biệt có liên quan đến các cấp số bằng các phương pháp truyền thống

như quy nạp toán học, sử dụng đạo hàm, tích phân, biến đổi đại số,sử dụng tính chất của số

phức,..

Ta nêu một dạng khác của bất đẳng thức Bernoulli.

Định lý 3.4 (xem [1]). (Bất đẳng thức Bernoulli). Với mọi bộ số thực a1, a2, . . . , an cùng dấu

n (cid:80) k=0

n (cid:81) k=1 Dấu đẳng thức xảy ra khi và chỉ khi a1 = a2 = · · · = an.

và lớn hơn −1, ta đều có (1 + ak) ≥ 1 + ak.

n+1 (cid:81) k=1

n (cid:81) k=1

Chứng minh. Để ý rằng (1 + ak) = (1 + an+1) (1 + ak) và

n (cid:88)

(cid:32) (cid:33)

k=0

1 + ak (1 + an+1) = 1 + ak + an+1 ak.

Vì vậy ta dễ dàng chứng minh bất đẳng thức Bernoulli bằng phương pháp quy nạp thông

thường.

Từ đây ta thu được bất đẳng thức Bernoulli (bậc nguyên) quen biết.

Hệ quả 3.4. Với mọi số a > −1 và số tự nhiên n, , ta đều có (1 + a)n ≥ 1 + na.

Bài toán 3.3. Chứng minh rằng với mọi bộ số dương a1, a2, . . . , an ta đều có

n (cid:89)

k=1

(cid:18) 1 + (cid:19) , (1 + ak) ≤ a2 k ak+1

trong đó an+1 := a1.

k) ≤

k + ak+1).

n (cid:81) k=1

Lời giải. Ta viết lại bất đẳng thức đã cho dưới dạng (a2 (ak + a2

Do các tổng trong các ngoặc đơn đều dương nên bất đẳng thức đã cho tương đương với bất

n (cid:88)

đẳng thức sau bằng cách logarit hóa hai vế.

k + ak) ≤

k + ak+1).

k=1

ln(a2 ln(a2

1 + a2, a2

2 + a3, . . . , a2

n + a1) gần đều hơn bộ số (a2

1 + a1, a2

2 +

Tiếp theo, để ý rằng bộ số (a2

n + an),

a2, . . . , a2

Vì vậy, ứng với hàm lõm f (x) = ln x trong (0; +∞), ta nhận lại được bất đẳng thức Karamata

quen thuộc.

n (cid:89)

n (cid:88)

Bài toán 3.4 (APMO 1989). Cho dãy số dương x1, x2, . . . , xn, Chứng minh rằng

k=1

!, (1 + xk) ≤ Sk n k

trong đó Sn = x1 + x2 + · · · + xn.

Lời giải. Sử dụng bất đẳng thức AM-GM đối với vế trái của bất đẳng thức cần chứng minh,

n (cid:89)

k=1

ta có: (cid:21)n , (1 + xk) ≤ (cid:20) (1 + x1) + (1 + x2) + . . . + (1 + xn) n

n (cid:89)

k=1

hay (cid:19)n (cid:18) . 1 + (1 + xk) ≤ Sn n

Sử dụng khai triển Newton, ta thu được

n (cid:88)

k=0

(cid:18) (cid:19)n (cid:19)k (cid:19)k 1 + = = . C k n Sn n (cid:18) Sn n n(n − 1) . . . (n − k + 1) k! (cid:18) Sn n

Mà

n(n − 1) . . . (n − k + 1) ≤ nk,

n (cid:88)

k=0

nên (cid:19)k ≤ . (Điều phải chứng minh). n(n − 1) . . . (n − k + 1) k! (cid:18) Sn n Sk n k!

2n (cid:88)

n (cid:88)

Bài toán 3.5. Cho dãy số thực dương {an} thỏa mãn điều kiện

i=n+1

i=1

ai ≤ ai, ∀n = 1, 2, . . . 1 n

n (cid:80) i=2

Chứng minh rằng ai ≤ 5a1, ∀n = 2, 3, . . . ..

2n (cid:88)

2n−1 (cid:88)

2n (cid:88)

i=1

i=2n−1+1

Lời giải. (cid:18) (cid:19) 2n−1 (cid:88) 1 + ai = ai+ ai ≤ ai 1 2n−1

2n (cid:88)

i=1

(cid:18) (cid:19) (cid:19) (cid:18) (cid:19) (cid:18) 1 + 1 + . . . .. 1 + 2a1. ai ≤ 1 2n−1 1 2n−2 1 2

n−1

Theo bất đẳng thức giữa trung bình cộng và trung bình nhân, thì

  n − 1 + + + . . . .. + (cid:19) (cid:18) (cid:18) (cid:19) (cid:18) (cid:19) 1 2 1 2n−1 1 + 1 + . . . .. 1 + . ≤     1 2n−1 1 2n−2 1 2 1 4 n − 1

n−1

2n (cid:88)

i=1

Suy ra   n − 1 + .2 (cid:19)n−1 (cid:18) n . ai ≤ 2a1 = 2a1     1 2 n − 1 n − 1

Để ý rằng (cid:19)n−1 (cid:18) n < e < 3, ∀n ∈ N∗. n − 1

2n (cid:88)

Từ đó ta thu được

i=1

ai ≤ 6a1.

n (cid:80) i=1

2k (cid:80) i=1

Với mọi n ≥ 2, ∃k ∈ N∗ để n ≤ 2k và do đó ai ≤ ai ≤ 6a1.

n (cid:80) i=2

3.1.3 Bất đẳng thức trong tập rời rạc

Suy ra ai ≤ 5a1, ∀n = 2, 3, . . .

Trong phần này, ta đề cập tới một số bài toán liên quan đến tính toán và ước lượng trên các

tập số nguyên hoặc hữu tỷ. Do đặc thù của tập số đang xét, nhiều bài toán cực trị (trong tập

rời rạc) cần đến sự điều chỉnh cách giải (tiếp cần phương pháp mới) thì mới giải quyết được.

Chẳng hạn, khi ta có hai số tự nhiên có tổng bằng 7, thì tích của nó lớn nhất không thể xảy ra

khi hai số nguyên đó bằng nhau được. Ta cần đến khái niệm và thuật toán điều chỉnh gần đều

để áp dụng.

Bài toán 3.6. Cho số nguyên dương n lớn hơn 1. Chứng minh rằng

n (cid:88)

k=0

(cid:18) (cid:19)n 1 + !. < 1 n 1 k

Lời giải. Nhận xét rằng

n + C 1 n

(cid:18) (cid:19)n (cid:19) (cid:19) (cid:19) 1 + = C 0 , + C 2 n + · · · + C n n 1 n (cid:18) 1 n (cid:18) 1 n2 (cid:18) 1 nn

n (cid:80) k=0

(cid:19) . Dấu đẳng thức xảy ra khi và chỉ khi k = 0 hoặc k = 1. = và C k n (cid:18) 1 nk 1 k! n! (n − k)!nk ≤ 1 k! (cid:18) (cid:19)n Từ đây, ta thu được bất đẳng thức 1 + < 1 n 1 k!

Bài toán 3.7. Chứng minh bất đẳng thức

n (cid:88)

k=1

(cid:18) (cid:19) (cid:18) (cid:18) (cid:19) (cid:18) 1 − 1 − < 1 − 1 + 1 2n + 1 2 2n + 1 (cid:19) π2 6 1 k2 < 1 2n + 1 1 2n + 1 (cid:19) π2 6

Lời giải. Với 0 < α < , ta có bất đẳng thức sin α < α < tan α, hay π 2

cot α < < . (3.1) 1 α 1 sin α

2n+1

Dễ thấy các số cot2 , cot2 , cot2 là n nghiệm của đa thức π 2n + 1 2π 2n + 1 3π 2n + 1 , . . . , cot2 nπ 2n + 1 bậc n sau

2n+1

xn − xn−1 + xn−2 − · · · + (−1)n−1 C 2n−1 x + . C 3 C 1 C 5 C 1 C 1 (−1)n C 1

2n+1

Do đó, tổng các nghiệm này là

2n+1

+ cot2 + cot2 = = . cot2 π 2n + 1 2π 2n + 1 3π 2n + 1 + · · · + cot2 nπ 2n + 1 C 3 C 1 n(2n − 1) 3

n (cid:88)

Vậy

k=1

= . (3.2) cot2 kπ 2n + 1 n(2n − 1) 3

Từ đó suy ra

2n+1

+ + · · · + 1 sin2 π 1 sin2 2π 2n+1 1 sin2 nπ 2n+1

= cot2 + 1 + cot2 + 1 + 1 + · · · + cot2 nπ 2n + 1

= . + n = π 2n + 1 n(2n − 1) 3 2π 2n + 1 2n(n + 1) 3

Vậy nên 1 1 . (3.3) + + · · · + = 2n(n + 1) 3 sin2 sin2 π 2n + 1 1 sin2 nπ 2n + 1 2π 2n + 1

Từ (3.1), (3.2) và (3.3) ta có

n (cid:88)

k=1

(cid:19)2 < = cot2 kπ < = . n(2n − 1) 3 2n + 1 (cid:18) 2n + 1 kπ 2n(n + 1) 3 1 sin2 kπ 2n + 1

(cid:19)2 Chia tất cả các số hạng của bất đẳng thức cho , ta được (cid:18) 2n + 1 π

n (cid:88)

k=1

(cid:18) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) 1 − 1 − 1 − < 1 + . 1 2n + 1 2 2n + 1 (cid:19) π2 6 1 k2 < 1 2n + 1 1 2n + 1 (cid:19) π2 6

Nhận xét 3.1. Từ bất đẳng thức trên, cho n → ∞, ta thu được

(cid:18) (cid:19) (cid:18) 1 − 1 − → , 1 2n + 1 2 2n + 1 (cid:19) π2 6 π2 6

và (cid:18) (cid:19) (cid:18) 1 − 1 + → . 1 2n + 1 1 2n + 1 (cid:19) π2 6 π2 6

∞ (cid:88)

Vậy

k=1

. 1 k2 = π2 6

Bài toán 3.8 (APMO 1990). Cho dãy số dương a1, a2, . . . , an. Gọi Sk tổng tất cả các tích của

k số lấy từ dãy đã cho. Chứng minh rằng

(cid:1)2 SkSn−k ≥ (cid:0)C k a1a2 . . . an, k = 1, 2, . . . , n − 1.

Lời giải. Sử dụng bất đẳng thức AG đối với bộ số C k n

1≤j1≤···≤jk≤n

(cid:32) (cid:33) 1 Ck n (cid:88) (cid:89) . Sk = aj1aj2 . . . ajk aj1aj2 . . . ajk ≥ C k n

1≤j1≤···≤jk≤n

Do trong tích (cid:89) aj1aj2 . . . ajk.

n−1 lần nên

mỗi số ai xuất hiện C k−1

k n .

1≤j1≤···≤jk≤n

(cid:32) (cid:33) 1 Ck n (cid:89) = (a1a2 . . . an) aj1aj2 . . . ajk

Suy ra

k n .

n(a1a2 . . . an)

1≤j1≤···≤jk≤n

(cid:88) Sk = aj1aj2 . . . ajk ≥ C k

n−k n .

Tiếp theo, đổi vai trò k bởi n − k ta thu được

Sn−k ≥ C n−k (a1a2 . . . an)

Do đó

3.2 Một số bài toán cực trị liên quan đến tổ hợp trong

dãy số

(cid:1)2 SkSn−k ≥ (cid:0)C k a1a2 . . . an, (điều phải chứng minh).

Bài toán 3.9. Cho đa thức

P (x) = (1 + 2x)n = a0 + a1x + a2x2 + · · · + anxn,

+ biết a0 + a1 2 a2 22 + · · · + an 2n = 4096. 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 3.2. Để 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ó (cid:19) f + = a0 + (cid:18) 1 2 a1 2 a2 22 + · · · + an 2n

⇔ 2n = 4096 ⇔ 2n = 212 ⇔ n = 12.

12 (cid:88)

Khi đó, ta có

n(2x)k =

12xk.

k=0

P (x) = C k C k

Suy ra

122k, k = 0, 1, 2, . . . , n.

ak = C k

Số hạng ak lớn nhất khi và chỉ khi

  ak ≥ ak+1

 ak ≥ ak−1

12 2k+1 12 2k−1

122k ≥ C k+1 122k ≥ C k−1

2k ≥ 2k+1 C k     ⇔ ⇔ C k  2k ≥ 2k−1  12! k!(12 − k)! 12! k!(12 − k)! 12! (k + 1)!(11 − k)! 12! (k − 1)!(13 − k)!

k ≥     2 k + 1 ⇔ ⇔ k ≤ .   ≥ 1 13 − k 22 3 26 3

12 = 126720 là số hạng lớn nhất của dãy (ak)

1 12 − k 2 ≥ k Vì k ∈ Z nên k = 8. Vậy a8 = 28C 8

(cid:21) Lời giải. Do C n nên ta chỉ cần xét dãy {C n Bài toán 3.10. Cho số nguyên dương N . Tìm giá trị lớn nhất trong dãy số C n N (n = 0, 1, . . . , N ). (cid:20)N . Mặt khác thì 2

N } = C p

N < C n

N , p =

N , nên max 0≤n≤N

N = C N −n (cid:21) (cid:20)N 2

N } với n = 0, 1, . . . , (cid:21) (cid:20)N 2

, ta có C n−1 {C n . với n = 0, 1, . . . ,

Bài toán 3.11 (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, . . . , kn 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

(3.4) A = . 1 a1a2 . . . an

+) Với n = 1, (3.4) đúng

+) Giả sử (3.4) đúng đến n − 1

Với mỗi n số nguyên dương a1, a2, . . . , an

Trong A, đặt làm thừa số chung, ta được 1 a1 + a2 + · · · + an

A = , 1 a1 + a2 + · · · + an

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}

Do đó theo giả thiết quy nạp thì B = . 1 a2a3 . . . an Tiếp tục như thế với a2, a3, . . . , an ta được

B = + + · · · + = . 1 a2a3 . . . an 1 a1a3 . . . an 1 a1a2 . . . an−1 a1 + a2 · · · + an a1a2 . . . an

Từ đó suy ra A = . 1 a1a2 . . . an Vậy theo nguyên lí quy nạp (3.4) đúng với mọi n ≥ 1.

2 = 1 + a2 thì tổng các số ai không đổi, còn tích

+) Nếu a1 = 1, loại a1 = 1, thế a2 = 1 bởi a(cid:48)

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

3.3 Một số bài toán cực trị liên quan qua các đề thi

Olympic

Do 2009 = 3.669 + 2 nên maxP = 2.3669. Suy ra minA = 1 2.3669 .

2011 (cid:88)

Bài toán 3.12 (Olympic 30/4/2011). Cho hàm số

2011xk(1 − x)2011−k.

k=0

F (x) = (k − 2011x)2C k

Tìm giá trị nhỏ nhất của hàm số F (x) trên [0; 1]

Nhận xét 3.3. Để 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).

n (cid:88)

Lời giải.

nxk(1 − x)n−k

k=0

n (cid:88)

A = (k − nx)2C k

nxk(1 − x)n−k +

nxk(1 − x)n−k − 2nx

nxk(1 − x)n−k

k=0

= (nx)2 C k k2C k kC k

n (cid:88)

Xét

nxk(1 − x)n−k

k=0 n (cid:88)

n (cid:88)

kC k A1 =

n−1xk(1 − x)n−k = nx

n−1xk−1(1 − x)n−k

k=1

= n C k−1 C k−1

n−k

n (cid:88)

= nx[x + (1 − x)]n−1 = nx

nxk(1 − x)

k=0 n (cid:88)

k2C k A2 =

n−1xk(1 − x)n−k

n (cid:88)

k=1 n (cid:88)

kC k−1 = n

n−1xk(1 − x)n−k

n−1xk−1(1 − x)n−k + n

k=1

n (cid:88)

(k − 1)C k−1 C k−1 = nx

n−2xk−2(1 − x)n−k = nx + n(n − 1)x2.

k=2

n−k

n (cid:88)

= nx + n(n − 1)x2 C k−2

nxk(1 − x)

k=0

C k = [x + (1 − x)]n = 1. A3 =

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ó

(cid:21) . Dấu đẳng thức xảy ra khi x = . F (x) ≤ 2011 (cid:20) x + (1 − x) 2 1 2

F (x) = ⇔ x = . Vậy max [0;1] 2011 4 1 2

Nhận xét 3.4. 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ừ

n (cid:80) k=0

Bài toán 3.13 (Canada 1997). Hãy viết tổng dưới dạng , trong (−1)kC k n k3 + 9k2 + 26k + 24 p(n) q(n)

đó p(n), q(n) là các đa thức với hệ số nguyên, ta có thể xây dựng được bài toán cực trị liên

quan đến tổ hợp là bài toán sau:

n (cid:88)

Bài toán 3.14. Tìm giá trị nhỏ nhất của biểu thức

k=0

f (n) = + . (−1)kC k n k3 + 9k2 + 26k + 24 2n4 − 10n3 − 64n2 + 272n + 959 2(n + 3)(n + 4)

Nhận xét 3.5. Để giải bài toán này, trước hết ta phải sử dụng công thức tính số tổ hợp, 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 biểu thức f (n).

n (cid:88)

Lời giải. Đặt

k=0

S(n) = . (−1)kC k n k3 + 9k2 + 26k + 24

Ta có

k3 + 9k2 + 26k + 24 = (k + 2)(k + 3)(k + 4),

n (cid:88)

nên

S(n) =

k=0 n (cid:88)

k=0

(cid:19) (cid:18) (cid:19) . = (−1)k.n! k!.(n − k)!(k + 2)(k + 3)(k + 4) (cid:18) (−1)k.(n + 4)! (k + 4)!.(n − k)! k + 1 (n + 1)(n + 2)(n + 3)(n + 4)

n (cid:88)

Đặt

n+4(k + 1)(−1)k.

k=0

C k+4 T (n) = (n + 1)(n + 2)(n + 3)(n + 4)S(n) =

n (cid:88)

Ta có

n−1 = 0,

n = (x − 1)n = 0 ⇒ −n

j=0

i=0

(−1)iC i (−1)jC j

n (cid:88)

và

n.i =

i=0

i=1 n (cid:88)

n (cid:88)

(−1)iC i (−1)i i.n! i!(n − i)! + (−1)0 0.n! 0!n!

i=1

n (cid:88)

= = (−1)i (−1)inC i−1 n−1 n! (i − 1)!(n − i)!

n−1 = −n

n−1 = 0.

i=1

= n (−1)iC i−1 (−1)i−1nC i−1

n (cid:88)

Do đó

n+4(k + 1)

k=0

T (n) = (−1)kC k+4

n (cid:88)

n+4(k + 1)

k=0 n (cid:88)

= (−1)k+4C k+4

n+4(k + 1) − (−3 + 2(n + 4) − C 2

n+4)

k=−4

= (−1)k+4C k+4

n+4 (cid:88)

n+4(j − 3) −

j=0

n+4 (cid:88)

(cid:19) (cid:18) = (−1)jC j 2n + 8 − 3 − (n + 4)(n + 3) 2

n+4j − 3

n+4 −

j=0

(4n + 10 − n2 − 7n − 12) = (−1)jC j (−1)jC j 1 2

= 0 + 0 + (n2 + 3n + 2) = (n + 1)(n + 2). 1 2 1 2

Suy ra

S(n) = = . T (n) (n + 1)(n + 2)(n + 3)(n + 4) (n + 1)(n + 2) (n + 1)(n + 2)(n + 3)(n + 4)

Vậy

. S(n) = 1 2(n + 3)(n + 4)

Do đó

f (n) = + 2n4 − 10n3 − 64n2 + 272n + 959 2(n + 3)(n + 4)

= 1 2(n + 3)(n + 4) 2n4 − 10n3 − 64n2 + 272n + 960 2(n + 3)(n + 4) 2(n + 3)(n + 4)(n2 − 12n + 40) 2(n + 3)(n + 4)

= n2 − 12n + 40.

Ta có

n2 − 12n + 40 = (n − 6)2 + 4 ≥ 4, ∀n ∈ N. Dấu đẳng thức xảy ra khi n = 6

Vậy f (n) đạt giá trị nhỏ nhất bằng 4 khi n = 6.

Bài toán 3.15. Trong một cuộc thi có 11 thí sinh tham gia giải 9 bài toán. Hai thí sinh bất

kì giải chung với nhau không quá 1 bài. Tìm k lớn nhất để mọi bài có ít nhất k thí sinh giải

được.

Lời giải. Gọi Hi là thí sinh thứ i và tập các bài toán là {b1, b2, . . . , b9}

Theo đề bài ta có |Hi ∩ Hj| ≤ 1, ∀i (cid:54)= j.

Đặt ni là số thí sinh giải được bài bi Ta đi đếm bộ (bi, Hj, Hi), trong đó bi ∈ Hj ∩ Hl. Ta có số bộ này chính bằng (cid:80) |Hi ∩ Hj|

9 (cid:80) i=1

Mặt khác, số bộ này lại bằng . Do đó ta có C 2 ni

9 (cid:88)

i=1

(cid:88) . |Hi ∩ Hj| = C 2 ni

9 (cid:88)

Suy ra

i − ni

11 = 110 ⇒ 9(k2 − k) ≤ 110 ⇒ k ≤ 4.

i=1

(cid:88) (cid:0)n2 (cid:1) ≤ 2 |Hi ∩ Hj| ≤ 2.C 2

i − di) ≥ 8.12 + 20 = 116 (vô lí).

9 (cid:80) i=1

(d2 Với k = 4, giả sử tồn tại ni ≥ 5, suy ra

11 (cid:88)

Suy ra

i=1

|Hi| ≥ 4 ⇒ |Hi| ≥ 36 + |H1| + |H2| > 36.

11 − 1.

(cid:88) ni = 4, ∀i = 1, 9 ⇒ |Hi ∩ Hj| = 54 = C 2

Do đó tồn tại (i, j) sao cho Hi ∩ Hj = ∅.

(cid:3) + 1 = 4 tập Ht, t (cid:54)= i.

Giả sử H1 ∩ H2 = ∅ và |Hi ∩ Hj| = 1, ∀t ∈ {1, 2, . . . , 11} \ {i} . Nên tồn tại một phần tử của Hi thuộc ít nhất (cid:2) 10 Suy ra sự tồn tại một phần tử thuộc nhiều hơn 5 tập Hj, vô lí.

Do đó k ≤ 3. Với k = 3 ta chỉ ra như sau:

Quy ước:

Số 1 là thí sinh giải được bài đó.

Số 0 là thí sinh không giải được bài đó.

b1 1 b2 0 b3 0 b4 1 b5 0 b6 0 b7 1 b8 0 b9 0

1 0 0 0 1 0 0 0 1

0 1 1 0 0 1 0 1 0

0 1 0 1 1 0 0 0 0

0 0 0 1 0 0 0 1 1

0 0 1 0 0 0 1 0 1

0 0 0 0 1 1 0 0 0

1 1 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0

0 0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 1 0 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11

Vậy k lớn nhất thỏa mãn yêu cầu bài toán bằng 3.

KẾT LUẬN

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” đã giải quyết được những vấn đề sau:

1. Luận văn đã trình bày chi tiết một số dạng toán liên quan đến tổ hợp, phát biểu

và chứng minh các tính chất cơ bản trong tổ hợp và xét các áp dụng liên quan trong

đại số, số học và hình học.

2. Trình bày các dạng toán về bất đẳng thức và cực trị liên quan đến tổ hợp.

3. Cuối cùng, luận văn trình bày các đề toán thi học sinh giỏi trong nước, Olympic

khu vực và quốc tế liên quan đến tổ hợp. . .

57 TÀI LIỆU THAM KHẢO

A. Tiếng Việt

[1] Nguyễn Văn Mậu (2006), Bất đẳng thức, định lí và áp dụng, NXB Giáo dục.

[2] Nguyễn Văn Mậu (2007), Đa thức đại số và phân thức hữu tỷ, NXB Giáo dục.

[3] Nguyễn Văn Mậu (2010), Số phức và áp dụng, NXB Giáo dục.

[4] Lê Hoành Phò, Nguyễn Văn Nho, Nguyễn Tài Chung (2013), Chuyên khảo đa thức, NXB

Đại học Quốc gia Hà Nội.

[5] Ban tổ chức kì thi Tổng tập đề thi Olympic 30 tháng 4 Toán học 10 (2002-2012), NXB

Đại học Sư phạm.

[6] Hà Văn Chương (2002), 342 bài toán giải tích tổ hợp, NXB Giáo dục.

[7] Tủ sách Toán học tuổi trẻ, Các bài thi Olympic Toán trung học phổ thông Việt Nam

(1990-2006), NXB Giáo dục.

B. Tiếng Anh

[8] Luis Comlet (1974), Advanced combinatorics, D.Reidel Pub. Com.

[9] Titu Andreescu, Zuming Feng (2002), 102 combinatorial problems from the training of the

USA IMO team.

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

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------

BÙI THỊ LỢI

BẤT ĐẲNG THỨC VÀ CÁC BÀI TOÁN

CỰC TRỊ TRONG ĐẠI SỐ TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2017

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------

BÙI THỊ LỢI

BẤT ĐẲNG THỨC VÀ CÁC BÀI TOÁN

CỰC TRỊ TRONG ĐẠI SỐ TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN 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. NGUYỄN VĂN MẬU

THÁI NGUYÊN - 2017

Chương 1. Nhị thức Newton và một số

đẳng thức tổ hợp liên quan

Chương 2. Bất đẳng thức trong tính

toán tổ hợp

Chương 3. Các dạng toán cực trị liên

quan đến tổ hợp trong dãy số

Có thể bạn quan tâm

Luận văn Thạc sĩ: Chế tạo và nghiên cứu tính chất điện, từ của vật liệu multiferroic Ba₀.₇Ca₀.₃TiO₃/ NiFe₂O₄

Luận văn Thạc sĩ: Nghiên cứu vật liệu biến hóa dạng chuỗi một chiều chế tạo từ kim loại đồng trên đế FR-4 hoạt động tại tần số MHz ứng dụng trong truyền năng lượng không dây

Luận văn Thạc sĩ: Đánh giá khả năng tác động tới môi trường biển của việc xả nước thải từ sự cố nhà máy điện hạt nhân Fukushima sử dụng công cụ ERICA

Luận văn Thạc sĩ: Xây dựng mô hình đầu dò nơtron và gamma sử dụng nhấp nháy EJ-276 ghép nối với mảng nhân quang silicon

Luận văn Thạc sĩ: Đánh giá khả năng ảnh hưởng của bức xạ ion hóa đến sức khỏe cư dân khu vực mỏ đất hiếm Đông Pao, xã Bản Hon, huyện Tam Đường, tỉnh Lai Châu

Luận văn Thạc sĩ: Sử dụng phương pháp nhiễu xạ neutron khảo sát cấu trúc tinh thể và pha trật tự từ trong vật liệu Pr2FeCrO6

Luận văn Thạc sĩ: Nghiên cứu phân lập, xác định cấu trúc và hoạt tính ức chế NO của các hợp chất thứ cấp từ chủng vi nấm biển Aspergillus sp. CL251

Luận văn Thạc sĩ: Phân tích một số hợp chất bisphenol thôi nhiễm từ bao bì nhựa lên một số mẫu thực phẩm nền tinh bột

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá hoạt tính kháng khuẩn, kháng nấm của loài hoa mộc (Osmanthus fragrans (Thunb.) Lour.) ở Việt Nam

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá tác dụng kháng viêm của loài côi Turpinia montana (Blume) Kurz

Luận văn Thạc sĩ: Tổng hợp và đặc trưng tính chất vật liệu composite có cấu trúc nano chitosan–cyclodextrin/TiO₂–Ag

Luận văn Thạc sĩ: Nghiên cứu chế tạo và khảo sát một số tính chất của màng phủ trên cơ sở nhựa epoxy gốc nước và khung cơ kim - ZIF

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất napthoquinone chứa nguyên tố flo bằng phản ứng đa thành phần

Luận văn Thạc sĩ: Nghiên cứu điều chế vật liệu Bioglass và tổ hợp lai với polymer ALG-F127 định hướng ứng dụng trong điều trị nội nha

Luận văn Thạc sĩ: Khảo sát thành phần hóa học và hoạt tính ức chế enzyme α-glucosidase trên một số hợp chất phân lập từ thịt quả bình bát nước (Annona glabra L.).

Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất của benzazole

Luận văn Thạc sĩ: Nghiên cứu chiết tách lignin từ vỏ sầu riêng Ri6 (Durio zibethinus Murr.) và tổng hợp vật liệu biocomposite định hướng ứng dụng trong bảo quản sau thu hoạch

Luận văn Thạc sĩ: Nghiên cứu tổng hợp hạt nano bạc phủ acid hyaluronic mang doxorubicin định hướng ứng dụng trong điều trị ung thư

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và hoạt tính kháng viêm của loài rau dừa nước (Ludwigia adscendens)

Tài liêu mới

Tài liệu tham khảo Tiếng Anh lớp 8

Đề ôn tập Vật lí lớp 12

Tài liệu chuyên đề: Cực trị hàm số

Câu hỏi trắc nghiệm ôn tập môn Toán lớp 11

Tài liệu Tổng hợp lý thuyết Toán lớp 8

Tài liệu Lý thuyết và bài tập Tiếng Anh lớp 6

Tài liệu Bài tập cơ bản và nâng cao Đại số 7 (Dành cho giáo viên, phụ huynh)

Tài liệu bồi dưỡng học sinh giỏi môn Lịch sử lớp 9 (Sách Kết nối tri thức)

Tài liệu Hình học 9 - Chương 5: Đường tròn - Tự luận có lời giải (Sách Kết nối trí thức với cuộc sống)

Phiếu bài tập cuối tuần Tiếng Việt 1 - Tuần 1 đến tuần 5

Phiếu bài tập cuối tuần Tiếng Việt 1 - Tuần 2 - Đề 4

Phiếu bài tập cuối tuần Tiếng Việt 1 - Tuần 2 - Đề 3

Phiếu bài tập cuối tuần Tiếng Việt 1 - Tuần 2 - Đề 2

Phiếu bài tập cuối tuần Tiếng Việt 1 - Tuần 2 - Đề 1

Phiếu bài tập cuối tuần Tiếng Việt 1 - Tuần 1 - Đề 3

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098