Luận văn: Phương pháp quy nạp trong các bài toán tổ hợp

Lời cảm ơn

Tôi xin bày tỏ lòng biết ơn sâu sắc đến GS.TSKH Hà Huy Khoái, đã

định hướng chọn đề tài và nhiệt tình hướng dẫn để tôi có thể hoàn thành

luận văn này.

Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng Sau đại học, các

thầy cô giáo giảng dạy chuyên ngành Phương pháp Toán sơ cấp, trường

Đại học Thăng Long đã giúp đỡ tôi trong suốt quá trình học tập tại trường.

Nhân dịp này tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè đã cổ vũ,

động viên để tôi hoàn thành luận văn này.

Hà Nội, tháng 4 năm 2016

Tác giả

Lê Thị Thọ

Lời cam đoan

Tôi xin cam đoan, dưới sự chỉ bảo và hướng dẫn của GS.TSKH Hà Huy

Khoái, luận văn chuyên ngành Toán Đại số với đề tài:”Phương pháp quy

nạp trong các bài toán tổ hợp” được hoàn thành bởi sự nhận thức và

tìm hiểu của bản thân tác giả.

Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa

những kết quả của các nhà khoa học với sự trân trọng và biết ơn.

Hà Nội, tháng 4 năm 2016

Tác giả

Lê Thị Thọ

Mục lục

Mở đầu 4

7 1 PHƯƠNG PHÁP QUY NẠP TOÁN HỌC

7 1.1 Phương pháp quy nạp toán học . . . . . . . . . . . . . . .

1.2 So sánh và đánh giá . . . . . . . . . . . . . . . . . . . . . . 12

1.3 Chứng minh các đồng nhất thức và bất đẳng thức nhờ quy

nạp toán học . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4 Bài toán của Fibonacci . . . . . . . . . . . . . . . . . . . . 16

1.5 Một số đồng nhất thức . . . . . . . . . . . . . . . . . . . . 19

2 QUY NẠP VÀ CÁC BÀI TOÁN TỔ HỢP 22

2.1 Số tập con . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 Dãy số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3 Số tập con có thứ tự . . . . . . . . . . . . . . . . . . . . . 25

2.4 Số tập con có kích thước cho trước . . . . . . . . . . . . . . 26

2.5 Bao hàm - Loại trừ . . . . . . . . . . . . . . . . . . . . . . 29

2.6 Một số bài toán tổ hợp . . . . . . . . . . . . . . . . . . . . 32

2.6.1 Nguyên lý chuồng chim bồ câu . . . . . . . . . . . . 32

2.6.2 Nghịch lý anh em sinh đôi và hàm Logarit . . . . . . 35

2.6.3 Cách chia quà . . . . . . . . . . . . . . . . . . . . . 40

2.6.4 Giải một số bài toán tổ hợp . . . . . . . . . . . . . . 41

2

2.7 Hệ số nhị thức và tam giác Pascal . . . . . . . . . . . . . . 48

2.7.1 Tam giác Pascal . . . . . . . . . . . . . . . . . . . . 50

2.7.2 Công thức trong tam giác Pascal . . . . . . . . . . . 51

Kết luận 55

3

Tài liệu tham khảo 56

MỞ ĐẦU

1. Lý do chọn đề tài

Học sinh ở các trường THPT hầu như chưa được học cơ bản về tổ hợp.

Không chỉ quan trọng đối với kỳ thi học sinh giỏi, mà tổ hợp là một phần

không thể thiếu cho những ai muốn tiếp tục học tập, nghiên cứu và làm

việc có hiệu quả trong những ngành như Toán học, Tin học, Kỹ thuật, hay

đơn giản chỉ là để trau dồi tư duy logic, điều mà ai cũng cần trong cuộc

sống. Trong những cố gắng nâng cao trình độ về tổ hợp cho học sinh, một

việc làm quan trọng là cung cấp cho giáo viên và học sinh những tài liệu

tốt về môn này. Yêu cầu đặt ra là tài liệu đó phải trình bầy những kiến

thức cơ bản nhất theo cách tự nhiên, bản chất và dễ hiểu nhất, để học

sinh cảm thấy tổ hợp không quá khó. Khi có những kiến thức cơ bản và

chắc chắn, học sinh sẽ tiếp cận bài toán khó một cách dễ dàng.

Trong tư duy khoa học, phân tích không phải là phương pháp duy nhất.

Ngay trong toán học tính toán, không phải khi nào cũng chứng minh được

chặt chẽ quá trình tính toán hội tụ, mà việc áp dụng dựa trên sự kiện là

chúng thường cho các kết quả phù hợp với thực tế. Những kết quả từ quan

sát và kinh nghiệm còn được sử dụng rộng rãi hơn trong những ngành

khoa học như Vật lý, Hóa học, Sinh học. Trong những ngành đó, bên cạnh

phân tích, người ta sử dụng một cách rộng rãi những lập luận quy nạp.

Chữ quy nạp có nghĩa là những kết luận được rút ra trên cơ sở quan sát,

4

kinh nghiệm, tức là nhận thức bằng con đường đi từ cái riêng rẽ đến cái

tổng quát.

Vai trò của kết luận quy nạp là rất lớn. Nó cho những xuất phát điểm

để từ đó, bằng con đường phân tích người ta rút ra những lý thuyết sâu

hơn.

Vì những lý do trên tôi chọn đề tài: Phương pháp quy nạp trong

các bài toán tổ hợp. Khi nghiên cứu và thực hiện đề tài bản thân tôi sẽ

hiểu rõ hơn về quy nạp toán học và các bài toán tổ hợp. Từ đó có thêm

kiến thức để hướng dẫn học sinh học tập tốt môn học này.

Chúng tôi không có ý định sưu tầm những bài toán khó, mà gần như

ngược lại, phân tích ý tưởng quy nạp dựa trên những bài toán tương đối

dễ. Mục tiêu là giúp học sinh hiểu được rằng, quy nạp là phương pháp

phát hiện ra các mệnh đề toán học chưa biết, chứ không đơn thuần như

quan điểm rộng rãi hiện nay là quy nạp chỉ dùng để chứng minh mệnh đề

cho trước, bằng cách chứng minh "đã đúng đến k thì đúng đến k + 1”.

2. Mục đích nghiên cứu

Đề tài nhằm nghiên cứu phương pháp chứng minh quy nạp toán học và

các bài toán tổ hợp.

3. Nhiệm vụ nghiên cứu

Nghiên cứu các bài toán tổ hợp trong chương trình THPT và một số bài

toán nâng cao.

4. Đối tượng và phạm vi nghiên cứu

Một số bài toán chứng minh bằng quy nạp toán học, các bài toán tổ

5

hợp.

5. Phương pháp nghiên cứu

Sử dụng các kiến thức toán Đại số. Tổng hợp, phân tích

6. Dự kiến đóng góp mới

Trình bầy một cách khoa học và dễ hiểu các nội dung liên quan đến đề

6

tài để đồng nghiệp và học sinh có thể tham khảo.

Chương 1

PHƯƠNG PHÁP QUY NẠP TOÁN HỌC

1.1 Phương pháp quy nạp toán học

Bây giờ ta tìm hiểu các công cụ quan trọng nhất trong toán rời rạc. Ta

bắt đầu bằng câu hỏi:

Cộng n số lẻ đầu tiên lại ta thu được số bằng bao nhiêu?

Có lẽ cách tốt nhất là ta thử tìm câu trả lời bằng thực nghiệm. Thử với

các giá trị n nhỏ, thì thứ ta tìm được là:

1 = 1

1 + 3 = 4

1 + 3 + 5 = 9

1 + 3 + 5 + 7 = 16

1 + 3 + 5 + 7 + 9 = 25

1 + 3 + 5 + 7 + 9 + 11 = 36

1 + 3 + 5 + 7 + 9 + 11 + 13 = 49

7

1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64

1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81

1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 = 100

Dễ dàng nhận thấy ta thu được các số chính phương; thật ra, dường như

từ các ví dụ trên ta có tổng của n số lẻ đầu tiên là n2. Ta đã thấy điều

này với 10 giá trị n đầu tiên; liệu ta có chắc chắn điều này đúng với mọi

giá trị? Vâng, tôi muốn nói rằng chúng ta có thể chắc chắn, nhưng trong

toán học thì tin rằng "chắc chắn đúng" chưa đủ. Làm thế nào chúng ta có

thể chứng minh khẳng định trên?

Xét tổng với số n tổng quát. Số lẻ thứ n là 2n − 1, nên ta thử chứng

minh rằng

(1.1)

1 + 3 + · · · + (2n − 3) + (2n − 1) = n2.

Nếu ta tách số hạng cuối cùng, ta còn lại tổng của (n − 1) số lẻ đầu tiên

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

Bây giờ, tổng trong dấu ngặc lớn là (n − 1)2, vì nó là tổng của (n − 1) số

lẻ đầu tiên. Do đó toàn bộ tổng bằng

(1.2)

(n − 1)2 + (2n − 1) = (n2 − 2n + 1) + (2n − 1) = n2,

chính là điều ta cần chứng mình.

Điều mà ta đã dùng là khẳng định về tổng của n − 1 số lẻ đầu tiên; và

ta biện luận (trong (1.2)) rằng điều này chứng minh khẳng định về tổng

của n số lẻ đầu tiên. Nói cách khác, điều mà chúng ta thực sự làm là chỉ

ra: nếu khẳng định đúng với một giá trị nhất định (n − 1), thì nó cũng

8

đúng với giá trị tiếp theo (n).

Điều đó là đủ để kết luận rằng khẳng đúng với mọi n. Ta đã thấy nó

đúng với n = 1; nên theo trên, nó cũng đúng với n = 2 (ta đã thấy điều

này bằng tích toán trực tiếp, nhưng việc đó không thực sự cần thiết: nó

được suy ra trừ trường hợp n = 1). Theo cách tương tự, tính đúng đắn

của khẳng định với n = 2 kéo theo nó cũng đúng với n = 3, và đến lượt

nó lại kéo theo tính đúng đắn với n = 4, v.v.. Nếu ta lặp lại điều này đủ

nhiều, ta thu được tính đúng đắn với giá trị n bất kỳ. Do đó khẳng định

trên là đúng với mọi giá trị n.

Kỹ thuật chứng minh này được gọi là quy nạp (hoặc đôi khi gọi là quy

nạp toán học, để phân biệt với khái niệm trong triết học). Nó được tóm

tắt lại như sau.

Giả sử rằng ta muốn chứng minh một tính chất của các số nguyên dương.

Giả sử thêm ta có thể chứng minh hai điều:

(a) số 1 có tính chất đó, và

(b) bất cứ khi nào n − 1 có tính chất đó thì n cũng có tính chất đó

(n > 1).

Nguyên lý quy nạp nói rằng nếu (a) và (b) đúng, thì mọi số tự nhiên có

tính chất như vậy.

Điều này chính là những gì ta làm ở trên. Ta đã chỉ ra “tổng” của số lẻ

đầu tiên là 12, và tiếp theo ta chỉ ra nếu tổng của n − 1 số lẻ đầu tiên là

(n − 1)2, thì tổng của n số lẻ đầu tiên là n2, với mọi số nguyên n > 1.

Do đó, theo Nguyên lý quy nạp ta có thể kết luận rằng với mọi số nguyên

dương n, tổng của n số lẻ đầu tiên là n2.

Thông thường, cách tốt nhất để thử tiến hành chứng minh bằng phương

pháp quy nạp là như sau. Đầu tiên ta chứng minh phát biểu đúng với n = 1.

9

(Việc này đôi khi được gọi là trường hợp cơ sở.) Tiếp theo ta thử chứng

minh phát biểu cho giá trị tổng quát của n, và ta được phép giả sử rằng

phát biểu là đúng nếu n được thay bằng n − 1. (Việc này được gọi là giả

thiết quy nạp.) Nếu cần thiết, ta cũng có thể dùng tính đúng đắn của phát

biểu với n − 2, n − 3, v.v. và một cách tổng quát, với mọi k sao cho k < n.

Đôi khi ta nói rằng nếu 1 có tính chất nào đó, và mọi số nguyên n thừa

hưởng tính chất đó của n − 1, thì mọi số nguyên dương có tính chất đó.

(Cũng giống như nếu người bố của một gia đình có một khoản tài sản, và

mọi thế hệ sau này thừa kế tài sản đó từ thế hệ trước, thì gia đình luôn

luôn có tài sản này).

Thỉnh thoảng ta không bắt đầu với n = 1 mà bắt đầu với n = 0 (nếu

điều này có nghĩa) hoặc có thể với một giá trị lớn hơn (chẳng hạn, nếu

n = 1 không có ý nghĩa gì với lý do nào đó, hoặc phát biểu không dùng

cho trường hợp n = 1). Ví dụ, ta muốn chứng minh rằng n! là một số chẵn

nếu n > 1. Ta kiểm tra thấy điều này đúng với n = 2 (thật vậy, 2! = 2 là

số chẵn), và n được thừa kế tính chất này từ n − 1 (thật vậy, nếu (n − 1)!

là số chẵn, thì n! = n · (n − 1)! cũng là số chẵn). Điều này chứng minh

rằng n! là số chẵn với mọi n bắt đầu từ trường hợp cơ sở n = 2. Tất nhiên,

khẳng định là sai với n = 1.

Bài toán 1.1.1. Chứng minh bằng quy nạp và không bằng quy nạp rằng

n(n + 1) luôn là số chẵn với mọi số nguyên dương n.

Bài toán 1.1.2. Chứng minh bằng quy nạp rằng tổng của n số nguyên

dương đầu tiên là n(n + 1)/2.

Bài toán 1.1.3. Nhận xét rằng n(n + 1)/2 là số cái bắt tay giữa n + 1

người. Giả sử rằng tất cả mọi người chỉ đếm số bắt tay với người nhiều

tuổi hơn mình (khá là lố bịch, phải không?). Ai là người có số bắt tay

nhiều nhất? Có bao nhiêu người có 6 cái bắt tay? (Chúng ta giả sử rằng

10

không có hai người nào bằng tuổi).

Dựa vào kết quả của bài tập 1.1.2 chứng minh các kết quả của bạn.

Chúng ta thường dùng chữ “v.v.”: để miêu tả một số lập luận mà phải

lặp n lần mới thu được kết quả ta cần, nhưng sau khi lập luận một hoặc

hai lần, ta nói “v.v.” thay vì tiếp lục lặp lại. Không có gì là sai ở đây, nếu

lập luận đủ đơn giản thì ta có một cách trực quan thấy những chỗ mà

phép lặp bắt đầu. Nhưng sẽ tốt hơn nếu có thể dùng một số công cụ thay

vì “v.v.” trong trường hợp mà kết quả của phép lặp không quá rõ ràng.

Cách chính xác để làm điều này là dùng phép quy nạp. Giả sử ta chứng

minh công thức tính số tập con của một tập n phần tử (đáp án là 2n).

Nguyên lý quy nạp cho ta biết ta phải kiểm tra khẳng định đúng với

n = 0. Việc này là rõ ràng. Tiếp theo, ta giả sử rằng n > 0 và khẳng định

đúng với các tập có n − 1 phần tử. Xét tập S có n phần tử, và cố định

một phần tử bất kỳ a ∈ S. Ta muốn đếm số tập con của S. Ta chia chúng

thành hai lớp: lớp chứa a và lớp không chứa a. Ta đếm chúng một cách

tách biệt.

Đầu tiên, ta giải quyết với các tập con mà không chứa a. Nếu ta xóa a

khỏi S, ta còn lại tập con S(cid:48) có n − 1 phần tử, và các tập con ta quan tâm

chính là các tập con của S(cid:48). Theo giả thiết quy nạp, số tập con như vậy

là 2n−1.

Thứ hai, ta xét các tập con chứa a. Nhận xét mấu chốt là mỗi tập con

như vậy chứa a và một tập con của S(cid:48). Ngược lại, nếu ta lấy bất kỳ tập

con của S(cid:48), ta có thể thêm a vào nó để thu được một tập con của S chứa

a. Do đó số tập con của S chứa a bằng số tập con của S(cid:48), mà theo giả

thiết quy nạp bằng 2n−1.

Kết luận: Tổng số tập con của S là 2n−1 + 2n−1 = 2 · 2n−1 = 2n. Đ. p.

11

c. m

1.2 So sánh và đánh giá

Thật tốt nếu có công thức tính các số nhất định (ví dụ, có n! hoán vị

của n phần tử), nhưng quan trọng hơn là phải có một ý tưởng sơ bộ về độ

lớn những con số này. Ví dụ, số 100! có bao nhiêu chữ số?

Ta bắt đầu với các câu hỏi đơn giản hơn. Số nào lớn hơn, n hay (cid:0)n 2

(cid:1)? (cid:1) là 1, 3, 6, nên nó nhỏ hơn n với n = 2, bằng (cid:1) nếu n ≥ 4. Với n = 2, 3, 4 giá trị (cid:0)n 2 nhau với n = 3 và lớn hơn với n = 4. Thật ra, n = (cid:0)n 1 (cid:1) < (cid:0)n 2

Còn nhiều điều để nói hơn: Thương

(cid:1)

=

(cid:0)n 2 n

n − 1 2

trở lên lớn tùy ý khi n đủ lớn; ví dụ nếu ta muốn thương này lớn hơn 1000,

ta có thể chọn n > 2001. Theo ngôn ngữ của giải tích, ta có

(cid:1)

→ ∞ (n → ∞).

(cid:0)n 2 n

Dưới đây là một câu hỏi đơn giản khác: Số nào lớn hơn, n2 hay 2n? Với

giá trị n nhỏ, có thể có các kiểu khác nhau: 12 < 21, 22 = 22, 32 > 23,

42 = 24, 52 < 25. Nhưng từ đây trở đi, 2n cất cánh và tăng nhanh hơn n2.

Ví dụ 210 = 1024 lớn hơn nhiều so với 102 = 100. Thật ra 2n/n2 lớn tùy

ý với n đủ lớn.

(cid:1) nếu n ≥ 3. Bài toán 1.2.1. (a) Chứng minh rằng 2n > (cid:0)n 3

(b) Dùng (a) để chứng minh 2n/n2 lớn tùy ý khi n đủ lớn.

Bây giờ ta giải quyết vấn đề ước lượng số 100!, hay tổng quát hơn,

n! = 1 · 2 · · · n. Nhân tử 1 đầu tiên không ảnh hưởng gì, nhưng tất cả các

nhân tử khác đều ít nhất là 2, nên n! ≥ 2n−1. Tương tự n! ≤ nn−1, vì (bỏ

12

qua nhân tử 1) n! là tích của n − 1 nhân tử, mỗi trong số đó đều nhỏ hơn

n. (Vì tất cả trừ một trong số chúng nhỏ hơn n, nên tích nhỏ hơn nhiều.)

Do vậy ta biết rằng

(1.3)

2n−1 ≤ n! ≤ nn−1.

Các cận này cách nhau khá xa, với n = 10, cận dưới là 29 = 512, trong

khi cận trên là 109 (một tỉ).

Dưới đây là một câu hỏi vẫn chưa được trả lời bằng các ước lượng trong

(1.3). Số nào lớn hơn, n! hay 2n? Nói cách khác, tập với n phần tử có số

phép hoán vị nhiều hơn số tập con hay không? Với các giá trị n nhỏ, số tập

con thắng nhiều hơn: 21 = 2 > 1! = 1, 22 = 4 > 2! = 2, 23 = 8 > 3! = 6.

Nhưng từ đây thì lại đổi chiều: 24 = 16 < 4! = 24, 25 = 32 < 5! = 120.

Dễ thấy rằng khi n tăng, n! tăng nhanh hơn 2n: Nếu ta đi từ n tới n + 1,

thì 2n tăng với hệ số 2, trong khi n! tăng với hệ số n + 1.

Bài toán 1.2.2. Dùng phép quy nạp để chính xác hoá phát biểu trên và

chứng minh rằng n! > 2n nếu n ≥ 4.

Dưới đây là công thức đưa ra phép xấp xỉ rất tốt cho n!. Ta phát biểu

nó mà không chứng minh, vì chứng minh (mặc dù không hoàn toàn khó)

cần đến giải tích.

Định lý 1.2.1. [Công thức Stirling]

(cid:17)n √

n! ∼

2πn.

(cid:16)n e

Ở đây π = 3.14... là diện tích của hình tròn có bán kính bằng 1, e =

2.718... là cơ sở của hàm logarit tự nhiên, và ∼ có nghĩa là phép xấp xỉ

theo nghĩa

→ 1 (n → ∞).

n! (cid:1)n √

2πn

(cid:0) n e

13

Cả hai số vô tỉ siêu việt e và π xuất hiện trong cùng một công thức!

Ta quay trở lại câu hỏi: Số 100! có bao nhiêu chữ số? Theo công thức

Stirling ta biết rằng

√

100! ≈ (100/e)100 ·

200π.

Số chữ số của số này là logarit cơ số 10 của nó được làm tròn. Do đó ta có

√

lg(100!) ≈ 100 lg(100/e) + 1 + lg

2π = 157.969...

Nên số chữ số trong số 100! là vào khoảng 158 (thật ra đây là giá trị đúng).

1.3 Chứng minh các đồng nhất thức và bất đẳng

thức nhờ quy nạp toán học

Phương pháp quy nạp toán học cho phép chứng minh các đồng nhất

thức và bất đẳng thức mà một hoặc hai vế của chúng phụ thuộc số tự

nhiên n. Chẳng hạn, trước tiên có thể kiểm tra rằng đồng nhất thức cần

chứng minh đúng khi n = 1, sau đó viết đồng nhất thức khi n = k + 1

và n = k rồi trừ từng vế hai đồng nhất thức nhận được. Nếu làm như vậy

mà thấy hiệu các vế trái của các đồng nhất thức bằng hiệu các vế phải,

thì do đồng nhất thức đúng với n = k, ta suy ra đồng nhất thức đúng với

n = k + 1, và như vậy do quy nạp toán học, đồng nhất thức đúng với mọi

giá trị n.

Chẳng hạn, ta sẽ chứng minh rằng, với mọi n đồng nhất thức sau đây

nghiệm đúng:

Bài toán 1.3.1.

Chứng minh rằng với mọi số nguyên dương n ta có

1 −

+

−

+ ... +

−

=

+

+ ... +

(1.3.1)

1 2

1 3

1 4

1 2n − 1

1 2n

1 n + 1

1 n + 2

1 2n

14

Chứng minh.

2 = 1

2 đúng.

Khi n = 1, đồng nhất thức có dạng 1 − 1

Bây giờ ta viết đồng nhất thức khi n = k và khi n = k + 1

1 −

+ ... +

−

=

+

,

+ ... +

(1.3.1.1)

1 2

1 2k − 1

1 2k

1 k + 1

1 k + 2

1 2k

1−

+...−

+

−

=

+...+

+

+

, (1.3.1.2)

1 2k

1 2k + 1

1 2(k + 1)

1 k + 2

1 2k

1 2k + 1

1 2k + 2

1 2

Trừ từng vế các đồng nhất thức này cho nhau ta được

−

=

+

−

,

1 2k + 1

1 2(k + 1)

1 2k + 1

1 2k + 2

1 k + 1

hay là

=

.

2 2(k + 1)

1 k + 1

đúng.

Điều đó có nghĩa là nếu (1.3.1.1) đúng thì (1.3.1.2) đúng, do đó theo quy

(cid:3) nạp toán học đồng nhất thức (1.3.1) đúng với mọi số tự nhiên n.

Hoàn toàn như vậy ta chứng minh được khẳng định sau đây, được gọi

là bất đẳng thức Bernoulli:

Bài toán 1.3.2.

Nếu x > −1 thì mọi số tự nhiên n bất đẳng thức sau đây nghiệm đúng:

(1 + x)n ≥ 1 + nx.

(1.3.2).

Chứng minh. Thật vậy, khi n = 1 ta có bất đẳng thức đúng

1 + x ≥ 1 + x .

Giả sử (1 + x)k ≥ 1 + kx. Vì theo giả thiết 1 + x > 0 nên bất đẳng thức

vấn đúng khi nhân cả hai vế với 1 + x ta nhận được

(1 + x)k+1 ≥ (1 + kx)(1 + x) .

15

hay (1 + x)k+1 ≥ 1 + (k + 1)x + kx2.

Do kx2 ≥ 0 nên từ đó suy ra

(1 + x)k+1 ≥ 1 + (k + 1)x .

Theo quy nạp toán học ta kết luận được rằng bất đẳng thức (1.3.2) đúng

(cid:3) với mọi số tực nhiên n

1.4 Bài toán của Fibonacci

Vào thế kỉ XIII, nhà toán học người Italia Leonardo Fibonacci nghiên

cứu câu hỏi sau:

Một người nông dân nuôi các con thỏ. Sau hai tháng tuổi, mỗi

con thỏ sinh ra một thỏ con, và sau đó cứ mỗi tháng lại sinh một

con. Giả sử các con thỏ không bao giờ chết, và ta xem là không

có thỏ đực. Hỏi người nông dân có bao nhiêu con thỏ sau n tháng

nếu ông ta bắt đầu bằng một con thỏ mới sinh?

Ta dễ dàng hình dung ra đáp án với các giá trị n nhỏ. Người nông dân

có một con thỏ trong tháng đầu tiên và một con thỏ trong tháng thứ hai,

vì con thỏ cần đủ hai tháng tuổi trước khi nó biết đẻ. Người nông dân có

2 thỏ trong thang thứ ba, và ba con thỏ trong tháng thứ tư, vì con thỏ

đầu tiên sinh ra một con sau tháng thứ hai. Sau 4 tháng, con thỏ thứ hai

cũng sinh một con thỏ mới, nên hai con thỏ con được thêm vào. Điều này

có nghĩa người nông dân có 5 con thỏ sau tháng thứ 5.

Dễ dàng suy ra quy tắc tăng trưởng đàn thỏ với số tháng bất kỳ, nếu ta

chú ý rằng số thỏ mới sinh trong mỗi tháng chính bằng số thỏ ít nhất hai

tháng tuổi, tức là, những con đã có ở tháng trước. Nói cách khác, để tính

16

số thỏ trong tháng tiếp theo, ta phải cộng thêm số thỏ trong tháng trước

đó vào số thỏ trong tháng hiện tại. Việc này giúp ta dễ dàng tính lần lượt

số thỏ:

1, 1, 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 5 = 13, . . .

(Có vẻ Fibonacci không thực sự coi câu hỏi của ông như bài toán áp

dụng thực tế; ông làm việc với các con số, chú ý rằng việc này sinh ra các

con số mới đối với ông, nhưng lại có các tính chất thú vị, như ta sẽ thấy

về sau).

Để viết điều này thành công thức, ta ký hiệu Fn là số thỏ trong tháng

thứ n. Khi đó ta có, với n = 2, 3, 4, . . .,

(1.4)

Fn+1 = Fn + Fn−1.

ta cũng biết rằng F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5. Để cho tiện, ta

ký hiệu F0 = 0; khi đó phương trình (1.4) vẫn đúng với n = 1, giống như

định nghĩa của các số này. Điều này có gì đó có vẻ không bình thường:

thay vì nói cho ta biết Fn là cái gì (theo công thức), ta chỉ đưa ra quy tắc

tính mỗi số Fibonacci từ hai số liền trước, và chỉ rõ hai giá trị đầu tiên.

Định nghĩa như thế này được gọi là phép truy hồi. Nó khá giống phép quy

nạp (ngoại trừ đây không phải là một kỹ thuật chứng minh, mà là một

phương pháp định nghĩa), và đôi khi được gọi là định nghĩa bằng quy nạp.

Bài toán 1.4.1. Tại sao ta phải chỉ rõ hai giá trị đầu tiên? Tại sao không

phải là một hoặc ba?

Trước khi thảo luận thêm về các số này, ta xét một bài toán đếm khác:

Một cầu thang có n bậc. Bạn đi lên theo từng bậc một hoặc 2

bậc. Hỏi có bao nhiêu cách để bạn đi lên?

Với n = 1, chỉ có một cách. Với n = 2, bạn có 2 lựa chọn: đi hai lần

17

bước đơn hoặc đi một lần bước kép. Với n = 3, ta có ba cách: ba lần bước

đơn, hoặc một bước đơn rồi một bước kép, hoặc một bước kép rồi một

bước đơn.

Ta dừng lại và thử đoán đáp án tổng quát! Nếu bạn dự đoán số cách đi

lên với n bậc là n cách, bạn đã sai. Trường hợp tiếp theo, n = 4, có 5 cách

(1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 2 + 2).

Nên thay vì dự đoán, ta thử cách sau. Ký hiệu Jn là đáp án. Ta thử hình

dung Jn+1 bằng bao nhiêu, giả sử ta biết giá trị của Jk với 1 ≤ k ≤ n.

Nếu ta bắt đầu bằng một bước đơn, ta có Jn cách để đi tiếp n bước còn

lại. Nếu bắt đầu bằng một bước kép, ta có Jn−1 cách đi lên n − 1 bước còn

lại. Nên tất cả có

Jn+1 = Jn + Jn−1.

Câu hỏi này cũng tương tự như câu hỏi ta đã dùng để tính dãy số Fibonacci

Fn. Điều này có phải có nghĩa là Fn = Jn? Tất nhiên là không rồi, như ta

thấy ở các giá trị ban đầu: Ví dụ, F3 = 2 nhưng J3 = 3. Tuy nhiên, dễ

thấy rằng tất cả những gì xảy ra là Jn bị di chuyển thành

Fn+1.

Điều này đúng với n = 1, 2, và nên tất nhiên đúng với mọi n, vì các dãy

F2, F3, F4, . . . và J1, J2, J3, . . . được tính toán bằng quy tắc giống nhau từ

giá trị của hai phần tử ban đầu.

Bài toán 1.4.2. Bạn có n đô la để tiêu. Mỗi ngày bạn mua một viên kẹo

với giá 1 đô la hoặc một cây kem với giá 2 đô la. Hỏi bạn có bao nhiêu

18

cách tiêu chỗ tiền này?

1.5 Một số đồng nhất thức

Có rất nhiều công thức thú vì về dãy Fibonacci. Ví dụ, tổng của n số

Fibonacci đầu tiên bằng bao nhiêu? Ta có

0 = 0,

0 + 1 = 1,

0 + 1 + 1 = 2,

0 + 1 + 1 + 2 = 4,

0 + 1 + 1 + 2 + 3 = 7,

0 + 1 + 1 + 2 + 3 + 5 = 12,

0 + 1 + 1 + 2 + 3 + 5 + 8 = 20,

0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.

Bắt đầu bằng các số này, không khó để nhận ra rằng bằng cách cộng thêm

1 vào vế phải ta thu được dãy số Fibonacci, thật ra, ta được số Fibonacci

sau hai bước của số hạng cuối cùng. Ta có

F0 + F1 + F2 + · · · + Fn = Fn+2 − 1.

Tất nhiên, tại thời điểm này thì đây mới chỉ là một khẳng định, một phát

biểu toán học chưa được chứng minh mà ta tin là đúng. Để chứng minh

nó, ta dùng phép quy nạp theo n (vì dãy Fibonacci được xác định bằng

phép truy hồi, phép quy nạp là tự nhiên, và thường là phương pháp chứng

minh duy nhất).

Ta đã kiểm tra công thức đúng với n = 0 và 1. Giả sử rằng công thức

đúng với n − 1 số Fibonacci đầu tiên. Xét tổng của n số Fibonacci đầu

tiên:

F0 + F1 + . . . + Fn = (F0 + F1 + . . . + Fn−1) + Fn = (Fn+1 − 1) + Fn,

19

theo giả thiết quy nạp. Nhưng bây giờ ta có thể dùng phương trình truy

hồi của dãy Fibonacci để thu được

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

Suy ra điều phải chứng minh.

Bài toán 1.5.1. Chứng minh rằng F3n là số chẵn.

Bài toán 1.5.2. Chứng minh rằng F5n chia hết cho 5.

Bài toán 1.5.3. Chứng minh các công thức sau.

(a) F1 + F3 + F5 + . . . + F2n−1 = F2n.

(b) F0 − F1 + F2 − F3 + · · · − F2n−1 + F2n = F2n−1 − 1.

Bây giờ ta muốn phát biểu một công thức khó hơn:

n + F 2 F 2

n−1 = F2n−1.

(1.5)

Dễ dàng kiểm tra được công thức này đúng với nhiều giá trị n, và ta có

thể thuyết phục rằng nó đúng, nhưng để chứng minh nó thì hơi khó hơn

một ít. Tại sao công thức này lại khó hơn các công thức trước. Bởi vì nếu

ta muốn chứng minh nó bằng quy nạp (ta không thực sự có cách nào khác

tại thời điểm này), thì ở vế phải ta chỉ có một số Fibonacci khác, và do

vậy ta không biết cách để áp dụng phép truy hồi ở đây.

Một cách để khắc phục điều này là tìm công thức tương tự cho F2n, và

chứng minh cả hai công thức bằng quy nạp. Với một chút may mắn (hay

trực quan sâu sắc?) bạn có thể giả thiết

(1.6)

Fn+1Fn + FnFn−1 = F2n.

20

Một lần nữa dễ dàng thấy công thức này đúng với nhiều giá trị n, để

chứng minh (1.6), ta dùng công thức truy hồi cơ bản (1.4) hai lần:

Fn+1Fn + FnFn−1 = (Fn + Fn−1)Fn + (Fn−1 + Fn−2)Fn−1

= (F 2

n + F 2

n−1) + (FnFn−1 + Fn−1Fn−2)

= F2n−1 + F2n−2 = F2n.

(áp dụng (1.5) cho số hạng đầu tiên và phép quy nạp cho số hạng thứ hai).

n + F 2 F 2

Chứng minh của (1.5) là tương tự:

= (F 2

n−1 n−2) + 2Fn−1Fn−2 + F 2

n−1

= (F 2

n−2) + Fn−1(Fn−2 + Fn−1) + Fn−1Fn−2

= (F 2

n−1 = (Fn−1 + Fn−2)2 + F 2 n−1 + F 2 n−1 + F 2 n−1 + F 2

n−2) + FnFn−1 + Fn−1Fn−2

= F2n−3 + F2n−2 = F2n−1.

(áp dụng phép quy nạp cho số hạng đầu tiên và công thức (1.6) cho số

hạng thứ hai).

Đợi một chút! Thủ thuật ở đây là gì? Chúng ta sử dụng (1.6) trong

chứng minh (1.5), và sau đó (1.5) trong chứng minh (1.6)? Không sao, lập

luận là đúng. Nó chỉ là hai chứng minh quy nạp phải đi cùng một lúc. Nếu

chúng ta biết rằng cả (1.6) và (1.5) cùng đúng với giá trị nhất định của

n, sau đó ta chứng minh (1.5) cho các giá trị tiếp theo (nếu bạn nhìn vào

chứng minh, bạn có thể thấy nó chỉ sử dụng các giá trị n nhỏ hơn), và sau

đó sử dụng điều này và các giả thiết quy nạp một lần nữa để chứng minh

(1.6).

Thủ thuật này được gọi là quy nạp đồng thời, và nó là một phương pháp

21

hữu ích để làm cho phép quy nạp mạnh hơn.

Chương 2

QUY NẠP VÀ CÁC BÀI TOÁN TỔ HỢP

2.1 Số tập con

Ta quay lại với bài toán: Có tất cả bao nhiêu tập con của một tập có n

phần tử?

Ta bắt đầu bằng cách thử với các số nhỏ. Các phần tử của tập là gì thì

cũng không có gì khác biệt, ta gọi chúng là a, b, c, v.v. Tập rỗng chỉ có một

tập con (cụ thể là chính nó). Một tập có một phần tử, ví dụ {a}, có hai

tập con: tập {a} và tập rỗng Ø. Một tập có hai phần tử, ví dụ {a, b} có

bốn tập con: Ø, {a}, {b}, {a, b}. Để liệt kê các tập con của tập có 3 phần

tử {a, b, c} ta phải tính nhiều hơn:

(2.1)

Ø, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}.

Số phần tử trong tập 0

1

2

3

Số tập con

1

2

4

8

Ta có thể lập thành bảng

Dựa vào các giá trị trong bảng, ta thấy rằng số tập con là lũy thừa của

2: Nếu tập có n phần tử, thì kết quả là 2n, ít nhất là đúng với các ví dụ

22

nhỏ này.

Không khó để thấy rằng điều này luôn đúng. Giả sử bạn phải chọn một

tập con của một tập A có n phần tử; ta gọi các phần tử này là a1, a2, . . . , an.

Khi đó chúng ta có thể muốn hoặc không muốn bao gồm a1, nói cách khác,

ta có thể đưa ra hai lựa chọn ở đây. Không quan trọng ta đã quyết định

như thế nào về a1, ta có thể muốn hoặc không muốn bao gồm a2 trong

tập con này; điều này có nghĩa có hai lựa chọn, và do vậy tổng số cách ta

có thể chọn về a1 và a2 là 2 · 2 = 4. Bây giờ không quan trọng ta đã chọn

a1 và a2, ta phải quyết định chọn a3, và một lần nữa ta có hai cách. Mỗi

một trong hai cách này có thể kết hợp với 4 lựa chọn ta có thể đưa ra về

a1 và a2, tạo ra 4 · 2 = 8 khả năng để quyết định về a1, a2 và a3.

Ta có thể tiếp tục như vậy: Không quan trọng về k phần tử đầu tiên,

ta có hai lựa chọn về số tiếp theo, và do vậy số khả năng nhân đôi mỗi lần

ta lấy một phần tử mới. Để quyết định về tất cả n phần tử của tập hợp,

ta có 2n khả năng.

Do đó ta suy ra định lý sau.

Định lý 2.1.1. Một tập với n phần tử có 2n tập con.

2.2 Dãy số

Từ việc "mã hóa" các tập con là các chuỗi 0 và 1, chúng ta muốn xác

định số lượng các chuỗi có độ dài n được xây dựng từ một tập các ký hiệu

khác nhau, ví dụ, a, b và c. Các lập luận mà chúng ta đưa ra cho trường

hợp của chuỗi 0 và 1 có thể được chuyển sang trường hợp này mà không

có bất kỳ sự thay đổi bản chất. Chúng ta có thể thấy rằng với phần tử

đầu tiên của chuỗi, chúng ta có thể chọn bất kỳ phần tử từ a, b và c, tức

là, chúng ta có 3 lựa chọn. Không quan trọng chúng ta chọn cái gì, có 3

lựa chọn cho phần tử thứ hai của chuỗi, do đó, số cách để chọn hai phần

23

tử đầu tiên là 32 = 9. Tiến hành theo cách thức tương tự, chúng tôi nhận

thấy số cách để chọn toàn bộ chuỗi là 3n.

Trong thực tế, số 3 không có vai trò đặc biệt gì ở đây; lập luận tương

tự ta chứng minh định lý sau:

Định lý 2.2.1. Số chuỗi có độ dài n gồm k phần tử là kn.

Bài toán sau đây dẫn tới tổng quát hóa của câu hỏi này. Giả sử rằng một

cơ sở dữ liệu có 4 trường: trường đầu tiên chứa tên viết tắt của người lao

động gồm 8 ký tự, trường thứ hai là M hoặc F cho giới tính, trường thứ 3

là ngày sinh của người lao động dưới dạng tháng-ngày-năm (bất chấp vấn

đề không thể phân biệt được các nhân viên sinh năm 1880 với các nhân

viên sinh năm 1980); và trường thứ 4 là mã nghề trong số 13 mã. Hỏi có

tất cả bao nhiêu dữ liệu khác nhau?

Số dữ liệu tất nhiên sẽ rất lớn. Trường thứ nhất có thể chứa 268 >

200.000.000.000 tên (phần lớn trong số chúng sẽ rất khó để phát âm và

khó có thể xảy ra, nhưng ta phải đếm tất cả số trường hợp). Trường thứ

hai có hai khả năng. Trường thứ 3 có thể được coi là 3 trường riêng biệt,

có tương ứng 12, 31, và 100 khả năng (một số tổ hợp của chúng sẽ không

bao giờ xảy ra, ví dụ 04-31-76 hay 02-29-13, nhưng ta bỏ qua điều này).

Trường cuối cùng có 13 khả năng.

Bây giờ ta xác định cách các trường này được kết hợp với nhau. Ta có

lặp lại lập luận như trên, theo thứ tự “3 cách chọn” được thay bằng “268

cách chọn”, “2 cách chọn”, “12 cách chọn”, “31 cách chọn”, “100 cách chọn”,

và “13 cách chọn”. Ta thu được kết quả là là 268 · 2 · 12 · 31 · 100 · 13 =

201, 977, 536, 857, 907, 200.

Ta có thể tổng quát hóa định lý 2.2.1 (chứng minh bao gồm lặp lại các

lập luận như trên).

Định lý 2.2.2. Giả sử ta muốn lập một chuỗi có độ dài n bằng một tập bất

24

kỳ có k1 ký hiệu làm phần tử đầu của chuỗi, một tập bất kỳ có k2 ký hiệu

làm phần tử thứ hai của chuỗi, v.v., một tập bất kỳ có kn ký hiệu làm phần

tử cuối của chuỗi. Khi đó tổng số chuỗi được lập thành là k1 · k2 · · · kn.

Một trường hợp đặc biệt khác, xét bài toán sau: có bao nhiêu số nguyên

không âm có đúng n chữ số (theo hệ số thập phân)? Rõ ràng chữ số đầu

tiên có thể là số bất kì trong 9 số (1, 2, . . . , 9), trong khi chữ số thứ hai,

thứ ba, v.v., có thể là số bất kì trong 10 số. Do đó ta thu được một trường

hợp đặc biệt của câu hỏi trước với k1 = 9 và k2 = k3 = · · · = kn = 10. Do đó đáp án là 9 · 10n−1.

Bài toán 2.2.1. Vẽ một cây minh họa cách ta đếm số chuỗi có độ dài 2

từ các ký tự a, b và c và giải thích. Làm tương tự với bài toán tổng quát

hơn khi n = 3, k1 = 2, k2 = 3, k3 = 2.

Bài toán 2.2.2. Trong cửa hàng thể thao có các áo cộc tay có 5 kiểu màu

khác nhau, quần có 4 kiểu màu khác nhau và tất có 3 kiểu màu khác nhau.

Có tất cả bao nhiêu kiểu đồng phục mà bạn có thể chọn từ các bộ này?

2.3 Số tập con có thứ tự

Trong cuộc thi có 100 vận động viên điền kinh, chỉ có thứ tự của 10

người đầu tiên được ghi lại. Hỏi có bao nhiêu kết quả có thể của cuộc thi?

Câu hỏi này có thể được trả lời theo các lập luận ta đã thấy. Vị trí đầu

tiên có thể là vận động viên bất kì; không quan trọng ai thắng, có 99 khả

năng người thắng thứ 2, nên hai giải thưởng đầu tiên có thể có 100 · 99

cách khác nhau. Lấy ra 2 vận động viên đầu tiên, còn 98 vận động viên có

thể lấy vị tr thứ 3, v.v.. Nên đáp án là 100 · 99... · 91.

Bài toán 2.3.1. Minh họa lập luận trên bằng một cây.

Bài toán 2.3.2. Giả sử rằng ta ghi lại thứ tự của tất cả 100 vận động

25

viên.

(a) Có bao nhiêu kết quả khác nhau có thể?

(b) Có bao nhiêu trong số các kết quả có 10 vị trí đầu tiên giống nhau?

(c) Chứng minh rằng kết quả về mười vị trị đầu tiên bên trên có thể

thu được từ các kết quả (a) và (b).

Không có gì đặc biệt liên quan đến số 10 hay 100 ở bài toán trên; ta có

thể tiến hành cho n vận động viên với k vị trí đầu tiên được ghi lại.

Để đưa ra dạng toán học, ta thay các vận động viên bằng tập bất kỳ

có kích thước n. Danh sách k vị trí đầu tiên được thay bằng một dãy k

phần tử được chọn trong số n phần tử, mà tất cả đều phải khác nhau. Ta

cũng có thể coi việc này như chọn một tập con từ các vận động viên chứa

k phần tử, và sau đó sắp xếp chúng. Do đó ta có định lý sau.

Định lý 2.3.1. Số tập con gồm k phần tử có thứ tự của một tập có n phần

tử là n(n − 1)...(n − k + 1).

Bài toán 2.3.3. Nếu tổng quát hóa lời giải của bài tập 2.2.2, ta thu được

kết quả dưới dạng

.

n! (n − k)!

Kiểm tra lại rằng kết quả này giống như trong Định lý 2.3.1.

Bài toán 2.3.4. Giải thích sự giống và khác nhau giữa lời giải của bài

toán đếm trong Định lý 2.3.1 và Định lý 2.1.1.

2.4 Số tập con có kích thước cho trước

Từ đây, ta dễ dàng suy ra được một trong các kết quả đếm quan trọng

nhất.

Định lý 2.4.1. Số tập con gồm k phần tử của một tập có n phần tử là

=

.

n(n − 1)...(n − k + 1) k!

n! k!(n − k)!

26

Chứng minh. Nhắc lại rằng nếu ta đếm tập con có thứ tự, theo Định lý

2.3.1 ta được n(n − 1)...(n − k + 1) = n!/(n − k)!. Tất nhiên, nếu ta muốn

biết số tập con không phân biệt thứ tự, thì ta đã tính được, mọi tập con

được đếm đúng k! lần (với mọi thứ tự đều có thể). Nên ta phải chia số này

(cid:3) cho k! để thu được số tập con với k phần tử (mà không có thứ tự).

Số tập con có k phần tử của tập n phần tử là một đại lượng quan trọng (cid:1) (đọc là “chập k của n”). Do đó mà ta có một ký hiệu đặc biệt cho nó: (cid:0)n k

(cid:32) (cid:33)

(2.2)

=

.

n k

n! k!(n − k)!

(cid:1) được gọi là hệ số nhị thức (trong Mục 2.7 ta sẽ thấy tại sao lại Các số (cid:0)n k

gọi như thế).

Giá trị của (cid:0)n n

(cid:1) là 1, vì một tập có n phần tử có đúng một tập con có n (cid:1) = 1, cụ thể là (cid:1) = 1. phần tử, chính là nó. Có thể hơi lừa gạt khi thấy rằng (cid:0)n 0 tập rỗng. Điều này thậm chí còn đúng với tập rỗng, nên (cid:0)0 0

(cid:1) với 0 ≤ k ≤ n ≤ 5.

Bài toán 2.4.1. Lập bảng giá trị của (cid:0)n k (cid:1) với k = 0, 1, n − 1, n bằng (2.2),

(cid:1). Bài toán 2.4.2. Tìm các giá trị của (cid:0)n k và giải thích kết quả theo ý nghĩa tổ hợp của (cid:0)n k

Hệ số nhị thức thỏa mãn nhiều đẳng thức quan trọng. Trong định lý

tiếp theo chúng ta liệt kê ra một vài trong số chúng; một số đẳng thức

khác sẽ xuất hiện trong bài tập tiếp theo.

Định lý 2.4.2. Hệ số nhị thức thỏa mãn các đẳng thức sau:

(cid:32) (cid:33) (cid:32)

(2.3)

=

(cid:33) ;

n k

n n − k

Nếu n, k > 0 thì (cid:32) (cid:33) (cid:32) (cid:33) (cid:32)

(2.4)

+

=

(cid:33) ;

n − 1 k − 1

n − 1 k

n k

27

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)

(2.5)

+

+

+ · +

+

= 2n.

n 0

n 1

n 2

n n − 1

n n

Chứng minh. Ta chứng minh (2.3) bằng cách dùng ý nghĩa tổ hợp cho cả

hai vế. Ta có một tập n phần tử, đặt là S. Vế trái đếm số tập con có k

phần tử của S, trong khi vế phải đếm số tập con có (n − k) phần tử của

S. Để thấy các số này bằng nhau, ta chỉ cần chú ý rằng với mọi tập con

k phần tử có tương ứng một tập (n − k) phần tử: phần bù của nó trong

S, mà chứa đúng các phần tử của S không nằm trong tập con k phần tử.

Việc này ghép cặp các tập con k phần tử với các tập con (n − k) phần tử,

chỉ ra chúng có số lượng bằng nhau.

Ta chứng minh (2.4) bằng công thức đại số (2.2). Sau khi thế, đẳng thức

trở thành

=

+

.

n! k!(n − k)!

(n − 1)! (k − 1)!(n − k)!

(n − 1)! k!(n − k − 1)!

Ta có thể chia cả hai vế cho (n − 1)! và nhân với (k − 1)!(n − k − 1)!; khi

đó đẳng thức trở thành

=

+

,

n k(n − k)

1 n − k

1 k

đến đây ta có thể dễ dàng kiếm tra bằng tính toán thông thường.

Cuối cùng, ta chứng minh (2.5) bằng giải thích tổ hợp một lần nữa. Gọi

S là tập có n phần tử. Số hạng đầu tiên ở vế trái là đếm các tập con không

phần tử của S (chỉ có một tập là tập rỗng); số hạng thứ hai đếm số tập

con chỉ có một phần tử, tiếp theo số hạng thứ hai đếm các con có 2 phần

tử, v.v.. Trong cả tổng, mọi tập con của S được đếm đúng một lần. Ta

biết rằng 2n (ở vế phải) là số tất cả các tập con của S. Điều này chứng (cid:3) minh (2.5), và kết thúc chứng minh định lý.

28

Bài toán 2.4.3. Tìm một chứng minh của (2.3) bằng công thức đại số (cid:1) và một chứng minh của (2.4) bằng ý nghĩa tổ hợp ở cả hai vế. cho (cid:0)n k

(cid:1) = n2; đưa ra hai chứng Bài toán 2.4.4. Chứng minh rằng (cid:0)n 2 (cid:1) + (cid:0)n+1 2

minh, một bằng giải thích tập hợp, một bằng công thức đại số của hệ số

nhị thức.

2.5 Bao hàm - Loại trừ

Trong một lớp học có 40 sinh viên, nhiều sinh viên đang sưu tầm những

bức ảnh của ngôi sao nhạc rock thần tượng của họ. 18 sinh viên có ảnh

của nhóm Beatles, 16 sinh viên có ảnh của nhóm Rolling Stones và 12 sinh

viên có ảnh của Elvis Presley (điều này xảy ra từ trước, khi họ còn trẻ).

Có 7 sinh viên có ảnh của cả nhóm Beatles và nhóm Rolling Stones, 5 sinh

viên có ảnh của cả nhóm Rolling Stones và Elvis Presley, và 3 sinh viên

có ảnh của cả nhóm Beatles và Elvis Presley. Cuối cùng, có 2 sinh viên có

ảnh của cả ba nhóm. Câu hỏi: Có bao nhiêu sinh viên trong lớp không có

bức ảnh nào của các nhóm trên?

Đầu tiên, ta có thể cố gắng lập luận như sau: Có 40 sinh viên trong lớp;

bỏ đi số sinh viên có ảnh của nhóm Beatles (18), bỏ đi những sinh viên

có ảnh của nhóm Rolling Stones (16), và bỏ đi những sinh viên có ảnh

của Elvis (12), nên ta bỏ đi 18 + 16 + 12. Ta được -6; đây là số âm cảnh

báo ta rằng đã có lỗi nào đó trong tính toán vừa rồi; nhưng cái gì không

đúng? Ta mắc sai lầm khi trừ số sinh viên mà có ảnh của cả hai nhóm

hai lần! ví dụ, một sinh viên có ảnh của Beatles và Elvis Presley bị trừ

với những người có ảnh của Beatles cũng như những sinh viên có ảnh của

Elvis Presley. Để sửa lại, ta phải cộng lại số sinh viên mà có ảnh của cả

hai nhóm. Theo cách này ta được 40 − (18 + 16 + 12) + (7 + 5 + 3). Nhưng

ta phải cẩn thận. Ta không nên mắc sai lầm một lần nữa! Điều gì xảy ra

29

với 2 sinh viên có ảnh của ba nhóm? Ta trừ 3 lần ở lúc đầu, rồi cộng lại 3

lần, nên ta phải trừ một lần nữa! Cuối cùng, kết quả là:

(2.6)

40 − (18 + 16 + 12) + (7 + 5 + 3) − 2 = 7.

Chúng ta không thể tìm bất kỳ chỗ sai sót nào trong công thức trên, dù

tìm theo bất kỳ cách nào. Nhưng từ kinh nghiệm trước đây, ta phải cẩn

thận hơn: Ta phải đưa ra một chứng minh chính xác!

Nên giả sử ai đó ghi lại dữ liệu của lớp trong một bản như bảng 2.1 bên

dưới. Mỗi hàng tương ứng với một sinh viên; chung tôi không ghi hết tất

Name Bonus Beatles Stones Elvis BS BE SE BSE

1

0

0

0

0

0

0

0

Al

1

-1

0

0

0

0

0

0

Bel

1

- 1

-1

0

1

0

0

0

Cy

1

-1

0

-1

0

1

0

0

Di

1

-1

-1

-1

1

1

1

-1

Ed ...

Bảng 2.1:

cả 40 sinh viên, mà chỉ ghi vài người

Bảng trên có vẻ ngớ ngẩn (nhưng có lý do). Đầu tiên, chúng ta tặng 1

cho mọi sinh viên. Thứ hai, ta ghi lại trong các cột tách biệt liệu sinh viên

có đang sưu tầm ảnh cả Beatles và Elvis Presley hay không (viết lắt là

BE), mặc dù điều này có thể được suy ra từ các cột trước đó. Thứ 3, ta

đặt −1 trong các cột để ghi lại thông tin người có số lẻ ảnh, và 1 để ghi

lại thông tin người giữ số chẵn ảnh.

Ta tính tổng số phần tử trong bảng theo hai cách khác nhau. Đầu tiên,

tổng hàng bằng bao nhiêu? Với Al ta được 1 và với tất cả các người khác

là tổng bằng 0. Đây không phải là một sự trùng hợp. Nếu ta xét một sinh

viên giống như Al, người mà không có bất kỳ bức tranh nào, thì sinh viên

30

này đóng góp 1 trong cột Bonus, nhưng không đóng góp chỗ nào khác,

điều đó có nghĩa tổng theo hàng của sinh viên này bằng 1. Tiếp theo, xét

Ed, người có cả 3 bức tranh. Anh có 1 trong cột Bonus; ba cột tiếp theo,

anh ấy có 3 số hạng −1. Trong mỗi ba cột tiếp theo anh ấy có 1, một cho (cid:1). Hàng của anh ấy kết mỗi một cặp ảnh; tốt hơn nếu ta coi 3 số này là (cid:0)3 2 (cid:1) bằng 1, nhưng viết theo cách này để thấy được ý (cid:1) số −1 ((cid:0)3 thúc với (cid:0)3 3 3

tưởng tổng quát tốt hơn). Nên tổng của hàng là

(cid:33)

1 −

+

−

= 0.

(cid:33) (cid:32) 3 1 (cid:32) 3 2 (cid:33) (cid:32) 3 3

= 0 của Bel (1 ảnh),

1 −

= 0 của Di (2 ảnh).

1 −

+

Kiểm tra hàng của Bel, Cy, và Di, ta thấy tổng hàng của họ là (cid:33) (cid:32) 1 1 (cid:33) (cid:32) 2 2 (cid:33) (cid:32) 2 1

Nếu ta chuyển số hạng âm sang vế bên kia của phương trình, ta thu được

một phương trình với ý nghĩa tổ hợp: Số tập con của tập n phần tử với số

chẵn phân tử bằng số tập con với số lẻ phần tử. ví dụ, (cid:33) (cid:33) (cid:33)

+

=

+

(cid:32) 3 0 (cid:32) 3 2 (cid:32) 3 1 (cid:33) (cid:32) 3 . 3

Nhắc lại trong Bài tập 1.3.3 khẳng định rằng điều này đúng với mọi n ≥ 1.

Vì tổng theo hàng bằng 0 với mọi sinh viên mà có ảnh của bất kỳ nhóm

nào, và bằng 1 với những người không có ảnh, tổng của 40 hàng chính là

số sinh viên không có ảnh.

Mặt khác, tổng theo cột thì như thế nào? Trong cột bonus, ta có 40 lần

+1; trong cột Beatles, ta có 18 lần −1, tiếp theo ta có 16 và 12 lần −1.

Ngoài ra, ta thu được 7 lần +1 trong cột BS, rồi 5 lần và 3 lần +1 tương

ứng trong các cột BE và SE. Cuối cùng ta được 2 lần −1 trong cột cuối

31

cùng. Nên điều này chính là biểu diễn (2.6). Công thức này được gọi là

công thức bao hàm loại trừ hay công thức sàng lọc. Từ đầu tiên trong tên

đầu là rõ ràng, từ thứ hai ám chỉ rằng ta bắt đầu với một tập lớn và sau

đó loại bỏ những số mà ta không muốn đếm.

Ta có thể mở rộng phương pháp này nếu các sinh viên sưu tầm ảnh của

4 hoặc 5 hoặc bất kỳ nhóm nhạc nào. Thay vì phát biểu định lý tổng quát,

tôi đưa ra một số bài tâp.

Bài toán 2.5.1. Trong lớp toàn bạn nam, 18 bạn nam thích chơi cờ vua,

23 bạn thích bóng đá, 21 bạn thích đạp xe và 17 bạn thích chạy dai sức.

Số người thích chơi cờ vua và bóng đá là 9. Ta cũng biết rằng 7 bạn nam

thích chơi cờ và đạp xe, 6 bạn thích cờ và chạy dai sức, 9 bạn thích bóng

đá và chạy dai sức, và cuối cùng 12 bạn thích đạp xe và chạy dai sức. Có

4 bạn thích cờ, bóng đá và đạp xe, 3 bạn thích cờ, bóng đá và chạy dai

sức, 5 bạn thích cờ, đạp xe và chạy dai sức, 7 bạn thích bóng đá, đạp xe

và chạy dai sức. Cuối cùng có 3 bạn thích cả 4. Ngoài ra ta biết rằng mọi

đều thích ít nhất một trong các môn trên. Hỏi cả lớp có bao nhiêu bạn?

2.6 Một số bài toán tổ hợp

2.6.1 Nguyên lý chuồng chim bồ câu

Liệu chúng ta có thể tìm thấy tại New York hai người có cùng một số

sợi tóc? Có người sẽ nghĩ rằng không thể trả lời câu hỏi này, vì thậm chí

ta còn không biết có bao nhiêu sợi tóc có trên đầu của một người. Hãy bỏ

qua số các sợi tóc trên đầu mỗi người đang sống ở New York (mà khá khó

khăn để có số chính xác). Nhưng có một số sự kiện mà chúng ta biết chắc

chắn là: Không ai có nhiều hơn 500.000 sợi tóc (một khảo sát khoa học),

và có hơn 10 triệu cư dân của New York. Bây giờ ta có thể trả lời câu hỏi

ban đầu chưa? Có. Nếu không có người nào có cùng số tóc, thì phải có

32

nhiều nhất một người có 0 sợi, nhiều nhất một người có đúng 1 sợi, và tiếp

tục như vậy. Cuối cùng, sẽ có nhiều nhất một người có đúng 500.000 sợi.

Nhưng tiếp theo đó điều này có nghĩa rằng không có nhiều hơn 500.001 cư

dân ở New York. Vì điều này mâu thuẫn những gì chúng ta biết về New

York, suy ra rằng phải có hai người có cùng số lượng sợi tóc.

Ta có thể công thức hóa điều này như sau. Hãy tưởng tượng 500.001 hộp

lớn (hoặc chuồng chim bồ câu). Người đầu tiên được dán nhãn "người dân

New York không có sợi tóc nào", người tiếp theo được dán nhãn "người

dân New York có 1 sợi tóc", và tiếp tục như vậy. Hộp cuối cùng được dán

nhãn "người dân New York có 500.000 sợi tóc". Bây giờ nếu tất cả mọi

người đi vào các hộp thích hợp, sau đó khoảng 10 triệu người dân New

York được ghi nhận đã vào đứng một số hộp (hoặc chuồng). Vì ta chỉ có

500.001 hộp, chắc chắn sẽ có một hộp chứa nhiều hơn một người dân New

York. Khẳng định này là hiển nhiên, nhưng nó là một công cụ rất thường

xuyên và mạnh mẽ, vì vậy ta công thức hóa nó trong bài toán tổng quát:

Nếu chúng ta có n hộp và ta đặt nhiều hơn n đồ vật vào các hộp,

khi đó sẽ có ít nhất một hộp có chứa nhiều hơn một vật.

Phát biểu trên thường được công thức hóa bằng cách sử dụng chim bồ

câu và chuồng của chúng, và được gọi là Nguyên lý chuồng chim bồ câu.

Nguyên lý chuồng chim bồ câu thực sự đơn giản: Mọi người đều hiểu nó

ngay lập tức. Tuy nhiên, nó xứng đáng được mang một cái tên, vì chúng ta

sử dụng nó rất nhiều như công cụ cơ bản trong nhiều chứng minh. Chúng

ta sẽ thấy nhiều ví dụ cho việc sử dụng nguyên lý chuồng chim bồ câu,

nhưng để thấy sức mạnh của nó, ta sẽ thảo luận ngay một ví dụ. Đây

không phải là một định lý với bất kỳ ý nghĩa nào; đúng hơn, nó là một

bài tập có lời giải được đưa ra một cách chi tiết.

Bài tập. Bắn 50 phát đạn vào một mục tiêu hình vuông, có cạnh dài 70

33

cm. Ta bắn súng thực sự tốt, bởi vì tất cả các phát bắn đều trúng mục tiêu.

Chứng minh rằng có hai lỗ đạn gần nhau hơn 15 cm.

Lời giải: Tưởng tượng rằng mục tiêu của chúng ta là một bàn cờ cũ. Một

hàng và một cột của nó đã bị mất đi, do đó, nó có 49 ô vuông. Cái bàn cờ

bị bắn 50 phát, vì vậy phải có một ô vuông bị bắn trúng hai lần (đặt các

lỗ đạn trong các chuồng chim bồ câu). Ta kết luận rằng có hai lỗ gần với

nhau hơn 15 cm.

Cạnh các ô vuông hiển nhiên bằng 10 cm, các đường chéo của chúng

√

bằng nhau và bằng

200 ≈ 14, 1 cm. Ta sẽ chỉ ra rằng:

Hai lỗ đạn không thể cách nhau lớn hơn độ dài đường chéo. (*)

Một cách trực quan hai điểm của ô vuông có khoảng cách lớn nhất là các

đỉnh của đường chéo, nhưng trực giác dễ gây hiểu nhầm, ta cần chứng

minh nó. Giả sử hai điểm P và Q cách nhau nhiều hơn độ dài của các

đường chéo. Cho A, B, C, và D là các đỉnh của hình vuông. Nối P và Q

bằng một đường thẳng, và lấy P (cid:48) và Q(cid:48) là hai điểm mà đường thẳng này

cắt cạnh hình vuông (Hình 2.1). Khi đó khoảng cách của P (cid:48) và Q(cid:48) thậm

Hình 2.1: Hai lỗ đạn trong cùng một hình vuông

chí còn lớn hơn, vì vậy nó cũng lớn hơn các đường chéo.

Không giảm tính tổng quát, ta có thể giả sử rằng P (cid:48) thuộc cạnh AB

34

(nếu ngược lại, ta đổi cách đặt tên các đỉnh hình vuông). Một trong các

góc Q(cid:48)P (cid:48)A và Q(cid:48)P (cid:48)B nhỏ nhất là 90o; không giảm tính tổng quát, ta có

thể giả sử góc này là góc Q(cid:48)P (cid:48)A. Khi đó đoạn AQ(cid:48) là cạnh của tam giác

Q(cid:48)P (cid:48)A đối với góc lớn nhất, nên nó còn lớn hơn P (cid:48)Q(cid:48), và do vậy nó lớn

hơn đường chéo.

Ta lập luận như trên để chỉ ra nếu ta thay Q(cid:48) bằng một trong các đầu

mút của cạnh chứa nó, ta thu được một đoạn mà dài hơn đường chéo,

nhưng bây giờ ta có một đoạn thẳng mà hai đầu mút là các đỉnh hình

vuông. Nên đoạn này hoặc là cạnh hình vuông, hoặc là đường chéo hình

vuông, và trong bất kỳ trường hợp nào thì nó dài hơn đường chéo! Mâu

thuẫn này chỉ ra rằng khẳng định (*) phải đúng.

Do đó không những hai lỗ đạn gần hơn 15 cm, mà thậm chí còn gần

hơn 14,2 cm. Suy ra lời giải của bài tập.

Nếu đây là lần đầu tiên bạn thấy cách chứng minh này, bạn có thể ngạc

nhiên: ta không trực tiếp chứng minh điều ta muốn, mà thay vào đó ta giả

sử rằng khẳng định không đúng, và tiếp theo dùng giả sử thêm vào này,

ta lập luận cho tới khi mâu thuẫn. Dạng chứng minh này được gọi là gián

tiếp (phản chứng), và nó được sử dụng khá thường xuyên trong toán học.

(Các nhà toán học là các sinh vật kỳ lạ, ta thấy rằng: Họ đi vào tranh luận

dài dựa trên những giả định họ biết là sai, và khoảnh khắc hạnh phúc của

họ là khi họ tìm thấy một sự mâu thuẫn giữa các phát biểu họ đã chứng

minh.)

Bài toán 2.6.1. Chứng minh rằng ta có thể chọn 20 người New Yorker

có cùng số tóc.

2.6.2 Nghịch lý anh em sinh đôi và hàm Logarit

Sau khi dạy nguyên lý chuồng chim bồ câu trên lớp học của mình, vị

35

giáo sư quyết định chơi một trò chơi nhỏ: "Tôi đặt cược rằng trong lớp có

hai bạn có cùng ngày sinh! Các bạn nghĩ thế nào?" Một số sinh viên trả

lời ngay:" Có 366 sinh nhật có thể, vì vậy thầy chỉ có thể thắng nếu có ít

nhất 367 người trong lớp học! Nhưng chỉ có 50 sinh viên, và như vậy thầy

sẽ mất tiền cược." Tuy nhiên, giáo sư nài nỉ cá cược, và ông đã thắng.

Làm thế nào chúng ta có thể giải thích điều này? Điều đầu tiên để nhận

ra đó là Nguyên lý chuồng chim bồ câu nói với ta rằng, với 367 học sinh

trong các lớp học,vị giáo sư luôn luôn thắng cược. Nhưng điều này là không

thú vị; với ông chỉ cần có một cơ hội tốt để giành chiến thắng. Với 366

sinh viên, ông đã có thể thua; liệu có thể là chỉ với 50 sinh viên, ông vẫn

có một cơ hội tốt để chiến thắng?

Câu trả lời đáng ngạc nhiên là ngay cả với ít nhất là 23 sinh viên, cơ

hội chiến thắng là lớn hơn 50%. Chúng ta có thể xem sự kiện này như một

"nguyên lý xác suất chuồng chim bồ câu", nhưng tên thông thường của

nó là nghịch lý anh em sinh đôi.

Ta thử xác định cơ hội thắng của giáo sư. Giả sử trên danh sách lớp,

ông viết sinh nhật của mọi người. Vì vậy, ông đã có một danh sách 50 sinh

nhật. Chúng ta biết rằng có 36650 danh sách khác nhau như thế này.

Có bao nhiêu danh sách mà vị giáo sư thua? Một lần nữa, ta biết rằng:

366 · 365 · · · 317. Vậy xác suất vị giáo sư thua cược là

366 · 365 · · · 317 36650

Ta có thể cố gắng tính toán giá trị này bằng nỗ lực, hoặc bằng cách sử

dụng một máy tính (hoặc chỉ cần một máy tính có lập trình), nhưng sẽ

hữu ích hơn nhiều nếu ta tìm được giới hạn trên và giới hạn dưới bằng

một phương pháp sử dụng được trong một trường hợp tổng quát hơn, khi

chúng ta có n ngày sinh nhật và k sinh viên. Nói cách khác, thương số sau

lớn cỡ nào

?

n(n − 1) · · · (n − k + 1) nk

36

Để cho tiện ta lấy nghịch đảo (nó sẽ lớn hơn 1)

(2.7)

.

nk n(n − 1) · · · (n − k + 1)

Ta có thể rút gọn phân số bằng cách khử n, nhưng khi đó sẽ không còn

cách rõ ràng để tiếp tục. Một manh mối nhỏ có thể là số lượng các nhân

tử là giống nhau ở tử số và mẫu số, vì vậy chúng ta hãy cố gắng để viết

phần này thành các tích:

=

·

· · ·

.

nk n(n − 1) · · · (n − k + 1)

n n − 1

n n − 2

n n − k + 1

Các nhân tử này khá đơn giản, nhưng vẫn đủ khó để thấy tích của chúng

lớn cỡ nào. Các nhân tử đứng độc lập lớn hơn 1, nhưng rất gần 1 (ít nhất

là nhân tử đầu tiên). Nhưng có rất nhiều số trong số chúng, và tích của

chúng có thể lớn.

Ý tưởng sau sẽ giúp ích: Lấy logarit từng vế. Ta có

(cid:18) (cid:19) (2.8)

ln

nk n(n − 1) · · · (n − k + 1)

(cid:19) (cid:19) (cid:18) (cid:19) (cid:18) n (cid:18) n (2.9)

ln

+ ln

+ · · · + ln

.

n − 1

n − 2

n n − k + 1

(Thông thường, ta lấy loga cơ số tự nhiên, cơ số e = 2.71828 . . ..) Theo

cách này ta có thể làm việc với phép cộng thay vì phép nhân, sẽ tốt hơn;

nhưng các số hạng ta phải cộng lại trông xấu xí! Ta biết gì về các hàm

loga này?

Ta nhìn vào đồ thị của hàm loga (Hình 2.2). Ta cũng vẽ đường y = x−1.

Ta thấy rằng đồ thị của hàm nằm dưới đường thẳng, và chạm vào đường

thẳng tại x = 1 (kết quả này có thể được chứng minh bằng giải tích sơ

cấp). Nên ta có

(2.10)

ln x ≤ x − 1.

37

Hình 2.2: Đồ thị của hàm loga tự nhiên. Lưu ý gần 1, nó rất gần đường thẳng x − 1.

Ta có thể nói gì về cận trên này? Từ hình vẽ ta thấy ít nhất với các giá

trị của x gần 1, hai đồ thị thực sự gần nhau. Thật ra, ta có thể tính toán

như sau: (cid:19) (2.11)

ln x = − ln

≥ −

− 1

=

.

1 x

(cid:18) 1 x

x − 1 x

x chỉ hơi nhỏ hơn

Nếu x hơi lớn hơn 1 (như các giá trị trong (2.9)), thì x−1

x − 1, và cận trên trong (2.10) và cận dưới trong (2.11) gần nhau.

Các cận của hàm loga rất hữu ích trong nhiều ứng dụng mà ta phải xấp

xỉ tính toán với hàm loga và ta nên phát biểu chúng thành bổ đề riêng.

(Một bổ đề là một phát biểu toán học chính xác, giống như định lý, ngoài

trừ nó không có mục tiêu tự thân, nhưng một số kết quả bổ sung cùng với

cách chứng minh của định lý. Tất nhiên, một số bổ đề còn thú vị hơn một

số định lý!)

Bổ đề 2.6.1. Với mọi x > 0,

≤ ln x ≤ x − 1.

x − 1 x

Đầu tiên ta sử dụng cận dưới của bổ đề này để đánh giá (2.9) từ bên

dưới. Với một số hạng tiêu biêu trong tổng trong (2.9) ta có

(cid:19) (cid:18) n

≥

=

,

ln

n − j

j n

n n−j − 1 n n−j

38

và do đó (cid:18) (cid:19)

ln

≥

+

+ · · · +

nk n(n − 1) · · · (n − k + 1)

2 n

k − 1 n

=

(1 + 2 + · · · + (k − 1)) =

1 n 1 n

k(k − 1) 2n

Do đó ta có một cận dưới của (2.9). Để tìm cận trên, ta có thể dùng một

bất đẳng thức trong Bổ đề 2.6.1; với một số hạng thông thường, ta có

(cid:19) (cid:18) n

≤

ln

− 1 =

.

n − j

n n − 1

j n − j

Ta phải cộng lại với j = 1, . . . , k − 1 để thu được cận trên của (2.9). Việc

này không dễ như trong trường hợp trên, vì các mẫu số thay đổi. Nhưng ta

chỉ cần cận trên, nên ta có thể thay mẫu số bằng giá trị nhỏ nhất mà nó có

thể nhận với các giá trị j, cụ thể n−k +1. Ta có j/(n−j) ≤ j/(n−k +1),

và do đó (cid:18) (cid:19)

ln

+ · · ·

≤

+

nk n(n − 1) · · · (n − k + 1)

2 n − k + 1

k − 1 n − k + 1

(1 + 2 + · · · + (k − 1))

=

=

.

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

Do đó ta có các cận trên và cận dưới đồng dạng của hàm logarit của tỉ số

k(k−1)

k(k−1)

(2.7), và áp dụng hàm mũ vào cả hai vế, ta được

(2.12)

e

2n ≤

≤ e

2(n−k+1) .

n(n − 1) · · · (n − k + 1) nk

Việc trên có giúp hiểu kỹ xảo của vị giáo sư trong lớp học? Ta áp dụng

(2.12) với n = 366 và k = 50; dùng máy tính, ta được

28.4 ≤

≤ 47.7.

36550 366 · 364 · · · 317

(tính toán hơn nữa, ta có thể xác định giá trị chính xác là 33.414...) Nên

39

xác suất mà mọi sinh viên trong lớp có ngày sinh khác nhau (là nghịch

đảo của số này) nhỏ hơn 1/28. Điều này có nghĩa nếu vị giáo sư đi các

cược hàng năm, ông sẽ chỉ thất bại một hoặc hai lần trong nghề!

Bài toán 2.6.2. Tổng sau bằng bao nhiêu

+

+

· · · +

.

1 1 · 2

1 2 · 3

1 3 · 4

1 (n − 1) · n

Thực hành, đoán giá trị và chứng minh bằng quy nạp.

Bài toán 2.6.3. Tổng sau bằng bao nhiêu

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32)

0 ·

+ 1 ·

+ 2 ·

+ · · · + (n − 1) ·

+ n ·

(cid:33) .

n 0

n 1

n 2

n n − 1

n n

Thực hành, đoán giá trị và chứng minh. (Thử chứng minh giá trị này bằng

quy nạp và bằng toán tổ hợp.)

Bài toán 2.6.4. Chứng minh các đẳng thức sau

1 · 20 + 2 · 21 + 3 · 22 + · · · + n · 2n−1 = (n − 1)2n + 1.

13 + 23 + 33 + · · · + n3 =

.

1 + 3 + 9 + 27 + · · · + 3n−1 =

.

n2(n + 1)2 4 3n − 1 2

Bài toán 2.6.5. Chọn 38 số nguyên dương, tất cả đều nhỏ hơn 1000.

Chứng minh rằng tồn tại hai số sao cho có hiệu bằng 26.

2.6.3 Cách chia quà

Giả sử bạn có n món quà khác nhau, và bạn muốn phát cho k đứa trẻ,

trong đó với một số nguyên nhân, bạn được khuyên từng đứa trẻ nên có

nhiều gói quà. Do đó Adam có nAdam món quà, Barbara có nBarbara món

quà, v.v. Để tiện cho toán học, ta có thể gọi các đứa trẻ là 1, 2, . . . , k; do

40

đó ta có các số nguyên không âm n1, n2, . . . , nk.

Ta giả sử rằng n1 + n2 + · · · + nk = n, vì nếu ngược lại sẽ không có cách

chia tất cả gói quà cho các đứa trẻ theo đúng số của chúng.

Tất nhiên, câu hỏi là, có bao nhiêu cách chia quà?

Ta có thể tổ chức việc chia quà như sau. Ta trải tất cả các gói quà thành

một hàng có độ dài n. Đứa trẻ đầu tiên tiến đến và lấy n1 món quà đầu

tiên, bắt đầu từ bên trái. Sau đó đứa trẻ thứ hai tiến đến và lấy n2 món

quà, tiếp theo đứa trẻ thứ 3 đến và lấy tiếp n3 món quà v.v. Đứa trẻ thứ

k lấy nk món quà cuối cùng.

Rõ ràng ta có thể xác định ai lấy quà gì bằng cách sắp xếp các món

quà. Có n! cách xếp quà. Nhưng tất nhiên, số n! lớn hơn số cách chia quà,

vì nhiều cách xếp quà dẫn tới cùng kết quả (đó là, mỗi đứa trẻ thu được

cùng một tập gói quà). Câu hỏi là có bao nhiêu?

Nên ta bắt đầu bằng một cách chia quà, và đề nghị các đứa trẻ xếp quà

cho chúng ta, thẳng thành một hàng, bắt đầu với đứa trẻ đầu tiên, rồi tiếp

tục với đứa thứ hai, đứa thứ ba, v.v. Theo cách này ta lấy được một thứ

tự dẫn tới cách chia quà hiện tại. Đứa trẻ đầu tiên có thể xếp quà của nó

theo n1! thứ tự có thể, không quan tâm thứ tự nó đã chọn, đứa trẻ thứ

hai xếp quà của nó theo n2! cách, v.v. Do đó tổng số cách xếp quà là tích

của các giai thừa:

n1! · n2! · · · nk!.

Suy ra số cách chia quà là

.

n! n1! · n2! · · · nk!

2.6.4 Giải một số bài toán tổ hợp

Khi giải một bài toán tổ hợp cụ thể trước tiên cần làm rõ xem nó có

thể giải trực tiếp hay không bằng cách sử dụng các quy tắc tổng và tích.

41

Nếu lời giải như thế có vẻ khó khăn, cần lập một lược đồ toán học cho bài

toán đang xét, bằng cách xét xem trong bài toán có đả động đến việc lập

các tập hợp con hoặc các xâu hay không, có chấp nhận lặp hay không. Ta

đưa ra một số ví dụ giải những bài toán tổ hợp.

Bài toán 1. Từ thành phố A đến thành phố B có 5 con đường, từ

thành phố B đến thành phố C có 3 con đường. Hỏi có bao nhiêu

con đường từ A đến B và đi qua C?

Lời giải: Mỗi con đường như bài toán đòi hỏi được cho bởi một cặp (a, b),

trong đó a là một trong những con đường nối A với B, và b là một trong

những con đường nối B với C . Vì theo giả thiết, a có thể chọn bởi 5 cách

khác nhau, còn b bởi 3 cách, nên cặp (a, b) , theo quy tắc tích, có thể chọn

bởi 5.3=15 cách.

Bài toán 2. Có 6 cặp găng tay cỡ khác nhau. Có bao nhiêu cách

để chọn ra từ chúng một chiếc găng bên trái và một chiếc găng

bên phải sao cho hai chiếc này khác cỡ nhau?

Lời giải: Bài toán này cũng có thể giải theo quy tắc tích. Chiếc găng bên

trái có thể được chọn bởi 6 cách. Sau khi nó đã được chọn, chiếc găng bên

phải chỉ có thể chọn bởi 5 cách (vì các chiếc được chọn phải có cỡ khác

nhau). Vì thế có cả thảy 6.5 = 30 cách chọn. Một phương pháp khác giải

bài toán này là dựa trên công thức chỉnh hợp không lặp. Mỗi cách chọn có

thể cho bởi một cặp số khác nhau (a, b), trong đó 1 ≤ a ≤ 6, 1 ≤ b ≤ 6

6 = 6.5 = 30.

Số các cặp như vậy là A2

Bài toán 3. Có bao nhiêu cách để tạo một lá cờ gồm 3 giải nằm

ngang có màu khác nhau, nếu ta có các vật liệu 5 màu khác

nhau?

Lời giải: Ký hiệu 5 màu mà ta có bởi các chữ cái a, b, c, d, e. Khi đó một

42

lá cờ tùy ý sẽ được “số hóa” bởi một xâu từ 3 chữ cái khác nhau. Vì thế

số các lá cờ bằng số các chỉnh hợp không lặp chập 3 của 5 phần tử, tức là

A3

5 = 5.4.3 = 60.

Bài toán 4. Có bao nhiêu cách để tạo một lá cờ 4 màu gồm các

giải nằm ngang có 4 màu khác nhau?

Lời giải: Trong trường hợp này các lá cờ khác nhau chỉ sai khác về thứ

tự các màu. Số lá cờ như vậy bằng số các hoán vị của 4 phần tử, tức là

P4 = 4! = 24

Bài toán 5. Từ một bộ bài gồm 52 quân bài ta lấy ra 10 quân. Có

bao nhiêu cách khác nhau để làm việc đó? Có bao nhiêu trường

hợp trong số các quân bài này có ít nhất một quân át? Có bao

nhiêu trường hợp có đúng một quân át? Có bao nhiêu trường hợp

có đúng 4 quân át?

Lời giải: Mỗi một cách chọn 10 quân bài từ bộ bài là một cách chọn 10-tập

từ 52-tập. Số cách chọn được cho bởi:

(cid:32) (cid:33)

=

.

52 10

52! 10!.42!

Bài toán tìm số cách chọn mà trong các quân bài đã chọn có ít nhất một

quân át thoạt nhìn có vẻ phức tạp hơn: cần phân tích trường hợp khi có

một quân át, có đúng 2 quân át, đúng 3 quân át, đúng 4 quân át. Nhưng

đơn giản hơn là ta xét xem có bao nhiêu trường hợp mà trong các quân

bài đã chọn không có quân át nào, những trường hợp còn lại sẽ có ít nhất

một quân át. Nếu trong các quân bài đã chọn không có quân át nào thì

việc chọn không phải được tiến hành với 52 quân bài, mà chỉ với 48 quân

(tất cả các quân bài, trừ át), mà số cách chọn như vậy sẽ là

(cid:32) (cid:33)

48 10

43

Do đó số cách chọn có ít nhất một quân át sẽ là:

(cid:32) (cid:33) (cid:32)

−

(cid:33) .

52 10

48 10

Để tìm bao nhiêu trường hợp có đúng một quân át, ta tách việc chọn

các quân bài ra hai bước: trước hết từ 4 quân át chọn ra 1 quân, để làm (cid:1) cách. Sau đó trong 48 quân bài còn lại chọn 9 quân, điều việc này có (cid:0)4 1 này có thể làm với (cid:0)48 (cid:1) cách. Theo quy tắc tích ta thấy rằng có tất cả là 9 (cid:1) cách chọn. (cid:0)4 1

(cid:1) cách (cần (cid:1).(cid:0)48 9 Cuối cùng, cách chọn có 4 quân át có thể tiến hành với (cid:0)48 6

lấy 4 quân át rồi sau đó chọn 6 quân bài trong 48 quân còn lại).

Bài toán 6. Trong một nước nọ không có hai người dân nào có

bộ răng với những chiếc răng ở cùng vị trí như nhau. Hỏi dân số

tối đa có thể của nước đó là bao nhiêu” (số răng nhiều nhất là

32)?

Lời giải: Mỗi người dân của nước đó có thể tương ứng với một tập hợp con

của tập hợp X lập nên từ 32 cái răng, tùy thuộc người dân đó có những

chiếc răng ở vị trí nào. Số các tập hợp con của 32-tập bằng 232. Nghĩa là

trong nước đó không thể có quá 232 người dân.

n2...Pm

n1.P2

Bài toán 7. Giả sử P1, P2, ..., Pm là những số nguyên tố khác nm. Trong nhau. Có bao nhiêu ước số của số a = P1

km.

đó n1, n2, ..., nm là các số tự nhiên. (kể cả ước là 1 và a).

k1.P2

k2...Pm

Lời giải: Mỗi ước số của a có dạng b = P1

Trong đó 0 ≤ ki ≤ ni, 1 ≤ i ≤ m. Nghĩa là số mũ ki có thể nhận ni + 1

giá trị. Theo quy tắc tích, số các xâu (k1, k2, ..., km) bằng

(n1 + 1).(n2 + 1)...(nm + 1) và đó cũng là số ước của số a.

44

Bài toán 8. Có bao nhiêu cách đặt các quân trắng (2 con mã, 2

con tượng, 2 con xe, 1 con Hậu và 1 con Vua) lên hàng đầu tiên

của bàn cờ ?

Lời giải: Trong bai toán này cần tìm số xâu độ dài 8 có cấu tạo (2,2,2,1,1).

Số các xâu như vậy (tức là số các hoán vị có lặp) bằng:

P (2, 2, 2, 1, 1) =

.

8! 2!.2!.2!.1!.1!

Bài toán 9. Có bao nhiêu cách xếp 15 quả bi-a có đánh số vào 6

hàng ?

Lời giải: Với mỗi số từ 1 đến 15, nếu quả bi-a mang số đó được xếp vào

hàng nào thì ta đặt tương ứng số đang xét với số thứ tự của hàng đó. Như

vậy ta nhận được một xâu độ dài 15 lập nên từ các số 1, 2, 3, 4, 5, 6 (số

thứ tự các hàng). Số các xâu như vậy là 615

Bài toán 10. Trên mặt phẳng vẽ n đường thẳng, đồng thời không

có hai đường nào song song và không có ba đường nào đồng quy.

Tính số giao điểm của các đường thẳng đó.

Lời giải: Mỗi giao điểm được xác định một cách duy nhất bởi cặp đường

thẳng đi qua nó. Đồng thời thứ tự của các đường thẳng không đóng vai

(cid:1). trò gì. Vì thế số giao điểm cần tìm bằng số các tổ hợp chập 2 của n, tức là bằng (cid:0)n 2

Bài toán 11. Trên một trong hai đường thẳng song song ta đánh

dấu 10 điểm, trên đường thẳng còn lại đánh dấu 7 điểm. Mỗi

điểm của đường thẳng này được nối với mỗi điểm của đường

thẳng kia. Tìm số giao điểm của các đoạn thẳng nhận được, nếu

không có ba đoạn thẳng nào có điểm chung (không kể những điểm

45

chung tại các đầu mút của các đoạn thẳng).

Lời giải: Bằng cách vẽ hình ta nhận thấy rằng giao điểm tùy ý xác định

duy nhất nếu cho một cặp điểm trên đường thẳng này và một cặp điểm

trên đường thẳng còn lại. Đồng thời thứ tự các điểm trên các đường thẳng

không đóng vai trò gì. Như vậy trong cả hai trường hợp ta đều chỉ cần

tính đến việc chọn các tập hợp con. Nhưng từ 10-tập có thể chọn được (cid:1) 2-tập con. Theo quy tắc (cid:0)10 2 (cid:1) 2-tập con và từ 7-tập có thể chọn được (cid:0)7 2

(cid:32) (cid:33)

= 495.

tích ta thấy số giao điểm cần tìm là: (cid:32) (cid:33) 7 . 2

10 2

Bài toán 12. Có bao nhiêu cách để chia n cái kẹo giống nhau cho

m đứa trẻ? (Chấp nhận cả trường hợp có đứa trẻ không nhận

được kẹo)

Lời giải: Gọi x1, x2, ..., xm lần lượt là số kẹo mà đứa trẻ thứ 1, thứ 2, ...,

thứ m nhận được. Ta có

x1 + x2 + ... + xm = n.

(trong đó x1, x2, ..., xm nguyên, không âm).

Đặt ai = xi + 1, 0 ≤ i ≤ m, ta có phương trình

(12)

a1 + a2 + ... + am = n + m.

Bài toán trở thành tìm số nghiệm nguyên dương của phương trình (12).

Kết quả là (cid:32)

(cid:33) .

n + m − 1 m − 1

Bài toán 13. Có bao nhiêu cách chọn ra bộ 8 cái bánh ngọt, nếu

46

có 4 loại bánh khác nhau? (mỗi loại có ít nhất 8 cái bánh).

Lời giải: Vì trong bài toán này thứ tự những chiếc bánh ngọt không có vai

trò gì, nên mỗi bộ là một xâu độ dài 8 từ 4 phần tử (là tên các loại bánh),

đồng thời thứ tự các thành phần của xâu không có vai trò gì. Bài toán trở

thành: Đếm số nghiệm nguyên không âm của phương trình

x1 + x2 + x3 + x4 = 8.

Trong đó xi là số bánh loại i. Đặt ai = xi + 1, 0 ≤ i ≤ 4, ta có phương

trình

(13)

a1 + a2 + a3 + a4 = 8 + 4.

Từ cách đếm số nghiệm nguyên dương của phương trình (13). Tìm được

số cách chọn ra bộ 8 bánh là

(cid:32) (cid:33)

= 165.

11 3

Bài toán 14. Có bao nhiêu người tham gia trong cuộc dã ngoại,

nếu biết rằng, 16 người trong họ mang theo bánh mỳ kẹp giăm

bông, 24 người mang bánh mỳ kẹp giò, 15 người mang bánh mỳ

kẹp pho mát, 11 người vừa mang bánh mỳ kẹp giăm bông, vừa

mang bánh mỳ kẹp giò, 8 người vừa mang bánh mỳ kẹp giăm

bông, vừa mang bánh mỳ kẹp pho mát, 12 người vừa mang bánh

mỳ kẹp giò vừa mang bánh mỳ kẹp pho mát, 6 người mang cả

ba loại bánh mỳ kẹp, còn 5 người không mang bánh mỳ kẹp mà

mang bánh ngọt?

Lời giải: Ký hiệu A là tập hợp những người tham gia có mang theo bánh

mỳ kẹp giăm bông, B là tập những người mang bánh mỳ kẹp giò, và C tập

47

những người mang bánh mỳ kẹp pho mát, D là tập những người không

mang bánh mì mà mang bánh ngọt. Khi đó giả thiết của bài toán có thể

viết như sau:

n(A) = 1, n(B) = 24, n(C) = 15

n(A ∩ B) = 11, n(A ∩ C) = 8, n(B ∩ C) = 12

n((A ∩ B ∩ C) = 6, n(D) = 5

Ta tìm n(A ∪ B ∪ C) tức là số người tham gia dã ngoại mà mang theo

một trong ba loại bánh mỳ kẹp. Từ công thức (4) ta nhận được:

n(A∪B∪C) = n(A)+n(B)+ n(C)−n(A∩B)−n(B∩C)−n(C∩A)+n(A∩B∩C)

= 16+24+15-11-8-12+6=30.

Như vậy có 30 người mang theo bánh mỳ kẹp, và tổng số người tham gia

dã ngoại là 30+5=35.

2.7 Hệ số nhị thức và tam giác Pascal

Issai Schur nghiên cứu nhiều bài toán về hệ thức giữa hàm phân bố không điểm và độ lớn của hệ số đa thức trên Zn. Công trình của ông khai sinh ra một hướng quan trọng trong giải tích và lý thuyết số. Chúng ta ôn

lại và phát triển một số kết quả gần đây về bài toán Schur.

(cid:1) và gọi chúng là hệ số nhị thức. Trong mục 2.4 ta đã giới thiệu số (cid:0)n k

Bây giờ ta giải thích cái tên này: nó có nguồn gốc từ một công thức rất

nổi tiếng trong đại số liên quan đến chúng, mà ta sẽ thảo luận sau đây.

Vấn đề là tính lũy thừa của biểu thức đại số rất đơn giản (x + y). Ta

bắt đầu với các ví dụ:

(x + y)2 =x2 + 2xy + y2,

(x + y)3 = (x + y) · (x + y)2 = (x + y) · (x2 + 2xy + y2)

= x3 + 3x2y + 3xy2 + y3,

48

và tiếp tục như vậy,

(x + y)4 = (x + y) · (x + y)3 = x4 + 4x3y + 6x2y2 + 4xy3 + y4.

Các hệ số này là đã gặp. Trong bài tập trước đó ta đã nhìn thấy chúng là (cid:1). Chúng ta minh họa cho lập luận bằng giá trị n tiếp theo, cụ các số (cid:0)n k thể là n = 5, nhưng nó đúng trong tổng quát.

Ta muốn khai triển

(x + y)5 = (x + y)(x + y)(x + y)(x + y)(x + y)

sao cho ta xóa được hết các dấu ngoặc. Ta thu được mỗi số hạng trong khai

triển bằng cách chọn một trong hai số của mỗi nhân tử, và nhân chúng

lại. Nếu ta chọn x, ví dụ 2 lần, thì ta phải chọn y 3 lần, nên ta được x2y3.

Có bao nhiêu lần ta được cùng số hạng như vậy? Rõ ràng, nhiều bằng số

cách chọn các nhân tử cung cấp y (phân còn lại cung cấp x). Do đó ta (cid:1) cách. phải chọn 3 trong 5, và có thể làm theo (cid:0)5 3

Cho nên khai triển của (x + y)5 sẽ như sau:

(cid:33) (cid:33) (cid:33)

(x + y)5 =

x5 +

x4y +

x3y2 +

x2y3 +

xy4 +

y5.

(cid:32) 5 0 (cid:32) 5 1 (cid:33) (cid:32) 5 2 (cid:32) 5 3 (cid:33) (cid:32) 5 4 (cid:33) (cid:32) 5 5

Ta có thể áp dụng lập luận này để thu được Định lý nhị thức:

(cid:1). Nói cách khác, ta có đẳng thức

Định lý 2.7.1. (Định lý nhị thức) Hệ số của xn−kyk trong khai triển (x + y)n là (cid:0)n k (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:32) (cid:33)

(x+y)n =

xn+

xn−1y+

xn−2y2+· · ·+

xyn−1+

yn.

n 0

n 1

n n − 1

n n

n 2

Đẳng thức quan trọng này được khám phá bởi nhà thơ, nhà toán học

nổi tiếng người Ba Tư Omar Khayyam. Tên của nó xuất phát từ tiếng Hy

49

Lạp binome để biểu diễn những thứ có hai số hạng, trong trường hợp này

(cid:1) trong định lý này là nguồn gốc là x + y. Sự xuất hiện của các con số (cid:0)n k

của tên chúng: hệ số nhị thức.

Định lý nhị thức có thể được áp dụng theo nhiều cách khác nhau để thu

được các đẳng thức liên quan đến hệ số nhị thức. Ví dụ, ta thay x = y = 1.

Khi đó, ta được đẳng thức (2.5):

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32)

(2.13)

2n =

+

+

+ · · · +

+

(cid:33) .

n 0

n 1

n 2

n n − 1

n n

Sau này, ta sẽ xét các ứng dụng tinh xảo của ý tưởng này. Tạm thời, một

bước ngoặt được trình bày trong bài tập 2.7.2.

Bài toán 2.7.1. Dựạ vào (2.4), chứng minh định lý nhị thức bằng phương

pháp quy nạp.

Bài toán 2.7.2. (a) Chứng minh công thức

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)

−

+

−

+ · · · = 0.

n 0

n 1

n 2

n 3

(b) Công thức trên có đúng nếu n lẻ. Tại sao?

2.7.1 Tam giác Pascal

Để nghiên cứu nhiều tính chất khác nhau của hệ số nhị thức, bức ảnh

(cid:1); ở hàng đầu tiên, ta đặt (cid:0)1 0

dưới đây là rất có ích. Ta xếp tất cả các hệ số nhị thức thành một sơ đồ tam giác: hàng thứ "không" ta đặt (cid:0)n (cid:1); (cid:1) và (cid:0)1 1 0 (cid:1); v.v. Tổng quát, hàng thứ n chứa các (cid:1), và (cid:0)2 (cid:1), (cid:0)2 trong hàng thứ hai, (cid:0)2 2 1 0 (cid:1). Ta dịch chuyển các hàng sao cho trung điểm của mỗi số (cid:0)n 0 (cid:1), . . ., (cid:0)n n (cid:1), (cid:0)n 1

hàng thẳng nhau, bằng cách này ta thu được một mô hình giống kim tự

tháp, và được gọi là tam giác Pascal (đặt tên theo nhà toán học và vật lý

50

Pháp Blaise Pascal, 1632 - 1662). Hình bên dưới chỉ là một phần nhỏ của

tam giác Pascal.

(cid:1) (cid:0)0 0 (cid:1) (cid:1) (cid:0)1 1 (cid:0)1 0 (cid:1) (cid:1) (cid:0)2 1 (cid:0)2 0 (cid:1) (cid:0)2 2 (cid:1) (cid:1) (cid:1) (cid:0)3 0 (cid:0)3 1 (cid:1) (cid:0)3 2 (cid:0)3 3 (cid:1) (cid:1) (cid:1) (cid:0)4 0 (cid:1) (cid:0)4 3 (cid:0)4 1 (cid:0)4 4

(cid:1) (cid:0)4 2 Ta có thể thay mỗi hệ số nhị thức bằng giá trị số của nó để được một dạng

tam giác Pascal khác (viết thêm một số hàng)

1 1 1 2 1 1 3 3 1 1 6 4 4 1 1 10 10 5 1 5 1 15 20 15 6 1 6 1

2.7.2 Công thức trong tam giác Pascal

Cùng nhìn vào tam giác Pascal, không khó để thấy tính chất quan trọng

nhất của nó: Mọi số trong nó (trừ các số 1 ở biên) là tổng của hai số ngay

trên nó. Thật ra, đây là một tính chất của hệ số nhị thức mà ta đã gặp,

cụ thể là phương trình (2.4) trong Mục 2.4:

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32)

(2.14)

=

+

(cid:33) .

n k

n − 1 k − 1

n − 1 k

tính chất của tam giác cho phép ta xây dựng tam giác một cách nhanh

chóng theo từng hàng. Nó cũng cho ta một công cụ để chứng minh nhiều

tính chất của hệ số nhị thức.

Một ứng dụng đầu tiên, ta đưa ra lời giải mới cho bài tập 2.7.2. Nhiệm

vụ là chứng minh

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)

(2.15)

−

+

−

+ · · · = 0.

n 0

n 1

n 3

n 2

51

(cid:1) (đều bằng 1), (cid:0)n 1 (cid:1) bằng (cid:0)n−1 0 (cid:1) bằng (cid:0)n−1 0 (cid:1), thay (cid:0)n 2 (cid:1) + (cid:0)n−1 1

(cid:1), v.v. Do vậy ta được tổng bằng định lý nhị thức. Bây giờ ta chứng minh dựa vào (2.14): ta có thể (cid:1) bằng thay (cid:0)n 0 (cid:1) + (cid:0)n−1 (cid:0)n−1 2 1

(cid:32) (cid:33) (cid:34)(cid:32) (cid:33) (cid:32) (cid:33)(cid:35) (cid:34)(cid:32) (cid:33) (cid:32) (cid:33)(cid:35)

−

+

+

+

n − 1 0

n − 1 1

n − 1 0 (cid:34)(cid:32)

n − 1 1 (cid:32)

(cid:33) (cid:33)(cid:35) (cid:32)

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

+

+ (−1)n

n − 1 2 (cid:33) ,

n − 1 n − 2

n − 1 n − 1

n − 1 n − 1

và rõ ràng bằng 0, vì số hạng thứ hai trong mỗi cặp ngoặc vuông đối với

số hạng đầu tiên trong cặp ngoặc vuông tiếp theo.

Phương pháp này đưa ra nhiều hơn một chứng minh của công thức. Ta

sẽ có được gì nếu ta bắt đầu bằng cách tương tự, cộng và trừ hệ số nhị

thức thay phiên, nhưng dừng lại sớm hơn? Viết lại công thức này ta có

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32)

−

+

−

+ · · · + (−1)k

(cid:33) .

n 0

n 1

n 2

n 3

n k

Nếu ta làm tương tự trên, ta được

(cid:32) (cid:33) (cid:34)(cid:32) (cid:33) (cid:32) (cid:33)(cid:35) (cid:34)(cid:32) (cid:33) (cid:32) (cid:33)(cid:35)

−

+

+

+

n − 1 0

n − 1 1

n − 1 2

n − 1 0 (cid:34)(cid:32)

n − 1 1 (cid:32)

(cid:33) (cid:33)(cid:35)

+ · · · + (−1)k

+

.

n − 1 k − 1

n − 1 k

(cid:1). Ở đây một lần nữa các số hạng khử lẫn nhau, ngoại trừ số hạng cuối cùng, nên kết là (−1)k(cid:0)n−1 k

Có nhiều hệ thức đáng ngạc nhiên khác được thỏa mãn bằng tam giác

Pascal. Ví dụ, ta thử tìm tổng bình phương các số hạng một hàng bằng

52

bao nhiêu?

Ta thử với các hàng đầu tiên:

12 = 1,

12 + 12 = 2,

12 + 22 + 12 = 6,

12 + 32 + 32 + 12 = 20,

12 + 42 + 62 + 42 + 12 = 70.

Ta nhận thấy các kết quả thu được trùng với số hạng ở cột giữa của tam

giác Pascal. Tất nhiên, chỉ hàng chẵn mới chứa phần tử ở cột giữa, nên

giá trị cuối cùng ở trên, tổng bình phương trong hàng thứ 4 là phần tử ở

giữa của hàng thứ 7. Nên các ví dụ bên trên gợi ý công thức sau:

(cid:32) (cid:33)2 (cid:32) (cid:33)2 (cid:32) (cid:33)2 (cid:32) (cid:33)2 (cid:32) (cid:33)2 (cid:32) (cid:33)

(2.16)

+

+

+ · · · +

+

=

n 0

n 1

n 2

n n − 1

n n

2n n

Hiển nhiên chỉ một vài ví dụ trên không thể chứng minh công thức đúng,

nên ta cần phải chứng minh.

Ta sẽ đưa ra minh họa cho cả hai vế của công thức bằng bài toán đếm;

kết quả sẽ là chúng cùng đếm một thứ, và do vậy chúng bằng nhau. Hiển

nhiên vế phải đếm: số tập con có kích thướng n của tập có kích thước 2n.

Để cho tiện, chọn tập S = {1, 2, . . . , 2n} là tập có 2n phần tử của ta.

Minh họa tổ hợp cho vế trái không dễ dàng gì. Xét một số hạng thông (cid:1)2. Ta khẳng định rằng đây là số tập con n phần tử thường, ví dụ (cid:0)n k của tập {1, 2, . . . , 2n} mà chứa đúng k phần tử từ {1, 2, . . . , n} (nửa đầu

của tập S). Thật ra, làm thế nào ta chọn tập con có n phần tử như

53

vậy? Ta cọn k phần tử từ {1, 2, . . . , n} và sau đó chọn n − k phần tử từ {n + 1, n + 2, . . . , 2n}. Việc đầu tiên có (cid:0)n (cid:1) cách, không quan trọng k phần k (cid:1) cách chọn n − k phần tử còn tử của {1, 2, . . . , n} được chọn, ta có (cid:0) n n−k lại. Do đó số cách chọn tập con có n phần tử của S mà có k phần tử thuộc

{1, 2, . . . , n} là

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)2

·

=

n k

n n − k

n k

(do tính đối xứng của tam giác Pascal).

Bây giờ, ta được tổng số tập con n phần tử của S, ta phải cộng các số

này với k = 0, 1, . . . , n. Ta chứng minh được đẳng thức (2.16).

Bài toán 2.7.3. Chứng minh công thức (2.5)

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32)

2n =

+

+

+ · · · +

+

(cid:33) ,

n 2

n n − 1

n n

n 0

n 1

dựa theo chứng minh của (2.15).

Bài toán 2.7.4. Theo định lý nhị thức, vế phải trong đẳng thức (2.16)

là hệ số của xnyn trong khai triển (x + y)2n. Viết (x + y)2n dưới dạng

(x + y)n(x + y)n, khai triển cả hai nhân tử (x + y)n bằng định lý nhị thức,

và thử tính hệ số của xnyn trong tích này. Chứng minh rằng đây là một

54

chứng minh khác của (2.16).

KẾT LUẬN

Luận văn gồm những nội dung chính sau đây:

1/ Trình bày phương pháp quy nạp toán học. Đặc biệt giới thiệu phương

pháp quy nạp như một phương pháp để phát hiện ra các mệnh đề toán

học, chứ không đơn thuần là một phương pháp chứng minh mệnh đề cho

trước.

2/ Giới thiệu một số nguyên lý cơ bản của tổ hợp, nhưng với phương

pháp dẫn dắt từ những bài toán đơn giản, nhằm giúp người đọc nắm được

bản chất vấn đề.

3/ Đưa ra một hệ thống bài tập rèn luyện.

Luận văn có thể làm tài liệu tham khảo cho học sinh giỏi và giáo viên

như một nhập môn vào Tổ hợp và quy nạp.

Hà Nội, tháng 4 năm 2016

Tác giả

55

Lê Thị Thọ

Tài liệu tham khảo

[1] D. Djukic, V. Jankovic, I. Matic, N. Petrovic, The IMO Compendium;

A Collection of Problems Suggested for the International Mathemat-

ical Olympiads: 1959–2004, Springer, 2006.

[2] L. Lovasz, J. Pelikan, K. Vesztergombi, Discrete Mathematics: Ele-

mentary and Beyond, Springer, 2003.

56

[3] N. Ia. Vilenkin. Tổ hợp và quy nạp, Tủ sách Spunik, 2015.