Luận văn Thạc sĩ Khoa học: Nâng cao hiệu quả bài toán sắp xếp với giải thuật song song

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

- - - - - - - - - - - - - - - - - -

NGUYỄN NGỌC MAI

MỘT VÀI NGUYÊN LÝ

VÀ

BÀI TOÁN TỔ HỢP

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

HÀ NỘI- 2014

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

- - - - - - - - - - - - - - - - - -

NGUYỄN NGỌC MAI

MỘT VÀI NGUYÊN LÝ

VÀ

BÀI TOÁN TỔ HỢP

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP

Mã số: 60460113

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

Người hướng dẫn khoa học

PGS. TS. ĐÀM VĂN NHỈ

HÀ NỘI- 2014

Mục lục

Mở đầu

1 Kiến thức chuẩn bị

1.1 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . 1.2 Hai quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . 1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . 1.5.2 Ứng dụng trong số học . . . . . . . . . . . . . . 1.6 Nhị thức Newton . . . . . . . . . . . . . . . . . . . . . 1.7 Đồ thị cây . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 8 9 11 14 14 16 18 20

2 Một vài nguyên lý trong tổ hợp

26 26 2.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . 2.1.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . 26 2.1.2 Nguyên lý Dirichlet áp dụng trong hình học tổ hợp 31 34 42 51

2.2 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . 2.3 Nguyên lý cực hạn . . . . . . . . . . . . . . . . . . . . . 2.4 Nguyên lý bất biến . . . . . . . . . . . . . . . . . . . .

3 Một vài đồng nhất thức trong tổ hợp

3.1 Xây dựng đồng nhất thức qua hệ phương trình . . . . . . . . . . . . . . 3.2 Xây dựng đồng nhất thức qua số phức 3.3 Xây dựng đồng nhất thức qua hàm sinh . . . . . . . . . 3.3.1 Khái niệm hàm sinh . . . . . . . . . . . . . . . . 3.3.2 Một số đồng nhất thức liên quan đến hàm sinh . 3.3.3 Ứng dụng của hàm sinh . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . .

60 60 66 69 70 70 71 77 78

Lời cảm ơn

Tôi xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến PGS.TS Đàm Văn Nhỉ. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình tôi thực hiện đề tài.

Tôi xin gửi lời cảm ơn chân thành tới các thầy cô Khoa Toán - Cơ - Tin học, Phòng Sau đại học - Trường Đại học Khoa học Tự nhiên- Đại học Quốc gia Hà Nội; các thầy cô đã tham gia giảng dạy khóa cao học 2011-2013.

Cuối cùng, tôi xin chân thành cảm ơn gia đình và bạn bè đã luôn động

viên tôi trong suốt quá trình học tập và thực hiện luận văn.

Mở đầu

Tư duy về tổ hợp xuất hiện từ rất sớm trong lịch sử phát triển của nhân loại. Tuy nhiên, lý thuyết tổ hợp được xem hình thành như một ngành toán học vào khoảng thế kỷ 17 bằng một loạt các công trình nổi tiếng của các nhà toán học như Passcal, Fermat, Leibniz, Euler, . . . . Kể từ sau khi tin học ra đời, lý thuyết tổ hợp phát triển ngày càng mạnh mẽ. Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn và lí thú của toán học nói chung và của toán rời rạc nói riêng. Nó không chỉ có nội dung phong phú, đa dạng, mà còn có nhiều ứng dụng trong thực tế đời sống. Trong toán sơ cấp, tổ hợp cũng xuất hiện với nhiều bài toán hay với độ khó cao. Khi giải các bài toán tổ hợp, ta phải liệt kê, đếm các đối tượng theo các tính chất nào đó. Để làm được việc này, ngoài việc sử dụng hai quy tắc đếm cơ bản, các kiến thức về hoán vị, chỉnh hợp, tổ hợp, trong nhiều bài toán ta phải sử dụng một số nguyên lý khác trong tổ hợp. Vì vậy, để hiểu rõ và nắm bắt sâu hơn vể vấn đề này, tôi đã chọn đề tài Một vài nguyên lý và bài toán tổ hợp. Luận văn đã trình bày một số nguyên lý cơ bản trong tổ hợp và xây dựng một số bài toán áp dụng. Luận văn gồm phần mở đầu, ba chương, kết luận và danh mục tài liệu tham khảo. Chương 1 : Kiến thức chuẩn bị. Trong chương này, tác giả đã trình bày một số lý thuyết về nguyên lý quy nạp, hai quy tắc đếm cơ bản, hoán vị, chỉnh hợp, tổ hợp, nhị thức Newton và đồ thị cây. Chương 2 : Một vài nguyên lý trong tổ hợp. Chương 2 gồm 4 nội dung chính, trình bày bốn nguyên lý cơ bản trong tổ hợp và các ví dụ áp dụng các nguyên lý đó. Cụ thể là: Mục 2.1 trình bày nguyên lý thứ nhất: Nguyên lý Dirichlet. Nguyên lý này còn được gọi là nguyên lý lồng chim bồ câu. Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất có ngăn

(cid:3) + 1 đồ vật."

có nhiều hơn 1 con chim. Phát triển dạng toán này, Piter Gustave Dirichlet đã đưa ra một nguyên lý chứng minh toán học đơn giản, được phát biểu như sau: "Nếu có N đồ vật được đặt vào k hộp thì tồn tại một hộp chứa ít nhất (cid:2)N k

Mục 2.2 trình bày Nguyên lý bù trừ. Khi hai công việc có thể làm đồng thời, chúng ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Cộng số cách thực hiện mỗi việc sẽ dẫn đến sự trùng lặp, vì những cách làm cả hai công việc sẽ được tính hai lần. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai công việc. Nguyên lý này được mở rộng cho trường hợp đếm số phần tử của hợp các tập hợp bất kì. Đó là Nguyên lý bù trừ. Nguyên lý thứ 3 là Nguyên lý cực hạn, được trình bày trong mục 2. 3. Nguyên lý này chỉ ra rằng tồn tại phần tử lớn nhất và phần tử nhỏ nhất của một tập hợp hữu hạn. Nguyên lý này có rất nhiều ứng dụng trong việc giải các bài toán tổ hợp, giải một số phương trình nghiệm nguyên, chứng minh các bất đẳng thức, . . . . Cuối cùng, mục 2. 4 trình bày nguyên lý thứ 4 là Nguyên lý bất biến. Trong mục này, tác giả đã trình bày hai mẫu bài toán tổng quát thường được giải bằng nguyên lý bất biến và đưa ra một ví dụ sử dụng nguyên lý bất biến. Chương 3. Một vài đồng nhất thức trong tổ hợp. Chương này trình bày một số ví dụ về xây dựng đồng nhất thức trong tổ hợp qua hệ phương trình, số phức và hàm sinh, . . .

Chương 1

Kiến thức chuẩn bị

1.1 Nguyên lý quy nạp

Mệnh đề 1.1. [Nguyên lý thứ nhất]. Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) đúng với một α ∈ N. (ii) P (n + 1) đúng khi P (n) đúng, ở đó n ≥ α, n ∈ N thì P (n) đúng với mọi số tự nhiên n ≥ α.

Mệnh đề 1.2. [Nguyên lý thứ hai]. Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) đúng với một α ∈ N. (ii) P (n + 1) đúng khi P (α), P (α + 1), ..., P (n) đúng, ở đó n ≥ α, n ∈ N, thì P (n) đúng với mọi số tự nhiên n ≥ α.

Cách chứng minh một định lý hay một bài toán có sử dụng nguyên lý quy nạp được gọi là phép quy nạp hay phương pháp quy nạp toán học. Sau đây, ta sẽ xét một số ví dụ áp dụng hai nguyên lý này.

Ví dụ 1.1. Chứng minh rằng, với số nguyên n ≥ 1 và số thực a > 0 ta luôn có đồng nhất thức

n (cid:88)

(cid:81)n

k=1

Lời giải. Trước tiên, ta chứng minh bằng quy nạp theo n rằng

(cid:90) 1

. = (−1)kCk n ak + 1 n!an k=1(1 + ka)

(cid:81)n

(1 − xa)ndx = . n!an k=1(1 + ka)

Thật vậy Với n = 1 ta có

(cid:90) 1

(cid:16)

(cid:17)(cid:12) (cid:12) (cid:12)

0 Suy ra khẳng định đúng với n = 1. Đặt

(cid:90) 1

= (1 − xa)dx = x − = . xa+1 a + 1 a a + 1 1!a1 1 + 1.a

Giả sử

(1 − xa)ndx. In =

(cid:81)n

Ta phải chứng minh

. In = n!an k=1(1 + ka)

Ta có

(cid:90) 1

. In+1 = (n + 1)!an+1 (cid:81)n+1 k=1(1 + ka)

Hay

(1 − xa)n+1dx = (n + 1)a In+1 = xa(1 − xa)ndx = (n + 1)a(In − In+!).

Theo giả thiết quy nạp ta có

In+1 = In. (n + 1)a 1 + (n + 1)a

Suy ra khẳng định trên đúng với n + 1. Vậy khẳng đinh trên đúng với mọi n ≥ 1. Từ đó suy ra

(cid:90) 1

n (cid:88)

. In+1 = (n + 1)!an+1 (cid:81)n+1 k=1(1 + ka)

(cid:81)n

k=0

Ví dụ 1.2. Chứng minh rằng với số nguyên n > 0 ta có đồng nhất thức

xakdx = (1 − xa)ndx = . = (−1)kCk n (−1)kCk n ak + 1 n!an k=1(1 + ka)

1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + 2.

Lời giải. Ta chứng minh bằng quy nạp theo n. + Với n = 1 ta có 1.2 = 2 = (1 − 1)21+1 + 2. Chứng tỏ kết luận đúng với n = 1. + Giả sử kết luận đúng với n ≥ 1. Khi đó

+ Ta phải chứng minh kết luận đúng với n + 1. Tức là

1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + 2.

Thật vậy, ta có

1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = n2n+2 + 2.

Chứng tỏ kết luận đúng với n + 1. Vậy khẳng định đúng với mọi số nguyên n > 0.

Ví dụ 1.3. Dãy (an) được cho như sau: a0 = 1, a1 = 3, a2 = 6, a3 = 10, a4 = 15, a5 = 21, .... Xác định (an) theo n và chứng minh bất đẳng thức

(cid:1)(cid:0)1 −

(cid:1)...(cid:0)1 −

(cid:1) <

1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = (n − 1)2n+1 + 2 + (n + 1)2n+1 = n2n+2 + 2.

Lời giải. Ta có

+ . T = (cid:0)1 − 1 3 1 6 1 10 1 3 1 n 1 an

a0 = 1,

a1 = 3 = a0 + 1 + 1,

a2 = 6 = a1 + 2 + 1,

a3 = 10 = a2 + 3 + 1,

a4 = 15 = a3 + 4 + 1,

a5 = 21 = a4 + 5 + 1,

Suy ra an = an−1 + n + 1. Điều này dễ dàng có được bằng chứng minh quy nạp.

...

. (n + 1)(n + 2) 2

Suy ra 1 −

Vậy an = 1 + 2 + 3 + 4 + ... + n + n + 1 = ak − 1 ak

Như vậy

= = = . (k + 1)(k + 2) − 2 (k + 1)(k + 2) k(k + 3) (k + 1)(k + 2) 1 ak

(cid:1)(cid:0)1 +

(cid:1).

= (cid:0)1 − 1 − 1 k + 1 1 k + 2 1 ak

Suy ra

(cid:1)

(cid:1) . . . (cid:0)1 −

(cid:1)(cid:0)1 +

(cid:1)

1 4

(cid:1) . . . (cid:0)1 −

(cid:1)(cid:0)1 +

(cid:1)

= 1 2 (cid:0)1 − 1 3 (cid:1)(cid:0)1 − 1 3 (cid:1)(cid:0)1 −

(cid:1)(cid:0)1 +

(cid:1)(cid:0)1 + 1 52 (cid:1)(cid:0) 52 − 1 52

(cid:1)(cid:0)1 + 1 32 (cid:0) 32 − 1 32

(cid:1)(cid:0)1 − 1 42 (cid:1)(cid:0) 42 − 1 42

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

= < = + . T =(cid:0)1 − 1 2 1 2 2.3.42.52 . . . (n − 1)2.n2(n + 1)(n + 2)(n + 3) 2.32.42.52 . . . (n − 1)2.n2(n + 1)2(n + 2) n + 3 1 3 3(n + 1) n + 3 3n 1 n

và T <

Vậy an =

1.2 Hai quy tắc đếm cơ bản

Chương trình toán phổ thông lớp 11 đã trang bị cho học sinh hai quy tắc đếm cơ bản, đó là quy tắc cộng và quy tắc nhân. Đây là hai công cụ quan trọng giúp học sinh giải được một số bài toán tổ hợp đơn giản. Quy tắc cộng được phát biểu như sau: Giả sử, một công việc có thể được thực hiện theo một trong k phương án A1, A2, . . . , Ak. Có n1 cách thực hiện phương án A1, n2 cách thực hiện phương án A2, . . . , nk cách thực hiện phương án Ak. Khi đó công việc có thể được thực hiện bởi n1 + n2 + · · · + nk cách. Bản chất của quy tắc cộng là công thức tính số phần tử của hợp n tập hợp hữu hạn đôi một không giao nhau. Cụ thể ta có: Cho A1, A2, . . . , Ak là các tập rời nhau. Khi đó (cid:12) + (cid:12) (cid:12)

(cid:12) (cid:12)A1 ∪ A2 ∪ · · · ∪ Ak

(cid:12) + · · · + (cid:12) (cid:12)

(cid:12) = (cid:12) (cid:12)

(cid:12)Ak

(cid:12)A1

(cid:12)A2

(cid:12) (cid:12).

Khi một công việc được thực hiện bởi nhiều công đoạn liên tiếp, thì ta phải sử dụng quy tắc nhân. Quy tắc nhân cho nhiều công đoạn được phát biểu như sau: Giả sử một công việc nào đó bao gồm k công đoạn A1, A2, . . . , Ak. Công đoạn A1 có thể thực hiện theo n1 cách, công đoạn A2 có thể thực hiện theo n2 cách, . . . , công đoạn Ak có thể thực hiện theo nk cách. Khi đó công việc có thể thực hiện theo n1n2 . . . nk cách.

+ . (n + 1)(n + 2) 2 1 3 1 n

Quy tắc nhân cũng có thể được phát biểu dưới dạng tập hợp như sau: Cho A1, A2, . . . , Ak là các tập hợp hữu hạn. Khi đó, số cách chọn một bộ gồm k phần tử (a1, a2, . . . , ak), ai ∈ Ai, i = 1, 2, . . . , k là

(cid:12) (cid:12)A1 × A2 × · · · × Ak

(cid:12) = (cid:12) (cid:12)

(cid:12)A1

(cid:12) × (cid:12) (cid:12)

(cid:12)A2

(cid:12) × · · · × (cid:12) (cid:12)

(cid:12)Ak

(cid:12) (cid:12).

1.3 Hoán vị

Hoán vị thực chất chính là một cách sắp xếp nào đó các phần tử của một tập hợp. Khi các phần tử của tập hợp phân biệt và không được sử dụng lặp lại thì ta có hoán vị không lặp, gọi tắt là hoán vị. Hoán vị không lặp (hoán vị) được định nghĩa như sau:

Định nghĩa 1.1. Cho tập A có n phần tử (n ≥ 1). Khi sắp xếp n phần tử này theo một thứ tự, ta được một hoán vị các phần tử của tập A (gọi tắt là một hoán vị của A). Kí hiệu: Số hoán vị của n phần tử là Pn. Để tính số hoán vị không lặp của một tập hợp gồm n phần tử, ta áp dụng định lý sau:

Định lý 1.1. Số các hoán vị của tập có n phần tử là

(1.1)

Chứng minh. Giả sử, tập A có n phần tử. Việc sắp xếp thứ tự n phần tử của A là một công việc gồm n công đoạn: Công đoạn 1: Chọn phần tử để xếp vào vị trí thứ nhất. Trong công đoạn này, ta có thể chọn bất kì phần tử nào trong n phần tử của A nên có n cách thực hiện. Công đoạn 2: Chọn phần tử để xếp vào vị trí thứ 2. Sau khi thực hiện xong công đoạn thứ nhất, ở công đoạn thứ 2 ta có thể chọn bất kì phần tử nào trong n − 1 phần tử còn lại của A để xếp vào vị trí thứ 2 nên có n − 1 cách thực hiện. Công đoạn 3: Chọn phần tử xếp vào vị trí thứ 3. Lập luận tương tự, ở công đoạn 3 có n − 2 cách thực hiện. . . . Công đoạn n: Chọn phần tử xếp vào vị trí thứ n. Sau khi thực hiện xong n − 1 công đoạn trên thì tập A chỉ còn 1 phần tử nên công đoạn thứ n có 1 cách

Pn = n! = n(n − 1) . . . 2.1.

thực hiện. Theo quy tắc nhân, có tất cả n(n − 1)(n − 2) . . . 1 = n! cách sắp xếp thứ tự n phần tử của tập A . Tức là có Pn = n! hoán vị.

Chú ý 1.1. Quy ước 0! = 1 nên công thức (1.1) đúng với n ≥ 0 Trong một số bài toán đếm, khi hoán vị n phần tử mà có các phần tử giống nhau hoặc được sử dụng lặp lại nhiều lần thì khi đếm số các hoán vị này cần thận trọng, tránh đếm chúng hơn một lần. Khi đó, công thức tính số hoán vị trên không sử dụng được. Ta phải sử dụng công thức tính số hoán vị lặp. Định nghĩa về hoán vị lặp được phát biểu như sau:

Định nghĩa 1.2. Hoán vị mà trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị lặp.

Định lý 1.2. Số hoán vị của n phần tử, trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2, . . . , nk phần tử giống nhau thuộc loại k, là

(1.2)

n−n1−n2−...nk−1 cách đặt nk phần tử loại k vào hoán vị.

Chứng minh. Để xách định số hoán vị, trước tiên ta thấy có Cn1 n cách giữ n1 chỗ cho n1 phần tử loại 1, còn lại n − n1 chỗ trống. Sau đó, đặt n − 2 phần tử loại 2 vào hoán vị. Có Cn2 n−n1 cách đặt, còn lại n − n1 − n2 chỗ trống. Tiếp tục, đặt các phần tử loại 3, loại 4, . . . , loại k − 1 vào hoán vị. Cuối cùng, có Cnk Theo quy tắc nhân, có tất cả các hoán vị là

. n! n1!n2! . . . nk!

n Cn2 Cn1

n−n1−n2−···−nk−1

. . . Cnk =

n−n1 n! n1!(n − n1)!

Ví dụ 1.4. Một lớp có 100 sinh viên gồm 50 nam và 50 nữ. Giả sử 100 em xếp thành một hàng thẳng. Tính số cách xếp để có ít nhất có hai em cùng giới đứng cạnh nhau.

Lời giải. Đánh số vị trí đứng từ 1 đến 100. Xếp 100 em vào 100 vị trí là một phép hoán vị của 100 phần tử. Tất cả có 100! cách xếp. Tính số cách xếp để không có hai người cùng giới đứng cạnh nhau: Lần đầu xếp các em nữ ở vị trí lẻ, các em nam đứng ở vị trí chẵn. Có 50!50! cách xếp.

. . . = . = (n − n1)! n2!(n − n1 − n2)! (n − n1 − · · · − nk−1)! nk!0! n! n1!n2! . . . nk!

Lần sau, xếp các em nữ ở vị trí chẵn, các em nam ở vị trí lẻ. Có 50!50! cách xếp. Vậy số cách xếp cần tính là 100! − 2.50!50!.

Ví dụ 1.5. Giả sử các số a1, a2, . . . , an, . . . được định nghĩa như sau : a1 = 0, a2 = 1 và an+1 = (n + 1)an + (−1)n+1, với mọi số nguyên n ≥ 1. Chứng minh rằng

(cid:1) với n ≥ 1.

(cid:0) 1 P0

− + − an = Pn 1 P1 1 P2 1 P3 + · · · + (−1)n 1 Pn

Lời giải. Với n = 1, ta có a1 = 0 = P1

(cid:0) 1 P0

−

(cid:1). Kết luận đúng với n = 1. 1 (cid:0) 1 P2 P0

(cid:1) với n ≥ 1.

+ · · · + − − + 1 P1 1 P3

1 P1 Giả sử kết luận đúng với n, có nghĩa là an = Pn (−1)n 1 Pn Ta chứng minh khẳng định đúng với n + 1. Thật vậy:

an+1 = (n + 1)an + (−1)n+1

(cid:1) + (−1)n+1

− + = (n + 1)Pn + · · · + (−1)n 1 Pn

− + − = Pn+1

(cid:1).

(cid:0) 1 P0 1 P1 1 P1

(cid:0) 1 P0 (cid:0) 1 P0

(cid:1) + (−1)n+1 + (−1)n+1 1 Pn+1

− + − = Pn+1 1 P1 1 P2 1 P2 1 − P3 + · · · + (−1)n 1 Pn + · · · + (−1)n 1 Pn

(cid:1) với n ≥ 1.

Do đó an = Pn

(cid:0) 1 P0

Ví dụ 1.6. Giả sử m và k là những số nguyên dương và đặt n = mk. Kí hiệu T là số cách phân chia n đồ vật khác nhau xếp vào k hộp giống nhau sao cho

mỗi hộp chứa đúng m đồ vật. Khi đó T =

− + − 1 P1 1 P2 1 P3 1 P2 1 P3 1 P3 + · · · + (−1)n 1 Pn

n! k!(m!)k .

Lời giải. Ta coi k hộp là khác nhau. Khi đó số cách phân chia n đồ vật vào n! (m!)k . Do k hộp giống nhau nên mỗi cách phân chia xuất hiện k! lần. Vậy thực tế số cách phân

chia là T =

= k hộp sao cho mỗi hộp chứa đúng m đồ vật là n! m!m!...m!

1.4 Chỉnh hợp

Trước tiên, ta có định nghĩa chỉnh hợp không lặp, gọi tắt là chỉnh hợp.

n! k!(m!)k .

Định nghĩa 1.3. Cho tập A gồm n phần tử và số nguyên k, 1 ≤ k ≤ n. Khi lấy ra k phần tử của A và sắp xếp chúng theo một thứ tự, ta được một chỉnh hợp chập k của n phần tử của A, gọi tắt là một chỉnh hợp chập k của A. Kí hiệu: Số chỉnh hợp chập k của tập A có n phần tử là Ak n.

Định lý 1.3. Số các chỉnh hợp chập k của một tập có n phần tử ( 1 ≤ k ≤ n) là

(1.3)

n =

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

Chứng minh. Việc lập một chỉnh hợp chập k của một tập hợp có n phần tử được coi như một công việc gồm k công đoạn như sau: Công đoạn 1: Chọn phần tử xếp vào vị trí thứ nhất. Vì tập hợp có n phần tử nên công đoạn này có n cách thực hiện. Công đoạn 2: Chọn phần tử xếp vào vị trí thứ 2. Ở công đoạn 2, tập hợp chỉ còn n − 1 phần tử chưa chọn nên có n − 1 cách thực hiện. Công đoạn 3: Chọn phần tử xếp vào vị trí thứ 3. Ở công đoạn 3, tập hợp chỉ còn n − 2 phần tử chưa chọn nên có n − 2 cách thực hiện. . . . Công đoạn k: Chọn phần tử xếp vào vị trí thứ k. Lập luận tương tự, ở công đoạn k, có n − k + 1 cách thực hiện. Theo quy tắc nhân, ta có n(n − 1) . . . (n − k + 1) cách thực hiện công việc. Hay có n(n − 1) . . . (n − k + 1) cách lập ra một chỉnh hợp chập k của n phần tử. n! Vậy Ak (n − k)!

n = 1 nên công thức (1.3) đúng với 0 ≤ k ≤ n.

Chú ý 1.2. Quy ước A0 Trong các bài toán đếm sử dụng chỉnh hợp không lặp, thì các phần tử được sử dụng nhiều nhất một lần. Nhưng trong thực tế, nhiều bài toán đếm, các phần tử có thể được sử dụng nhiều hơn một lần. Khi đó, áp dụng chỉnh hợp không lặp trong các bài toán đó không còn đúng nữa. Vì vậy, ta có khái niệm chỉnh hợp lặp.

Định nghĩa 1.4. Cho tập hữu hạn A gồm n phần tử. Mỗi dãy có độ dài k các phần tử của A, mà mỗi phần tử có thể lặp lại nhiều lần và được xếp theo một thứ tự nhất định, được gọi là một chỉnh hợp lặp chập k của n phần tử của A. Kí hiệu: Số chỉnh hợp lặp chập k của n phần tử là Ak n.

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

Định lý 1.4. Số chỉnh hợp lặp chập k của n phần tử là

(1.4)

n = nk.

Chứng minh. Việc lập một chỉnh hợp lặp chập k của một tập hợp có n phần tử được coi như một công việc gồm k công đoạn: Công đoạn 1 là chọn phần tử vào vị trí thứ nhất, công đoạn 2 là chọn phần tử vào vị trí thứ 2, công đoạn 3 là chọn phần tử vào vị trí thứ 3, . . . , công đoạn k là chọn phần tử vào vị trí thứ k. Vì các phần tử có thể lặp lại nhiều lần nên ở mỗi công đoạn, ta đều có n cách chọn một phần tử từ tập hợp có n phần tử cho mỗi một trong k vị trí của = nk chỉnh hợp lặp chập k của n chỉnh hợp. Theo quy tắc nhân, có n.n . . . n (cid:124) (cid:123)(cid:122) (cid:125) k lần

phần tử.

Ví dụ 1.7. Một cuộc khiêu vũ có 10 nam và 8 nữ tham gia. Người ta chọn có thứ tự 3 nam và 3 nữ để ghép thành 3 cặp. Hỏi có bao nhiêu cách chọn?

8 = 336 cách chọn nữ.

Lời giải. Chọn có thứ tự 3 nam trong số 10 nam là một chỉnh hợp chập 3 của 10. Số cách chọn là A3 10 = 720 cách chọn nam. Chọn có thứ tự 3 nữ trong số 8 nữ là một chỉnh hợp chập 3 của 8. Số cách chọn là A3 Mỗi cách chọn nam lại tương ứng với tất cả các cách chọn nữ nên tất cả có số cách chọn là 720.336 = 241920 cách chọn.

Ví dụ 1.8. Có thể lập được bao nhiêu biển số xe với hai chữ cái đầu thuộc tập {A, B, C, D, E}. Tiếp theo là một số nguyên dương gồm năm chữ số chia hết cho 5.

...5 nên e = 0 hoặc e = 5. Suy ra e có 2 cách chọn.

10 = 103 = 1000.

Lời giải. Giả sử một biển số xe nào đó có dạng XY abcde. Vì X, Y có thể trùng nhau nên XY là chỉnh hợp lặp chập 2 của 5 phần tử A, B, C, D, E. Số 5 = 52 = 25. cách chọn XY là A2 Do a (cid:54)= 0 nên a có 9 cách chọn. Vì abcde Do b, c, d có thể trùng nhau nên số cách chọn mỗi số bcd là chỉnh hợp lặp chập 3 của 10. Bởi vậy, số cách chọn số bcd là A3 Vậy số biển số xe có thể lập được theo yêu cầu là 25.9.2.1000 = 450000.

1.5 Tổ hợp

Định nghĩa 1.5. Cho tập A có n phần tử và số nguyên k với 1 ≤ k ≤ n. Mỗi tập con của A có k phần tử được gọi là một tổ hợp chập k của n phần tử của A , gọi tắt là một tổ hợp chập k của A. Kí hiệu: Số tổ hợp chập k của n phần tử là Ck n.

Định lý 1.5. Số các tổ hợp chập k của một tập hợp có n phần tử, với 1 ≤ k ≤ n, là

1.5.1 Tổ hợp

(1.5)

n =

Chứng minh. Giả sử, ta lập được một tổ hợp chập k của tập A có n phần tử. Mỗi cách sắp xếp thứ tự các phần tử của một tổ hợp chập k của A cho ta một chỉnh hợp chập k của A. Nói cách khác, mỗi hoán vị của một tổ hợp chập k của A cho ta một chỉnh hợp chập k của A. Vậy từ một tổ hợp chập k của A ta lập được k! chỉnh hợp chập k của A. Suy ra

= . Ck Ak n k! n! k!(n − k)!

n = Ck

nk! hay Ck

n =

n = 1 nên công thức (1.5) đúng với mọi số nguyên

Chú ý 1.3. Ta quy ước C0 k thỏa mãn 0 ≤ k ≤ n.

Hệ quả 1.1. Cho n và k là các số nguyên không âm sao cho k ≤ n . Khi đó

Ak = . Ak n k! n! k!(n − k)!

n = Cn−k Ck

Chứng minh. Theo định lý 1.5 ta có

n =

và

Ck n! k!(n − k)!

n =

Suy ra

Cn−k = . n! (n − k)![n − (n − k)]! n! (n − k)!k!

n = Cn−k Ck

Định nghĩa 1.6. Cho tập A gồm n phần tử (n ≥ 1). Một tổ hợp lặp chập k của n phần tử của A (k không nhất thiết phải nhỏ hơn n) là một bộ gồm k phần tử, mà mỗi phần tử này có thể lặp lại của tập hợp A. Kí hiệu: Số tổ hợp lặp chập k của n phần tử là Ck n.

Định lý 1.6. Số các tổ hợp lặp chập k của tập n phần tử là

(1.6)

n = Ck Ck

n+k−1.

Chứng minh. Mỗi tổ hợp lặp chập k của n phần tử có thể biểu diễn bằng một dãy n − 1 thanh đứng và k ngôi sao. Ta dùng n − 1 thanh đứng để ngăn cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao nếu phần tử thứ i của tập hợp xuất hiện trong tổ hợp. Ví dụ, tổ hợp lặp chập 6 của tập 4 phần tử được biểu thị bằng 3 thanh đứng và 6 ngôi sao. Dãy ∗ ∗ | ∗ | thứ hai, không có phần tử thứ ba và 3 phần tử thứ tư của tập hợp. Như vậy, mỗi dãy n − 1 thanh đứng và k ngôi sao ứng với một tổ hợp lặp chập k của n phần tử. Vì mỗi dãy ứng với một cách chọn k vị trí cho k ngôi sao từ n + k − 1 vị trí. Nên số các dãy như vậy là Ck n+k−1. Vậy số tổ hợp lặp chập k của tập n phần tử là Ck

n+k−1.

Ví dụ 1.9. Một cửa hàng có 10 loại bánh khác nhau. Ngày Trung thu, cô giáo đi mua 30 chiếc bánh cho học sinh. Hỏi có bao nhiêu cách chọn mua 30 chiếc bánh đó.

Lời giải. Mỗi cách chọn mua 30 chiếc bánh cho học sinh là một tổ hợp lặp chập 30 của 10 phần tử. Khi đó, số cách mua 30 chiếc bánh đó là C30 30+10−1 = C30 39

Ta có một số kết quả sau đây.

Bổ đề 1.1. Số nghiệm nguyên không âm của phương trình x1 +x2 +· · ·+xk = n bằng Ck−1

n+k−1.

n+1.

Chứng minh. Kí hiệu số nghiệm nguyên không âm của phương trình là Nk(n). Ta có N1(n) = 1. Tính N2(n), tức là tính số nghiệm nguyên không âm của phương trình x1 + x2 = n. Phương trình này có các nghiệm (0, n), (1, n − 1), . . . , (n, 0) nên N2(n) = n + 1 = C1 Để tính N3(n) ta xét phương trình x1 +x2 +x3 = n. Cho x3 = 0, 1, 2, . . . , n, ta có

| ∗ ∗∗ biểu thị tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử

n+2.

Ta chứng minh Nk(n) = Ck−1

n+k−1 bằng quy nạp. Ta có

= C2 N3(n) = N2(n) + N2(n − 1) + · · · + N2(2) + N2(1) + N2(0) = (n + 1) + n + · · · + 2 +1 = (n + 1)(n + 2) 2

Nk(n) = Nk−1(n) + Nk−1(n − 1) + Nk−1(n − 2) + · · · + Nk−1(0)

n+k−2 + Ck−2

n+k−3 + Ck−2

n+k−4 + · · · + Ck−2

k−2 = Ck−1

n+k−1.

Hệ quả 1.2. Số nghiệm nguyên không âm của hệ bất phương trình dưới đây đúng bằng Ck−1

n−α1−α2−···−αn+k−1

 

= Ck−2



x1 + x2 + · · · + xk = n

Chứng minh. Đặt xi = yi + αi với i = 1, 2, . . . , k. Khi đó ta phải xác định nghiệm nguyên không âm của hệ bất phương trình

 

x1 ≥ α1, . . . , xk ≥ αk.



y1 + y2 + · · · + yk = n − α1 − · · · − αk

Theo bổ đề 1.1, số nghiệm cần xác định đúng bằng Ck−1

n−α1−α2−···−αn+k−1.

n+k−1.

Nhận xét 1.1. Ta có thể sử dụng hệ phương trình nghiệm nguyên để chứng minh định lý 1.6: Giả sử ta lấy xi lần phần tử của tập A = {a1, a2, . . . , an}. Khi đó xi là số nguyên không âm. Mỗi tổ hợp lặp chập k của A tương ứng một - một với một nghiệm nguyên không âm của phương trình x1 + x2 + · · · + xn = k. Theo bổ đề 1.1, số nghiệm nguyên không âm của phương trình này là Cn−1 n+k−1 = Ck

y1 ≥ 0, . . . , yk ≥ 0.

Bổ đề 1.2. Với số nguyên dương n, đặt f (x) = (1 + x)(2 + x) . . . (n + x). Giả sử f (x) = b0 + b1x + b2x2 + · · · + bnxn. Chứng minh rằng

1.5.2 Ứng dụng trong số học

k+2bk+1.

n−1

n+1

và hệ thức (1 + x)(2 +

Chứng minh. Từ (1 + x)(2 + x) . . . (n + x) = b0 + b1x + b2x2 + · · · + bnxn ta suy ra (2 + x)(3 + x) . . . (n + 1 + x) = b0 + b1(x + 1) + b2(x + 1)2 + · · · + bn(x + 1)n. Ta có ngay bn = 1, bn−1 = 1 + 2 + 3 + · · · + n =

bn−1 + Cn−1−k bn−2 + · · · + C2 bn + Cn−k (n − k)bk = Cn+1−k

n(n + 1) 2

x) . . . (n + x)(n + 1 + x) = b0(x + 1) + b1(x + 1)2 + b2(x + 1)3 + · · · + bn(x + 1)n+1. Tức là (n + 1 + x)f (x) = (x + 1)f (x + 1). Suy ra

Như vậy: 

(n+1+x)(b0+b1x+b2x2+· · ·+bnxn) = b0(x+1)+b1(x+1)2+b2(x+1)3+· · ·+bn(x+1)n+1

bn = 1

(n + 1)bn−1 + bn−2 = C2

nbn−1 + C0 nbn−1 + C1

n−1bn−2 n−1bn−2 + C0

n−2bn−3

n+1bn + C1 n+1bn + C2

(n + 1)bn−2 + bn−3 = C3

. . .

2 b1

(n + 1)b2 + b1 = Cn−1

n+1 bn + Cn−2 n+1bn + Cn−1

3 b2 + C0 2 b1 + C0

1 b0

 

bn−1 + Cn−3 bn−1 + Cn−2

n bn−1 + Cn−1

n−1 bn−2 + · · · + C1 n−1 bn−2 + · · · + C1 2 b1 + C1

1 b0

n+1 bn + Cn

n−1 bn−2 + · · · + C2



(n + 1)b1 + b0 = Cn (n + 1)b0 = Cn+1

bn = 1

bn−1 =

nbn−1

2bn−2 = C3 n(n + 1) 2! n+1 + C2

. . .

4 b3

n+1 + Cn−2 n+1 + Cn−1

3 b2

n−1 bn−2 + · · · + C2 n−1 bn−2 + · · · + C1

 

(n − 2)b2 = Cn−1

n n bn−1 + Cn−1

2 b1

(n − 1)b1 = Cn nb0 = Cn+1 bn−1 + Cn−3 bn−1 + Cn−2 n−1 bn−2 + · · · + C0

Do vậy (n − k)bk = Cn+1−k

n+1 + Cn n+1 + Cn−k

n−1

k+2bk+1.

Hệ quả 1.3. [MO British 1974] Với số nguyên tố lẻ p, đặt f (x) = (1 + x)(2 + x) . . . (p − 1 + x). Giả sử f (x) = b0 + b1x + b2x2 + · · · + bp−1xp−1. Chứng minh rằng

(i) p | bk với k = 1, 2, . . . , p − 2 và p |(b0 + 1).

(ii) Với mọi số nguyên n ta có p | (n + 1)(n + 2) . . . (n + p − 1) − np−1 + 1. Từ

đó suy ra p | (p − 1)! + 1 và p | np−1 − 1 khi (n, p) = 1.

bn−1 + Cn−1−k bn−2 + · · · + C2

Chứng minh:. (i) Qua các công thúc tính toán được ở trên ta có



bp−1 = 1

bp−2 =

p−1bp−2

3 b2

p−1 bp−2 + Cp−3

 

p(p − 1) 2! p + C2 2bp−3 = C3

p + Cp−2 p + Cp−1

p−2 bp−3 + · · · + C1 2 b1.

p−1 bp−2 + Cp−2

p−2 bp−3 + · · · + C2

Sử dụng quy nạp theo k có p | bk với k = 1, 2, . . . , p − 2. Từ hệ thức cuối cùng suy ra hệ thức pb0 = (b0 + 1) + bp−2 + bp−3 + · · · + b1 và như vậy b0 + 1 chia hết cho p. (ii) Vì p | bk với k = 1, 2, . . . , p − 2 và b0 + 1 chia hết cho p nên p | (n + 1)(n + 2) . . . (n + p − 1) − np−1 + 1 với mọi số nguyên n. Từ đó suy ra p | (p − 1)! + 1 và p | np−1 − 1 khi (n, p) = 1.

Từ các kết quả trên ta suy ra các kết quả sau đây

Định lý 1.7. Với số nguyên tố p và với mọi số tự nhiên n thỏa mãn (n, p) = 1, ta luôn có:

(i) [Fermat] np−1 ≡ 1(modp).

(cid:1)!(cid:3)2

· · · (p − 2)b1 = Cp−1 (p − 1)b0 = Cp

(ii) [Wilson] (p − 1)! + 1 ≡ 0(modp). (iii) Nếu số nguyên tố p có dạng 4k + 1 thì (cid:2)(cid:0) p − 1

1.6 Nhị thức Newton

Định lý 1.8. [Hằng đẳng thức Pascal] Cho n và k là các số nguyên dương với n ≥ k. Khi đó

(1.7)

n + Ck n.

n+1 = Ck−1 Ck

Chứng minh. Giả sử T là tập có n + 1 phần tử. Gọi a là một phần tử nào đó của T và S = T − {a}. Ta có, số tập con có k phần tử của tập T là Ck n+1. Khi đó, các tập con này hoặc là chứa phần tử a cùng với k − 1 phần tử của S hoặc là chứa k phần tử của S và không chứa a.

+ 1 ≡ 0(modp). 2

và số tập con chứa k phần

Mà số tập con chứa k − 1 phần tử của S là Ck−1 tử của S là Ck

n. Do đó

n+1 = Ck−1 Ck

n + Ck n.

Chú ý 1.4. Trên đây là cách chứng minh hằng đẳng thức Pascal bằng lý thuyết tổ hợp. Ta cũng có thể chứng minh đẳng thức này bằng cách áp dụng kết quả định lý 1.5. Hằng đẳng thức Pascal là cơ sở để sắp xếp hình học các hệ số nhị thức Ck

n, k = 0, 1, 2, . . . , n thành tam giác Pascal như sau:

2 C1 C0

C0 0

3 C2

1 C1 C0 1 2 C2 2 3 C3 3

C0 3 C1

n C1 C0

n . . . Cn−1

. . . . . . . . . . . .

Cn n

Hàng thứ n của tam giác gồm hệ số nhị thức Ck n, k = 0, 1, 2, . . . , n. Hằng đẳng thức Pascal chỉ ra rằng khi cộng hai hệ số nhị thức liền kề trong tam giác sẽ nhận được hệ số nhị thức liền kề trong tam giác tiếp theo ở giữa hai hệ số này. Ngoài tam giác Pascal, các hệ số nhị thức còn liên quan chặt chẽ tới việc khai triển lũy thừa của một nhị thức. Đó là khai triển Nhị thức Newton.

Định lý 1.9. [Nhị thức Newton] Cho x, y là hai biến và n là số nguyên dương. Khi đó

n (cid:88)

. . . . . . . . . . . . . . .

nxn−kyk Ck

(1.8)

n yn.

n xyn−1 + Cn

nxn−1y + · · · + Cn−1

k=0 nxn + C1 = C0

Chứng minh. Ta sẽ chứng minh định lý này bằng suy luận tổ hợp. Các số hạng trong khai triển của (x + y)n sẽ có dạng xn−kyk với k = 0, 1, . . . , n. Để nhận được số hạng dạng xn−kyk ta chon x từ n − k tổng (x + y) và có Cn−k

(x + y)n =

n = Ck n.

cách chọn như vậy. Khi đó, y được chọn từ k tổng còn lại nên có một cách chọn duy nhất. Do đó, hệ số của xn−kyk là Cn−k Điều phải chứng minh.

Các hệ số của khai triển chính là các hệ số nhị thức.

Hệ quả 1.4. Cho n là số nguyên dương. Khi đó

n (cid:88)

n = 2n. Ck

k=0

Chứng minh. Áp dụng công thức Nhị thức Newton ta có

n (cid:88)

n1n−k1k = Ck

k=0

Hệ quả 1.5. Cho n là số nguyên dương. Khi đó

n (cid:88)

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

n = 0.

k=0

Chứng minh. Áp dụng công thức Nhị thức Newton ta có

n (cid:88)

(−1)kCk

n1n−k(−1)k = Ck

k=0

1.7 Đồ thị cây

Để giải một số bài toán đếm, ta phải liệt kê các kết quả có thể xảy ra của bài toán. Khi đó, đồ thị cây là một trong các phương pháp hiệu quả để giải quyết các bài toán đó. Trước tiên, ta tìm hiểu một số khái niệm về xích, chu trình và liên thông.

Định nghĩa 1.7. Giả sử G(X, E) là một đổ thị hay đa đồ thị vô hướng. Dãy các đỉnh của G(X, E):

0 = (1 − 1)n = (−1)kCk n.

được gọi là một xích hay một dây chuyền, nếu ∀i(1 ≥ i ≥ n − 1) cặp đỉnh xi, xi+1 kề nhau. Một xích với hai đầu trùng nhau, được gọi là một chu trình.

α = [x1, x2, . . . , xi, xi+1, . . . xn−1, xn]

Định nghĩa 1.8. Hai đỉnh x, y được gọi là cặp đỉnh liên thông, nếu hoặc giữa x và y có ít nhất một xích nối với nhau, hoặc tồn tại ít nhất một đường đi từ x sang y hoặc từ y sang x. Một đồ thị vô hướng được gọi là liên thông nếu mọi cặp đỉnh của nó đều liên thông.

Định nghĩa 1.9. Một đồ thị vô hướng liên thông, không có chu trình và có ít nhất một đỉnh được gọi là một cây. Như vậy, một cây bao gồm một gốc và các cành đi ra từ gốc và các cành phụ đi ra từ điểm cuối của cành khác. Các đặc điểm của cây được phát biểu trong các định lý sau:

Định lý 1.10. Một cây có n đỉnh có đúng n − 1 cạnh.

Chứng minh. Chứng minh bằng quy nạp theo số đỉnh n của cây. + Với n = 1. Hiển nhiên cây có một đỉnh không có cạnh nào cả. + Giả sử một cây bất kì với n đỉnh có đúng n − 1 cạnh. + Xét G là cây với n + 1 đỉnh tùy ý. Khi đó, G có ít nhất một đỉnh treo P nào đó. Xét đồ thị G − {P }. Vì P là đỉnh treo nên G − {P } là một đồ thị liên thông. Vì nếu giả sử ngược lại, đồ thị G − {P } có ít nhất hai thành phần liên thông G1 và G2 nào đó. Do G là đồ thị liên thông nên có một con đường nối G1 với G2 trong G. Rõ ràng, đường này phải đi qua đỉnh P và nhận đỉnh P làm đỉnh trong của nó. Vậy P có bậc ít nhất là hai, mâu thuẫn với giả thiết là P là đỉnh treo trong đồ thị G. Vậy G − {P } là một đồ thị liên thông. Do G không có chu trình, nên đồ thị G−{P } không có chu trình. Vậy đồ thị G−{P } là một cây có n đỉnh. Theo giả thiết quy nạp, đồ thị G − {P } có đúng n − 1 cạnh. Suy ra đồ thị G có đúng n cạnh, vì bậc của P trong G bằng 1. Vậy một cây có n đỉnh có đúng n − 1 cạnh.

Định lý 1.11. Giả sử H là một đồ thị vô hướng với n đỉnh (n > 1). Để đặc trưng cho đồ thị H là một cây thì sáu tính chất sau đây là tương đương: (1) H liên thông và không có chu trình; (2) H không có chu trình và có n − 1 cạnh; (3) H liên thông và có n − 1 cạnh; (4) H không có chu trình và nếu thêm một cạnh nối giữa hai đỉnh bất kì không kề nhau thì đồ thị nhận được H (cid:48) có một chu trình (và chỉ một mà thôi); (5) H liên thông và khi bớt một cạnh bất kì thì đồ thị mất tính liên thông;

Chứng minh. Định lý được chứng minh theo phương pháp vòng tròn (1) ⇒ (2) ⇒ (3) ⇒ (4) ⇒ (5) ⇒ (6) ⇒ (1). Kí hiệu số cạnh của đồ thị H bằng m; số thành phần liên thông bằng p. (1) ⇒ (2) : Theo tính chất (1), đồ thị H liên thông và đồ thị không có chu trình nên p = 1 và H có chu số ν(H) = m − n + p = m − n + 1 . Suy ra

(6) Mọi cặp đỉnh của H đều được nối với nhau bằng một xích trong H và chỉ một mà thôi.

Chứng tỏ, đồ thị H không có chu trình và có n − 1 cạnh. (2) ⇒ (3) : Theo tính chất (2) : m = n − 1 và chu số ν(H) = 0 nên

m − n + 1 = 0 hay m = n − 1.

Vậy H liên thông và có n − 1 cạnh. (3) ⇒ (4) : Theo tính chất (3) : p = 1, m = n − 1 nên

ν(H) = m − n + p = n − 1 − n + p = 0 =⇒ p = 1.

Suy ra H không có chu trình; Mặt khác , nếu thêm vào một cạnh nối giữa hai đỉnh kề nhau, thì đồ thị H (cid:48) nhận được sẽ có chu số :

ν(H) = m − n + p = n − 1 − n + 1 = 0.

Chứng tỏ đồ thị H (cid:48) có chu trình và chỉ một mà thôi. (4) ⇒ (5) : Lấy hai đỉnh bất kì của đồ thị H. Theo tính chất 4, nếu thêm vào cạnh (x, y) thì đồ thị mới nhận được H (cid:48) có chu trình, điều đó chứng tỏ giữa x, y đã có xích nối với nhau, tức là H đã liên thông. Giả sử bớt đi một cạnh nào đó, chẳng hạn (u, v) mà đồ thị nhận được vẫn liên thông. Điều này chứng tỏ trong đồ thị H, giữa các đỉnh u, v ngoài cạnh (u, v) còn một xích nữa nối giữa chúng, tức là trong H có ít nhất một chu trình đi qua u, v. Điều này mâu thuẫn với tính chất 4: Đồ thị H không có chu trình. Vậy, nếu bớt đi một cạnh tùy ý thì đồ thị nhận được từ H sẽ không liên thông. (5) ⇒ (6) : Giả sử trong H tồn tại cặp đỉnh nào đó, chẳng hạn x, y, được nối với nhau bằng từ hai xích trở lên. Khi đó, nếu ta bỏ đi một cạnh nào đó thuộc một trong hai xích này, thì xích còn lại vẫn đảm bảo cho x, y liên thông . Mâu thuẫn với tính chất 5. Do đó, mọi cặp đỉnh của H đều được nối với nhau bằng

ν(H (cid:48)) = m + 1 − n + 1 = n − 1 + 1 − n + 1 = 1.

một xích và chỉ một mà thôi. (6) ⇒ (1) : Giả sử H không liên thông. Khi đó có ít nhất một cặp đỉnh không có xích nối với nhau. Mâu thuẫn với tính chất 6. Vậy H liên thông. Giả sử H có chu trình. Khi đó, có ít nhất một cặp đỉnh nằm trên chu trình này được nối với nhau bằng ít nhất hai xích. Điều này cũng mâu thuẫn với tính chất 6. Bởi vậy đồ thị H liên thông và không có chu trình.

Ví dụ 1.10. [Đề thi HSG tại Liên Bang Nga 1961]. Cho n(n > 1) điểm được nối với nhau bằng những đoạn thẳng không cắt nhau sao cho từ mỗi điểm có thể đi tới những điểm khác bằng dãy các đoạn thẳng đã nối kế tiếp nhau, sao cho không có cặp điểm nào được nối với nhau bằng từ hai dãy đoạn thẳng trở lên. Chứng minh rằng, số đoạn thẳng đã nối bằng n − 1.

Lời giải. Giả sử n điểm được nối với nhau tạo thành một đồ thị T . Do mỗi điểm đều được nối với các điểm còn lại bằng một dãy các đoạn thẳng, tức là hai đỉnh tùy ý của đồ thị T đều liên thông với nhau. Do đó, đồ thị T là một đồ thị liên thông. Vì không có cặp điểm nào được nối với nhau bằng từ hai dãy đoạn thẳng trở lên, nên trong đồ thị T không có chu trình. Vì T là một đồ thị liên thông và không có chu trình nên nó là một cây với n đỉnh. Theo định lý 1.10, số cạnh của T bằng n − 1. Do đó, số đoạn thẳng đã nối bằng n − 1.

Để sử dụng cây trong các bài toán đếm, chúng ta dùng cành biểu diễn mỗi sự lựa chọn, các kết cục bằng các lá, đó là điểm cuối của cành, không có cành khác bắt đầu trên nó.

Ví dụ 1.11. Trong một trận đấu bóng bàn, Anh và Việt quy ước với nhau như sau: Người thắng cuộc là người đầu tiên thắng ba ván hoặc thắng hai ván liên tiếp. Hãy xác định số khả năng có thể xảy ra?

Lời giải. Ta sẽ dùng đồ thị cây để giải quyết bài toán này. Ta dùng A để kí hiệu Anh thắng, V để kí hiệu Việt thắng. Ta sẽ dùng đồ thị cây để mô tả toàn bộ các khả năng có thể xảy ra. Ta dùng S làm điểm xuất phát. + Ván đầu tiên có hai khả năng Anh thắng hoặc Việt thắng nên ta lấy hai điểm A và V sao cho 3 điểm S, A, V vẽ không thẳng hàng.

Nối S với A bằng một đoạn thẳng (tức Anh thắng); Nối S với V bằng một đoạn thẳng (tức Việt thắng). + Ván thứ hai: Cũng có hai khả năng xảy ra nên xuất phát: Từ A ta cũng lấy hai điểm, một điểm kí hiệu là A, điểm còn lại kí hiệu là V: Biểu diễn Anh thắng: nối A với A; Biểu diễn Việt thắng: nối A với V. Xuất phát từ V, ta cũng nối tương tự như trên. Vì quy ước người đầu tiên thắng ba ván hoặc hai ván liên tiếp là người thắng cuộc nên ta có một đồ thị cây.

2 Cây có 10 đỉnh treo nên có 10 khả năng xảy ra.

Ví dụ 1.12. Tại một giải bóng đá có 4 đội tham gia: Anh, Đức, Hà Lan, Thụy Điển vào chung kết. Có mấy dự đoán kết quả như sau: 1) Anh vô địch, Đức thứ nhì; 2) Hà Lan thứ nhì, Thụy Điển thứ ba; 3) Đức nhất, Thụy Điển thứ tư. Kết quả chứng tỏ mỗi dự đoán đúng được một đội. Hãy cho biết kết quả của xếp hạng?

Lời giải. Ta dùng các chữ cái A, D, H, T để lần lượt kí kiệu các đội Anh, Đức, Hà Lan, Thụy Điển. Dùng xi, (i = 1, 2, 3, 4) để kí hiệu đội xếp thứ i. Ta có thể dùng đồ thị cây để biểu diễn các dự đoán. Trước tiên, ta xây dựng cây dự đoán kết quả như sau: Lấy điểm O làm gốc của cây. + Để biểu diễn dự đoán thứ nhất, ta lấy hai điểm ghi tên hai đội Anh, Đức

bằng hai kí hiệu A1 và D2. Từ gốc nối với 2 điểm A1 và D2. + Để biểu diễn dự đoán thứ hai, từ mỗi đỉnh treo, ta kẻ hai cạnh nối với hai điểm H2 và T3. + Để biểu diễn dự đoán thứ 3, từ mỗi đỉnh treo, ta cũng kẻ hai cạnh nối với hai điểm D2 và T4. Ta có cây dự đoán kết quả như sau:

Cuối cùng, ta chọn đường biểu diễn dự đoán: Vì một đội không thể xếp ở hai thứ hạng và hai đội không thể xếp ở cùng một thứ hạng, nên những đường hoặc có hai kí hiệu trùng nhau hoặc một kí hiệu có hai chỉ số khác nhau thì đều bị loại. Vậy ta có kết quả: Anh vô địch, Hà Lan nhì, Đức thứ 3 và Thụy Điển thứ 4.

Chương 2

Một vài nguyên lý trong tổ hợp

2.1 Nguyên lý Dirichlet

Nguyên lý Dirichlet mang tên nhà toán học người Đức: Peter Gustav Dirichlet (1851- 1931), được phát biểu rất đơn giản như sau

thì tồn tại một hộp chứa ít nhất

Định lý 2.1. [Nguyên lý Dirichlet]. Nếu có N đồ vật được đặt vào k hộp (cid:105) + 1 đồ vật. Trong đó, N, k ∈ N∗ và N

(cid:104)N k

không chia hết cho k.

Chứng minh. Ta chứng minh định lý bằng lập luận phản chứng.

(cid:105)

Giả sử, không có hộp nào trong k hộp chứa nhiều hơn

đồ vật.

(cid:104) N k

Khi đó, tổng số đồ vật được chứa trong k hộp nhiều nhất là

(cid:105)

2.1.1 Nguyên lý Dirichlet

(cid:104) N k

(cid:105)

Điều này trái giả thiết. Suy ra, tồn tại một hộp chứa ít nhất

= N. k. < k. N k

(cid:104) N k

Điều phải chứng minh.

Nguyên lý Dirichlet là một trong các nguyên lý có nhiều ứng dụng rất hay, đặc biệt được khai thác nhiều trong các đề thi học sinh giỏi toán quốc gia và quốc tế. Tuy nhiên, trong nhiều áp dụng của nguyên lý Dirichlet các đối tượng đặt vào hộp phải chọn một cách khôn khéo và không phải lúc nào chúng ta cũng dễ dàng nhận ra "đồ vật" và "hộp". Bây giờ, chúng ta sẽ xét một vài ví dụ để thấy được điều này.

+ 1 đồ vật.

Ví dụ 2.1. Trong một tháng 30 ngày, một đội bóng chơi ít nhất mỗi ngày một trận, nhưng cả tháng chơi không quá 45 trận. Hãy chỉ ra rằng có những ngày liên tiếp mà đội bóng đã chơi tất cả 14 trận.

Lời giải. Gọi aj là số trận đấu mà đội bóng đã chơi kể từ ngày đầu tháng tới hết ngày j, j = 1, 30. Khi đó a1, a2, . . . , a30 là một dãy các số nguyên dương phân biệt và tăng dần với 1 ≤ aj ≤ 45, j = 1, 30. Mặt khác: a1 + 14, a2 + 14, . . . , a30 + 14 cũng là một dãy các số nguyên dương phân biệt và tăng dần với 15 ≤ aj + 14 ≤ 59, j = 1, 30. Như vậy, ta có 60 số nguyên dương a1, a2, . . . , a30, a1 + 14, a2 + 14, . . . , a30 + 14 luôn nhỏ hơn hoặc bằng 59. Vì các dãy a1, a2, . . . , a30 và a1 + 14, a2 + 14, . . . , a30 + 14 gồm các số phân biệt nên theo nguyên lý Dirichlet, tồn tại các chỉ số i, j sao cho ai = aj + 14 (j < i). Điều này chứng tỏ từ ngày j + 1 đến ngày i đội đã chơi đúng 14 trận.

Ví dụ 2.2. [VMO - 2004]. Cho tập A = {1; 2; . . . ; 16}. Hãy tìm số nguyên dương k nhỏ nhất sao cho trong mỗi tập con gồm k phần tử của A đều tồn tại hai số phân biệt a, b mà a2 + b2 là một số nguyên tố.

Lời giải. Ta thấy, nếu a, b cùng chẵn thì a2 + b2 là hợp số. Do đó, nếu mỗi tập con X có k phần tử của A mà có hai phần tử phân biệt a, b sao cho a2 + b2 là số nguyên tố thì X không thể chỉ chứa các số chẵn. Mà tập A có tất cả 8 số chẵn. Suy ra k ≥ 9. Ta chứng minh, k = 9 là giá trị nhỏ nhất cần tìm. Điều đó có nghĩa là với mọi tập con X gồm 9 phần tử của A luôn tồn tại hai phần tử phân biệt a, b mà a2 + b2 là một số nguyên tố. Thật vậy, ta chia tập A thành các cặp hai phần tử phân biệt a, b mà a2 + b2 là một số nguyên tố. Ta có tất cả 8 cặp:

Theo nguyên lý Dirichlet thì trong 9 phần tử của X có hai phần tử thuộc cùng một cặp. Ta có điều phải chứng minh. Vậy k = 9 là số nguyên dương nhỏ nhất thỏa mãn yêu cầu bài toán.

Chú ý 2.1. Cách chia tập A như trên không phải là duy nhất. Chẳng hạn, ta có thể chia tập A thành các cặp như sau:

(1; 4), (2; 3), (5; 8), (6; 11), (7; 10), (9; 16), (12; 13), (14; 15).

(1; 2), (3; 8), (4; 5), (6; 9), (7; 10), (11; 14), (12; 13), (15; 16).

Ví dụ 2.3. [Iberoamerica 1998]. Các đại diện của n (n ∈ N∗\{1}) quốc gia ngồi quanh một bàn tròn theo cách sao cho hai người ngồi sát bên phải hai đại diện bất kì có cùng quốc tịch thì phải có quốc tịch khác nhau. Hãy xác định (theo n) số lớn nhất có thể có các đại diện ngồi quanh bàn tròn đó.

i , x2

i , x3

i , . . . , xn+1

i , x2

i (N∗ (cid:51) i ≤ n).

i , . . . , xn

i , x2

i , x3

Lời giải. . Kí hiệu X1, X2, X3, . . . , Xn là n quốc gia có các đại diện ngồi quanh i , . . . (N∗ (cid:51) bàn tròn. Các đại diện có quốc tịch Xi sẽ được đánh số là x1 i ≤ n) i) Trước tiên, nếu có nhiều hơn n2 đại diện ngồi quanh bàn tròn thì theo nguyên lý Dirichlet, tồn tại i (N∗ (cid:51) i ≤ n) để quốc gia Xi có ít nhất n + 1 đại diện. Ta kí hiệu n + 1 đại diện đó là x1 i , x2 . Do chỉ có n quốc tịch nên trong số n + 1 người ngồi sát bên phải các đại diện x1 phải có hai người có cùng quốc tịch. (Mâu thuẫn với yêu cầu bài toán). Điều này chứng tỏ rằng có không quá n2 đại diện ngồi bàn tròn. ii) Tiếp theo, giả sử mỗi quốc gia có đúng n đại diện ngồi bàn tròn. Các đại diện của Xi là x1 Ta sẽ chứng minh bằng quy nạp theo n rằng có một cách sắp xếp toàn bộ n2 đại diện đó vào bàn tròn sao cho thỏa mãn yêu cầu bài toán. Mỗi cách sắp xếp toàn bộ n2 đại diện vào bàn tròn thực chất là một hoán vị

(2.1)

i |i, j ∈ N∗; i, j ≤ n} với quy ước:

2; x2

1; x1

1; x2

2) thỏa mãn mọi yêu cầu

i , . . . , xn

i , x2

i , x3

của tập hợp {xj 1. ak+1 là đại diện ngồi sát bên phải ak, với k nguyên dương và k < n2. 2. a1 ngồi sát bên phải an2. Thật vậy + Với n = 2 ta dễ thấy có cách sắp xếp (x1 của bài toán. + Giả sử với n ∈ N∗\{1} nào đó đã có một cách sắp xếp, mà ta vẫn giữ kí hiệu (2.1), thỏa mãn mọi yêu cầu bài toán. Khi đó có thể chứng minh được rằng: Với mỗi i ∈ N∗ và i ≤ n, tồn tại duy nhất j ∈ N∗ và j ≤ n sao cho người ngồi sát bên phải xj i cũng có quốc tịch Xi. (*) i (N∗ (cid:51) Thật vậy, giả sử n người ngồi sát bên phải các đại diện x1 i ≤ n) đều có quốc tịch khác Xi (có n − 1 quốc tịch như thế). Theo nguyên lý Dirichlet, có ít nhất hai người trong số họ phải có cùng quốc tịch. Mâu thuẫn với yêu cầu bài toán. Điều này chứng tỏ tồn tại j = ji sao cho người ngồi sát

(a1, a2, . . . , an2−1, an2)

i có cùng quốc tịch Xi.

i không có cùng quốc tịch Xi với người ngồi sát bên phải xji

n+1, x2

n+1, x3

n+1, . . . , xn+1

và i n+1. Khi đó,

n+1; xn+1 1

bên phải xji Mặt khác, nếu k ∈ N∗, n ≥ k (cid:54)= ji thì theo yêu cầu bài toán, người ngồi sát bên phải xk i . Chứng tỏ j = ji là tồn tại duy nhất. Như vậy, (*) đã được chứng minh. Trong (2.1), giả sử a1 và a2 có cùng quốc tịch, từ đó suy ra a1 phải khác quốc tịch với an2. Theo (*), với mỗi i ∈ N∗ và i ≤ n, tồn tại duy nhất ki ∈ N∗, ki ≤ n2 − 1 sao cho aki và aki+1 có cùng quốc tịch Xi. + Giả sử mỗi quốc gia Xi (N∗ (cid:51) i ≤ n) có thêm đại diện thứ n + 1 là xn+1 có thêm quốc gia Xn+1 với n + 1 đại diện là x1 từ bộ (2.1) bằng cách: n+1; xn+1 • Thay cặp (ak1; ak1+1) bởi bộ (ak1; x1 ; aki+1), với mỗi i ∈ N∗, 2 ≤ i ≤ n. n+1; xn+1 • Thay cặp (aki; aki+1) bởi bộ (aki; xi i Ta sẽ thu được một cách sắp xếp thỏa mãn mọi yêu cầu của bài toán cho trường hợp n + 1 quốc gia. Theo nguyên lý quy nạp (ii) đúng với mọi n ∈ N∗\{1}. Từ (i) và (ii), ta thấy số lớn nhất có thể có các đại diện ngồi quanh bàn tròn đã cho là n2.

Ví dụ 2.4. [Vô địch Trung Quốc 2000]. Có 2000 học sinh tham gia một cuộc thi trắc nghiệm gồm 5 câu hỏi; mỗi câu hỏi có 4 phương án trả lời và mỗi học sinh chỉ được phép chọn 1 trong 4 phương án tương ứng để trả lời câu hỏi. Tìm số tự nhiên n nhỏ nhất sao cho các học sinh có thể làm bài thi theo cách nào đó mà cứ n học sinh thì tìm được 4 học sinh (trong số n học sinh này) để hai học sinh nào trong số 4 học sinh đó cũng có bài làm khác nhau ở ít nhất là hai câu hỏi?

Lời giải. Trước tiên, ta chứng minh n ≤ 24 thì trong mọi trường hợp, yêu cầu bài toán không thỏa mãn. Xét I = {1, 2, 3, 4}. Suy ra I 5 là tập hợp tất cả các cách làm bài của học sinh. Khi đó, bài làm của mỗi học sinh được đặt tương ứng với bộ x = (x1; x2; x3; x4; x5) ∈ I 5, trong đó xi là số thứ tự của phương án mà học sinh đã chọn để trả lời câu hỏi thứ i, (1 ≤ i ≤ 5). Ngoài ra, nếu x ∈ I 5 ta cũng chấp nhận cách viết x ≡ (x1; x(cid:48)) với x(cid:48) := (x2; x3; x4; x5) ∈ I 4. Bằng cách như vậy, ta thấy I 5 được phân hoạch thành 44 = 256 tập con (rời nhau). Mỗi tập con gồm đúng 4 bộ chỉ khác nhau ở thành phần thứ nhất, tức là tập con có dạng

; ak1+1);

Ax(cid:48) := {(1; x(cid:48)), (2; x(cid:48)), (3; x(cid:48)), (4; x(cid:48))} ⊂ I 5

với x(cid:48) ∈ I 4. Vì 2000 > 7.256 nên theo nguyên lý Dirichlet có tám học sinh (khác nhau )A1; A2; . . . ; A8, mà bài làm của họ thì ứng với các bộ thuộc cùng một tập con A nào đó (trong số 256 tập con nói trên). Nhưng 2000 - 8 = 1992 > 7. 256 nên theo nguyên lý Dirichlet, tồn tại tám học sinh (khác nhau, trong số 1992 học sinh còn lại ), là B1; B2; . . . ; B8, có bài làm ứng với các bộ thuộc cùng một tập con B nào đó (trong số 256 tập con nói trên). Cuối cùng, vẫn có 1992 - 8 = 1984 > 7. 256 nên theo nguyên lý Dirichlet một lần nữa, từ 1984 học sinh còn lại, tồn tại tám học sinh (khác nhau ), là C1; C2, . . . ; C8, mà bài làm của họ ứng với các bộ trong cùng một tập con C nào đó. Như vậy, từ 4 học sinh bất kì trong số 24 học sinh

ta luôn chọn được hai học sinh có bài làm tương ứng với các bộ thuộc cùng một tập con (một trong 3 tập con A, B, C). Chẳng hạn, đó là các học sịnh Ai, Aj(i, j ∈ Z, 1 ≤ i < j ≤ 8) mà bài làm tương ứng với hai bộ trong tập con A. Mà theo cách xây dựng các tập con ở trên, bài làm của hai học sinh này chỉ khác nhau ở thành phần thứ nhất, tức là bài làm của hai học sinh này chỉ khác nhau tối đa ở một câu hỏi. Như vậy, yêu cầu của bài toán không thỏa mãn. Bây giờ, ta chứng minh rằng với n = 25 thỏa mãn yêu cầu bài toán. Xét

5 (cid:88)

A1; A2; . . . ; A8; B1; B2; . . . ; B8; C1; C2; . . . ; C8,

i=1

Nhận xét: S gồm đúng 4 × 4 × 4 × 4 × 1 = 256 bộ. Hơn nữa, ta có

Với x, y ∈ S mà x (cid:54)= y thì ∃i, j ∈ N∗, i < j ≤ 5, xi (cid:54)= yi, xj (cid:54)= yj.

Lấy D là một tập con có 250 phần tử của S. Vì 2000 = 8.250 nên với mỗi x ∈ D, tồn tại đúng 8 học sinh có bài làm cùng ứng với bộ x. Khi đó, ta có 25 > 8. 3 nên theo nguyên lý Dirichlet, cứ 25 học sinh thì tìm được 4 học sinh (trong số 25 học sinh này) mà có bài làm ứng với bộ x, y, z, t ∈ D ⊂ S đôi một khác nhau. Và theo nhận xét trên, hai học sinh nào trong số 4 học sinh cũng có bài làm khác nhau ở ít nhất là hai câu hỏi. Chứng tỏ, n = 25 thỏa mãn yêu cầu bài toán. Vậy n = 25 là số tự nhiên bé nhất phải tìm.

S := {x ∈ I 5| xi = 0(mod4)}.

Hình học tổ hợp là một nhánh mới của hình học và nó là một trong các ứng dụng không thể thiếu của toán tổ hợp. Hình học tổ hợp thường xuyên xuất hiện trong các đề thi học sinh giỏi quốc gia và quốc tế. Nguyên lý Dirichlet là một trong những phương pháp thông dụng và hiệu quả để giải các bài toán hình học tổ hợp. Sau đây, ta xét một số mệnh đề (thực chất là nguyên lý Dirichlet áp dụng cho độ dài các đoạn thẳng, diện tích các hình phẳng, thể tích các vật thể) hay sử dụng nhiều trong các bài toán hình học tổ hợp.

Mệnh đề 2.1. [Nguyên lý Dirichlet cho diện tích] Giả sử K là một hình phẳng, còn K1, K2, . . . , Kn là các hình phẳng sao cho Ki ⊆ K với i = 1, 2, . . . , n và

2.1.2 Nguyên lý Dirichlet áp dụng trong hình học tổ hợp

trong đó, SK là diện tích hình phẳng K và SKi là diện tích hình phẳng Ki, với i = 1, 2, . . . , n. Khi đó, tồn tại ít nhất hai hình phẳng Ki và Kj (1 ≤ i ≤ j ≤ n) sao cho Ki và Kj có điểm trong chung. Ở đây, ta nói điểm P là điểm trong của tập hợp A trên mặt phẳng, nếu như tồn tại hình tròn tâm P bán kính đủ bé sao cho hình tròn này nằm trọn trong A. Tương tự, ta cũng có nguyên lý Dirichlet cho độ dài các đoạn thẳng và thể tích các vật thể. Nguyên lý Dirichlet cho trường hợp vô hạn các phần tử như sau:

Mệnh đề 2.2. [Nguyên lý Dirichlet vô hạn]. Nếu chia một tập hợp vô hạn các đồ vật vào hữu hạn các hộp. thì có ít nhất một hộp chứa vô hạn đồ vật. Tiếp theo, ta trình bày một số bài toán để thấy được ứng dụng của nguyên lý Dirichlet trong các bài toán hình học tổ hợp.

SK < SK1 + SK2 + · · · + SKn

Ví dụ 2.5. Trong hình vuông có cạnh bằng 1, đặt 101 điểm bất kì, phân biệt. Chứng minh rằng, có ít nhất 5 trong số 101 điểm đó nằm trong một hình tròn bán kính

Lời giải. Chia hình vuông thành 25 hình vuông con bằng nhau có cạnh bằng 1 . Theo nguyên lý Dirichlet, tồn tại ít nhất một hình vuông con (α) chứa ít 5 nhất 5 trong số 101 điểm đã cho.

. 1 7

√

. Vậy

Đường tròn ngoại tiếp hình vuông (α) có bán kính r =

5 điểm nói trên nằm trong đường tròn đồng tâm với đường tròn ngoại tiếp 1 hình vuông (α) và có bán kính bằng . 7

= < 2 5 1 2 1 7 1 √ 5 2

Ví dụ 2.6. Tìm số n nhỏ nhất sao cho nếu có n điểm trong hình chữ nhật 3 × 4 thì luôn có hai điểm trong chúng có khoảng cách nhỏ hơn

Lời giải. . Lấy 5 điểm A, B, C, D, E, trong đó, ABCD là hình chữ nhật, tâm E, cạnh 3 × 4 cho trước. Ta thấy, khoảng cách giữa hai điểm tùy ý trong 5 √ điểm đó là 3, 4, hoặc

√ 5.

, đều lớn hơn

5. Như vậy, n ≥ 6. 5 2

Ta chứng minh, n = 6 là giá trị nhỏ nhất cần tìm. Ta chia hình chữ nhật ra thành 5 hình có đường kính 5 như hình dưới.

√

Theo nguyên lý Dirichlet, trong 6 điểm tùy ý luôn có hai điểm cùng thuộc 5. Vậy n = 6 vào một hình, tức là khoảng cách giữa chúng không vượt quá là giá trị nhỏ nhất thỏa mãn yêu cầu bài toán.

Chú ý 2.2. Đường kính của một hình H là khoảng cách lớn nhất giữa hai điểm của hình đó.

Ví dụ 2.7. Cho 1000 điểm M1, M2, . . . , M1000 trên mặt phẳng. Vẽ một đường tròn bán kính 1 tùy ý. Chứng minh rằng tồn tại điểm S trên đường tròn sao cho SM1 + SM2 + · · · + SM1000 ≥ 1000.

Lời giải. Xét đường kính tùy ý S1S2 của đường tròn, ở đây S1, S2 là hai đầu

√

của đường kính. Vì S1S2 = 2 nên ta có



S1M1 + S2M1 ≥ S1S2 = 2

 

S1M2 + S2M2 ≥ S1S2 = 2 ...

Cộng vế với vế của 1000 bất đẳng thức trên ta có:

S1M1000 + S2M1000 ≥ S1S2 = 2.

Theo nguyên lý Dirichlet, suy ra trong hai tổng của vế trái của (1) có ít nhất một tổng lớn hơn hoặc bằng 1000. Giả sử

(S1M1 + S1M2 + · · · + S1M1000) + (S2M1 + S2M2 + · · · + S2M1000) ≥ 2000. (1)

Khi đó lấy S ≡ S1.

Ví dụ 2.8. Trên mặt phẳng, cho năm điểm A, B, C, D, E có các tọa độ là các số nguyên. Chứng minh rằng trong số các tam giác được tạo thành từ 5 điểm đó có ít nhất ba tam giác có diện tích nguyên.

Lời giải. Nhận xét rằng nếu thay đổi tọa độ của một đỉnh một số chẵn đơn vị thì tính nguyên của diện tích không đổi. Ta dịch chuyển tọa độ của các điểm đã cho những số chẵn đơn vị sao cho ta thu được các điểm mới A(cid:48), B(cid:48), C(cid:48), D(cid:48), E(cid:48) mà tọa độ chỉ là các số 0 hoặc 1. Chỉ có bốn trường hợp là:

S1M1 + S1M2 + · · · + S1M1000 ≥ 1000.

Mà ta có 5 điểm A(cid:48), B(cid:48), C(cid:48), D(cid:48), E(cid:48) nên theo nguyên lý Dirichlet, có hai điểm trong số 5 điểm trùng nhau. Giả sử A(cid:48) ≡ B(cid:48) ≡ (0; 0). Khi đó, ba tam giác OOC(cid:48), OOD(cid:48), OOE(cid:48) sẽ có diện tích bằng 0 ∈ Z nên các tam giác ABC, ABD, ABE sẽ có diện tích nguyên.

Ví dụ 2.9. Trong một hình vuông cạnh bằng 1, ta vẽ một số đường tròn có tổng chu vi là 10. Chứng minh rằng tồn tại một đường thẳng cắt ít nhất 4 đường tròn trong số chúng.

Lời giải. Giả sử hình vuông có cạnh bằng 1 đó là ABCD và có n đường tròn trong hình vuông ABCD có tổng chu vi bằng 10. Chiếu tất cả các đường tròn nằm trong nó lên cạnh AB. Gọi hình chiếu của đường tròn (Oi) là một đoạn

(0; 0), (0; 1), (1; 0), (1; 1).

thẳng AiBi bằng đường kính di của nó. Vì tổng chu vi của các đường tròn là 10 nên

n (cid:88)

i=1

hay

n (cid:88)

πdi = 10

i=1

Vì các đoạn AiBi chứa trong AB và có tổng độ dài lớn hơn 3AB nên tồn tại một điểm M là điểm trong của ít nhất 4 đoạn AiBi nào đó. Khi đó, đường thẳng d đi qua M, vuông góc với AB cắt ít nhất 4 đường tròn có hình chiếu là 4 đoạn AiBi nói trên.

2.2 Nguyên lý bù trừ

Trong nhiều bài toán tổ hợp, chúng ta phải tính số phần tử của hợp của hai tập hợp không rời nhau. Khi đó, ta không thể áp dụng quy tắc cộng cho hai tập hợp nữa. Để giải được các bài toán đó, ta phải áp dụng quy tắc cộng mở rộng cho hai tập hợp như sau: Đối với hai tập hợp hữu hạn bất kì A và B ta có

(2.2)

(cid:12)A ∪ B(cid:12) (cid:12)

(cid:12) = (cid:12)

(cid:12)A(cid:12)

(cid:12) + (cid:12)

(cid:12)B(cid:12)

(cid:12) − (cid:12)

(cid:12)A ∩ B(cid:12) (cid:12).

Tổng quát, quy tắc cộng mở rộng cho nhiều tập hợp ta được Nguyên lý bù trừ.

n (cid:92)

Định lý 2.2. [Nguyên lý bù trừ]. Đối với bộ n tập hợp hữu hạn A1, A2, . . . An ta có n (cid:88)

n (cid:91)

(cid:88)

π > 3 = 3AB. AiBi = AiBi = 10 ⇔ 10 π

(cid:12) (cid:12)Ai∩Aj ∩Ak

(cid:12) (cid:12)Ai

(cid:12) (cid:12)−

(cid:12) (cid:12)Ai∩Aj

(cid:12) (cid:12)+

(cid:12)−· · ·+(−1)n−1(cid:12) (cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12).

(cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12) =

i=1

1≤i,j≤n

1≤i,j,k≤n

(2.3)

Chứng minh. Ta chứng minh đẳng thức (2.3) bằng phép quy nạp theo n như sau: • Với n = 1 đẳng thức (2.3) hiển nhiên đúng. • Với n = 2 ta có

(cid:12) (cid:12)A1 ∪ A2

(cid:12) = (cid:12) (cid:12)

(cid:12)A1

(cid:12) + (cid:12) (cid:12)

(cid:12)A2

(cid:12) − (cid:12) (cid:12)

(cid:12)A1 ∩ A2

(cid:12) (cid:12).

Ai Ai

Đẳng thức luôn đúng. Suy ra đẳng thức (2.3) đúng với n = 2. • Giả sử, đẳng thức (2.3) đúng với n ≥ 2 tập hợp tùy ý. Tức là

n (cid:88)

n (cid:91)

(cid:88)

n (cid:92)

(cid:88)

(cid:12) (cid:12)Ai

(cid:12) (cid:12)−

(cid:12) (cid:12)Ai∩Aj

(cid:12) (cid:12)+

(cid:12) (cid:12)Ai∩Aj ∩Ak

(cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12) =

(cid:12)−· · ·+(−1)n−1(cid:12) (cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12).

i=1

1≤i,j≤n

i=1

1≤i,j,k≤n

Ta phải chứng minh đẳng thức (2.3) đúng với n + 1 tập hợp. Tức là

n+1 (cid:88)

n+1 (cid:91)

(cid:88)

n+1 (cid:92)

(cid:88)

Ai Ai

(cid:12) (cid:12)Ai

(cid:12) (cid:12)−

(cid:12) (cid:12)Ai∩Aj

(cid:12) (cid:12)+

(cid:12) (cid:12)Ai∩Aj∩Ak

(cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12) =

(cid:12)−· · ·+(−1)n(cid:12) (cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12).

i=1

1≤i,j≤n+1

i=1

1≤i,j,k≤n+1

Thật vậy, ta xét n + 1 tập hợp tùy ý A1, A2, . . . , An, An+1. Ta có

n (cid:91)

Ai Ai

i=1

Suy ra

n (cid:91)

(cid:12) (cid:12)(A1 ∪ A2 ∪ · · · ∪ An) ∩ An+1

(cid:12) (cid:12) =

(cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (Ai ∩ An+1) (cid:12).

i=1

Theo giả thiết quy nạp, ta có

n (cid:91)

n (cid:88)

(cid:88)

(cid:12) (cid:12)Ai ∩ An+1

(cid:12) (cid:12) −

(cid:12) (cid:12)Ai ∩ Aj ∩ An+1

(cid:12) (cid:12) +

(cid:12) (cid:12)Ai ∩ Aj ∩ Ak ∩ An+1

(cid:12) (cid:12)

(cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12) = (Ai ∩ An+1)

i=1

1≤i,j≤n

1≤i,j,k≤n

(A1 ∪ A2 ∪ · · · ∪ An) ∩ An+1 = (Ai ∩ An+1).

(cid:12)A1 ∩ A2 ∩ · · · ∩ An ∩ An+1

(cid:12) (cid:12)

Đặt A = A1 ∪ A2 ∪ · · · ∪ An, B = An+1 và áp dụng đẳng thức

(cid:12)A ∪ B(cid:12) (cid:12)

(cid:12) = (cid:12)

(cid:12)A(cid:12)

(cid:12) + (cid:12)

(cid:12)B(cid:12)

(cid:12) − (cid:12)

(cid:12)A ∩ B(cid:12) (cid:12)

ta được

(cid:12) (cid:12)A1 ∪ A2 ∪ · · · ∪ An ∪ An+1

(cid:12)A1 ∪ A2 ∪ · · · ∪ An

(cid:12)(A1 ∪ A2 ∪ · · · ∪ An) ∩ An+1

(cid:12) (cid:12)

(cid:12) + (cid:12) (cid:12)

n (cid:92)

n (cid:88)

(cid:88)

− · · · + (−1)n−1(cid:12)

(cid:12)An+1

(cid:12) (cid:12)

(cid:12) (cid:12)Ai ∩ Aj ∩ Ak

(cid:12) (cid:12)Ai

(cid:12) (cid:12) −

(cid:12) (cid:12)Ai ∩ Aj

(cid:12) = (cid:12) (cid:12) (cid:12) (cid:12) +

(cid:12) (cid:12) + (cid:12) (cid:12)

(cid:12) − (cid:12) (cid:12) (cid:12)An+1 (cid:12) − · · · + (−1)n−1(cid:12) (cid:12) (cid:12) (cid:12)

i=1

1≤i,j≤n

1≤i,j,k≤n

i=1 (cid:16) n (cid:88)

(cid:88)

= Ai

(cid:12) (cid:12)Ai ∩ Aj ∩ Ak ∩ An+1

(cid:12) (cid:12)

(cid:12) (cid:12)Ai ∩ An+1

(cid:12) (cid:12) −

(cid:12) (cid:12)Ai ∩ Aj ∩ An+1

(cid:12) (cid:12) +

i=1

1≤i,j≤n

1≤i,j,k≤n

(cid:17)

n+1 (cid:92)

−

(cid:12) (cid:12) (cid:12)

i=1

n+1 (cid:88)

(cid:88)

n+1 (cid:92)

Ai − · · · + (−1)n−1(cid:12) (cid:12) (cid:12)

(cid:12) (cid:12)Ai

(cid:12) (cid:12) −

(cid:12) (cid:12)Ai ∩ Aj

(cid:12) (cid:12) +

(cid:12) (cid:12)Ai ∩ Aj ∩ Ak

(cid:12) − · · · + (−1)n(cid:12) (cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12).

i=1

1≤i,j≤n+1

i=1

1≤i,j,k≤n+1

= Ai

Chứng tỏ đẳng thức (2.3) đúng với n + 1 tập hợp. Vậy đẳng thức (2.3) đúng với mọi n ≥ 1.

Nhận xét 2.1. Trong trường hợp đặc biệt khi

|S| = m, |S − (A1 ∪ A2 ∪ · · · ∪ An)| = mo,

|Ai| = m1, i = 1, n,

|Ai ∩ Aj| = m2,

|Ai ∩ Aj ∩ Ak| = m3,

. . . ,

thì ta có

(2.4)

|A1 ∩ A2 ∩ · · · ∩ An| = mn,

nm1 − C2

nm2 + C3

nm3 − · · · + (−1)n−1Cn

(2.5)

Hay mo = m − C1

nm1 + C2

nm2 − C3

n mn. nm3 + · · · + (−1)nCn

n mn.

Nhận xét 2.2. Ta đồng nhất tập Ak với tính chất Ak cho trên một tập X nào đó và đếm xem có bao nhiêu phần tử thuộc X không thỏa mãn bất kì tính chất Ak nào cả. Gọi N là số cần đếm, N là số phần tử của X. Ta có

|A1 ∪ A2 ∪ · · · ∪ An| = C1

(cid:12)A1 ∪ A2 ∪ · · · ∪ An

(cid:12) (cid:12).

Sau đây, ta xét một số ví dụ áp dụng nguyên lý trên.

Ví dụ 2.10. Hỏi trong tập X = {1, 2, 3, . . . , 2014} có bao nhiêu số không chia hết cho bất cứ số nào trong các sô 3, 4, 7, 11?

Lời giải. Gọi Ai = {x ∈ X : x chia hết cho i}, i = 3, 4, 7, 11. Khi đó A3 ∪ A4 ∪ A7 ∪ A11 là tập các số chia hết cho ít nhất một trong bốn số 3, 4, 7, 11. Suy ra số các số trong X không chia hết cho bất cứ số nào trong bốn số 3, 4, 7, 11 là

N = N − (cid:12)

N = |X| − |A3 ∪ A4 ∪ A7 ∪ A11|.

Ta có

|X| = 2014;

|A3 ∪ A4 ∪ A7 ∪ A11| = |A3| + |A4| + |A7| + |A11| − |A3 ∩ A4| − |A3 ∩ A7| − |A3 ∩ A11|

− |A4 ∩ A7| − |A4 ∩ A11| − |A7 ∩ A11| + |A3 ∩ A4 ∩ A7|

+ |A3 ∩ A4 ∩ A11| + |A4 ∩ A7 ∩ A11| + |A3 ∩ A7 ∩ A11|

Trong đó

(cid:3) = 183.

(cid:3) = 503, |A7| = (cid:2)2014 7

(cid:3) = 287, |A11| = (cid:2)2014 11 (cid:3) = 61,

(cid:3) = 26.

(cid:3) = 95, |A3 ∩ A11| = (cid:2)2014 3.11 (cid:3) = 45, |A7 ∩ A11| = (cid:2)2014 7.11

(cid:3) = 6,

(cid:3) = 15, |A4∩A7∩A11| = (cid:2) 2014 4.7.11

(cid:3) = 2.

− |A3 ∩ A4 ∩ A7 ∩ A11|.

(cid:3) = 671, |A4| = (cid:2)2014 4 (cid:3) = 167, |A3 ∩ A7| = (cid:2)2014 3.7 (cid:3) = 71, |A4 ∩ A11| = (cid:2)2014 4.11 (cid:3) = 23, |A3∩A4∩A11| = (cid:2) 2014 3.4.11 (cid:3) = 8, |A3 ∩ A4 ∩ A7 ∩ A11| = (cid:2) 2014 3.4.7.11

Ở đây, kí hiệu [r] để chỉ số nguyên lớn nhất không vượt quá r. Suy ra

|A3| = (cid:2)2014 3 |A3 ∩ A4| = (cid:2)2014 3.4 |A4 ∩ A7| = (cid:2)2014 4.7 |A3∩A4∩A7| = (cid:2) 2014 3.4.7 |A3 ∩ A7 ∩ A11| = (cid:2) 2014 3.7.11

Vậy số các số không chia hết cho bất kì số nào trong các số 3, 4, 7, 11 là 785 số.

Ví dụ 2.11. [Công thức hàm Euler]. Với mỗi số nguyên dương n > 1, kí hiệu φ(n) là số các số nguyên dương bé hơn n và nguyên tố cùng nhau với n. Hàm φ(n) được gọi là hàm Euler. Chứng minh rằng

(cid:16)

m (cid:89)

(cid:17) ,

N = 2014−(cid:0)671+503+287+183−167−95−61−71−45−26+23+15+6+8−2(cid:1) = 785.

i=1

trong đó p1, p2, . . . , pm là các ước nguyên tố phân biệt của n.

Chứng minh. Kí hiệu S = {1, 2, . . . , n}. Ta đếm xem trong tập S có bao nhiêu số chia hết cho ít nhất một trong các số p1, p2, . . . , pm. Gọi Ai = {k ∈ S : k chia hết cho pi}, i = 1, 2, , . . . , m. Khi đó A1 ∪ A2 ∪ · · · ∪ Am là tập hợp các số chia hết cho ít nhất một trong các số p1, p2, . . . , pm.

φ(n) = n 1 − 1 pi

Ta có |Ai| =

. Với mỗi cặp i, j, i (cid:54)= j, tập Ai ∩ Aj bao gồm tất cả các số thuộc

. Tương tự tính lực lượng của các tập giao

n pi

khác. Do đó, theo nguyên lý Bù trừ ta có

m (cid:88)

(cid:88)

T là bội của pipj và |Ai ∩ Aj| = n pipj

1≤i

(cid:88)

− + − . . . |A1 ∪ A2 ∪ · · · ∪ Am| = n pi n pipj

i=1 (−1)k+1

1≤i1

Do φ(n) chính bằng số các số không chia hết cho tất cả các số p1, p2, . . . , pm nên

(cid:16)

+ · · · + (−1)m+1 . + n pipjpk n p1p2 . . . pm n pi1pi2 . . . pik

(cid:88)

i=1

1≤i

(cid:17)

(cid:88)

m (cid:89)

φ(n) = n − |A1 ∪ A2 ∪ · · · ∪ Am| m (cid:88) = n + − + . . . 1 − 1 pi 1 pipj 1 pipjpk

(cid:1).

(cid:0)1 −

1≤i1

(cid:0)1 −

Vậy ta nhận được công thức hàm Euler φ(n) = n (cid:81)m i=1

i=1 1 (cid:1). pi

Ví dụ 2.12. [VMO 1995, bảng B] Hỏi từ các chữ số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số có 10 chữ số thỏa mãn đồng thời các điều kiện sau:

(i) Trong mỗi số, mỗi chữ số có mặt đúng hai lần.

(ii) Trong mỗi số, hai chữ số giống nhau không đứng cạnh nhau

Lời giải. Gọi N là số các chữ số cần tìm và A là tập hợp gồm tất cả các số có 10 chữ số lập từ các chữ số 1, 2, 3, 4, 5 thỏa mãn điều kiện (i). Kí hiệu Ai là tập gồm các số thuộc A, mà trong mỗi số đều có hai chữ số i đứng cạnh nhau , i = 1, . . . , 5. Khi đó theo nguyên lý bù trừ ta có: 5 (cid:91)

+ · · · + + = n (−1)m p1p2 . . . pm 1 pi (−1)k pi1pi2 . . . pik

(cid:12) (cid:12)

i=1 5 (cid:88)

(cid:88)

Ai N = |A| − (cid:12) (cid:12)

i=1

1≤i1

(cid:88)

5 (cid:92)

= |A| − |Ai| + |Ai1 ∩ Ai2| − |Ai1 ∩ Ai2 ∩ Ai3|

(2.6)

(cid:12) (cid:12).

i=1

1≤i1

+ Ai |Ai1 ∩ Ai2 ∩ Ai3 ∩ Ai4| − (cid:12) (cid:12)

Ta có

(2.7)

Xét k bất kì thuộc tập {1, 2, 3, 4, 5} và xét bộ (i1, i2, . . . , ik) bất kì thỏa mãn 1 ≤ i1 < i2 < · · · < ik ≤ 5. Gọi T là tập gồm tất cả các số có (10 − k) chữ số được lập từ các chữ số 1, 2, 3, 4, 5 mà trong mỗi số đó: mỗi chữ số i1, i2, . . . , ik đều có mặt đúng một lần, còn các chữ số khác, mỗi chữ số đều có mặt đúng hai lần. Đặt tương ứng mỗi chữ số a ∈ Ai1 ∩ Ai2 ∩ · · · ∩ Aik, với số nhận được từ a bằng cách bỏ đồng thời ở a một chữ số i1, một chữ số i2, . . . , một chữ số ik. Ta thấy, tương ứng nói trên xác lập một song ánh từ Ai1 ∩ Ai2 ∩ · · · ∩ Aik đến T . Khi đó

|A| = 10! 25 .

(2.8)

Từ (2.6), (2.7), (2.8) ta suy ra

. |Ai1 ∩ Ai2 ∩ · · · ∩ Aik| = |T | = (10 − k)! 25−k

Ví dụ 2.13. Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì. Hỏi số khả năng không có lá thư nào bỏ đúng địa chỉ?

Lời giải. Gọi Dn là số khả năng không có lá thư nào bỏ đúng địa chỉ. Gọi A là tập hợp tất cả các cách bỏ thư. Ai là tập hợp các cách bỏ thư sao cho lá thư thứ i bỏ đúng địa chỉ. Khi đó

n (cid:91)

N = 10! 25 − C1 9! 24 + C2 8! 23 − C3 7! 22 + C4 6! 21 − 5! 20 = 39480.

(cid:12) (cid:12),

(cid:84)s

i=1 (cid:12) (cid:12) = (n − s)!. Theo công thức (2.5) ta

j=1 Aij

trong đó |A| = n!, |Ai| = (n − 1)!, (cid:12) (cid:12) có

n (cid:88)

Ai Dn = |A| − (cid:12) (cid:12)

n(n − 1)! + C2

n(n − 2)! − · · · + (−1)nCn

n (n − n)! =

ni!.

i=0

Vậy

n (cid:88)

(−1)n−iCi Dn = n! − C1

ni! =

i=0

với quy ước Do = 1.

(−1)n−i = (−1)n−iCi Dn = n! (n − i)! (−1)i n! i!

Bài toán trên gọi là bài toán bỏ thư và số Dn trong bài toán được gọi là

số mất thứ tự. Từ bài toán bỏ thư, ta có bài toán tổng quát sau:

Bài toán 2.1. [Bài toán hỗn độn.] Cho một tập X gồm n phần tử. Một hỗn độn trên tập X là một hoán vị trên tập này mà:

Hãy tìm số các hỗn độn trên tập X. Lập luận tương tự ví dụ trên, ta có số các hỗn độn trên X là

(cid:17)

n (cid:88)

f (i) (cid:54)= i với mọi i = 1, 2, . . . , n.

(cid:16) 1 2!

i=0

Số hỗn độn trên tập n phần tử xấp xỉ bằng 0, 36788n!. Cuối cùng, ta xét một ứng dụng rất hay của nguyên lý bù trừ. Đó là bài toán phân hoạch. Trước tiên, ta có định nghĩa về phân hoạch như sau:

Định nghĩa 2.1. Giả sử X là tập có n phần tử. Một phân hoạch của tập X là một họ các tập con {A1, A2, . . . , Ak} của X thỏa mãn các tính chất sau đây:

(i) Ai (cid:54)= ∅, 1 ≤ i ≤ k;

(ii) Ai ∩ Aj = ∅, 1 ≤ i < j ≤ k;

(iii) A1 ∪ A2 · · · ∪ Ak = X.

Phân hoạch trên còn được gọi là phân hoạch k khối.

Ví dụ 2.14. [Bài toán phân hoạch]. Cho trước số n và k. Hãy tìm số các phân hoạch của tập n phần tử được phân thành k khối.

Lời giải. Kí hiệu S(n, k) là số các phân hoạch của tập n phần tử được phân thành k khối. Dễ thấy rằng, mỗi phân hoạch của tập n phần tử được phân thành k khối tạo nên k! toàn ánh từ tập n phần tử lên tập k phần tử và ngược lại. Vậy thay vì tìm số phân hoạch ta đi tìm số các toàn ánh này. Kí hiệu Y là tập hợp có k phần tử. Xét tất cả các toàn ánh f : X −→ Y . Nghĩa là các ánh xạ từ X sang Y mà f (X) = Y Kí hiệu số các toàn ánh này là sn,k. Ta có mối quan hệ sau đây:

= n! − + . Dn = (−1)i n! i! 1 3! 1 4! − · · · + (−1)n 1 n!

(2.9)

S(n; k) = sn,k. 1 k!

Giả sử

Kí hiệu

Y = {y1, y2, . . . , yk}.

Hiển nhiên:

k (cid:91)

Fi = {f : X −→ Y | yi /∈ f (X)}, i = 1, 2, . . . , k.

i=1

i=1 Fi.

Số tất cả các ánh xạ f : X −→ Y là kn. Vậy ta chỉ cần tìm lực lượng của tập hợp (cid:83)k Áp dụng nguyên lý bù trừ để giải quyết việc này. Chú ý, giao của i tập hợp Fp1 ∩ Fp2 ∩ · · · ∩ Fpi chính là tất cả các ánh xạ f : X −→ Y mà yp1, yp2, . . . , ypi /∈ f (X) và bằng tập các ánh xạ:

f (X) (cid:54)= Y ⇐⇒ f ∈ Fi.

Vậy số các ánh xạ này là (k − i)n. Theo nguyên lý bù trừ thì ta có:

k (cid:91)

k−1 (cid:88)

f : X −→ Y \ {yp1, yp2, . . . , ypi}.

(cid:12) (cid:12) = kn −

k(k − i)n =

k(k − i)n.

i=1

i=0

Theo công thức (2.9) ta có công thức tính số phân hoạch k khối như sau:

k−1 (cid:88)

(−1)iCi (−1)iCi Fi sn,k = kn − (cid:12) (cid:12)

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

i=0

Trong một số bài toán, ta có thể linh hoạt kết hợp các nguyên lý khác nhau

để giải.

Ví dụ 2.15. Trong hình vuông có diện tích bằng 6, đặt 3 đa giác có diện tích bằng 3. Chứng minh rằng luôn tìm được hai đa giác mà diện tích phần chung của chúng không nhỏ hơn 1.

Lời giải. Gọi 3 đa giác là M1, M2, M3. Kí hiệu |A| là diện tích của hình phẳng A. Khi đó, theo nguyên lý bù trừ ta có:

(cid:12) (cid:12)M1∪M2∪M3

(cid:12) = |M1|+|M2|+|M3|−(cid:0)|M1∩M2|+|M2∩M3|+|M3∩M1|(cid:1)+(cid:12) (cid:12)

(cid:12)M1∩M2∩M3

(cid:12) (cid:12).

(−1)iCi S(n,k) = 1 k!

Theo giả thiết ta có |M1| = |M2| = |M3| = 3. Ta lại có M1 ∪ M2 ∪ M3 nằm trong hình vuông có diện tích bằng 6 nên ta có bất đẳng thức sau:

(cid:12)M1 ∩ M2 ∩ M3

(cid:12) (cid:12).

Hay

6 ≥ 9 − (cid:0)|M1 ∩ M2| + |M2 ∩ M3| + |M3 ∩ M1|(cid:1) + (cid:12)

(cid:12)M1 ∩ M2 ∩ M3

(cid:12) (cid:12).

Do (cid:12)

(cid:12)M1 ∩ M2 ∩ M3

(cid:12) (cid:12) ≥ 0 ta suy ra

|M1 ∩ M2| + |M2 ∩ M3| + |M3 ∩ M1| ≥ 3 + (cid:12)

Theo nguyên lý Dirichlet, tồn tại ít nhất một trong ba số |M1 ∩ M2|, |M2 ∩ M3|, |M3 ∩ M1| lớn hơn hoặc bằng 1. Giả sử |M1 ∩ M2| ≥ 1. Điều này chứng tỏ hai đa giác M1, M2 có diện tích phần chung không nhỏ hơn 1. Vậy ta luôn tìm được hai đa giác trong ba đa giác đã cho có diện tích phần chung không nhỏ hơn 1.

2.3 Nguyên lý cực hạn

Trong một số bài toán tổ hợp, chúng ta thường phải xét phần tử lớn nhất hay phần tử nhỏ nhất của một tập hợp. Nguyên lý cực hạn cho ta một khẳng định về sự tồn tại của các phần tử đó.

Định lý 2.3. (Về sự tồn tại điểm cực hạn của một tập hợp).

(i) Cho tập số thực A (cid:54)= Ø. Nếu A có hữu hạn phần tử thì trong A tồn tại

phần tử nhỏ nhất và phần tử lớn nhất.

(ii) Cho một tập các số nguyên A (cid:54)= Ø. Nếu A bị chặn trên, tức là tồn tại số thực α sao cho a ≤ α, với mọi a ∈ A, thì trong A tồn tại phần tử lớn nhất.

(iii) Cho một tập các số nguyên A (cid:54)= Ø. Nếu A bị chặn dưới, tức là tồn tại số thực α sao cho a ≥ α, với mọi a ∈ A, thì trong A tồn tại phần tử nhỏ nhất.

Để thấy được tầm quan trọng và những áp dụng thú vị của nguyên lý này, ta xét một số ví dụ sau:

|M1 ∩ M2| + |M1 ∩ M3| + |M2 ∩ M3| ≥ 3.

Ví dụ 2.16. Một quốc gia có 213 thành phố. Ban đầu, giữa các thành phố chưa có đường. Người ta muốn xây dựng một số con đường một chiều giữa các thành phố sao cho: Nếu có đường đi từ A đến B và từ B đến C thì không có đường từ A đến C. Hỏi có thể xây dựng nhiều nhất bao nhiêu đường?

Lời giải. Gọi A là thành phố có nhiều đường đi nhất (gồm cả đường đi xuất phát từ A và đường đi đến A). Ta chia các thành phố còn lại thành 3 loại: - Loại I: Có đường đi xuất phát từ A; - Loại II: Có đường đi đến A; - Loại III: Không có đường đi đến A hoặc xuất phát từ A. Đặt m = |I|, n = |II|, p = |III|. Ta có m + n + p = 212. Từ giả thiết ta suy ra giữa các thành phố loại I không có đường đi và giữa các thành phố loại II không có đường đi. Do số đường đi liên quan đến A là m + n lớn nhất nên số đường đi liên quan đến các thành phố loại 3 không vượt quá p(m + n). Như vậy, tổng số đường đi bao gồm: - Các đường đi liên quan đến A: m + n; - Các đường đi giữa các thành phố loại I và II: ≤ mn; - Các đường đi liên quan đến các thành phố loại III: ≤ p(m + n). Suy ra tổng số đường đi không vượt quá

Vậy có thể xây dựng nhiều nhất 15123 con đường. Dấu bằng xảy ra với đồ thị 3 phe, mỗi phe có 71 thành phố, thành phố phe 1 có đường đi đến thành phố phe 2, thành phố phe 2 có đường đi đến thành phố phe 3, thành phố phe 3 có đường đi đến thành phố phe 1.

Ví dụ 2.17. Một nước có 80 sân bay mà khoảng cách giữa các cặp sân bay bất kì đều khác nhau và không có ba sân bay nào thẳng hàng. Cùng một thời điểm từ mỗi sân bay có một chiếc may bay cất cánh và bay đến sân bay nào gần nhất. Chứng minh rằng trên bất kì sân bay nào cũng không thể có quá 5 máy bay đến.

Lời giải. Từ giả thiết suy ra nếu máy bay từ các sân bay B, C đến sân bay A thì BC là cạnh lớn nhất trong tam giác ABC. Khi đó, (cid:91)BAC là góc lớn nhất trong tam giác ABC. Suy ra (cid:91)BAC > 60o. Giả sử A là sân bay có nhiều máy bay đến nhất (= n) và các máy bay đó

mn+(p+1)(m+n) = mn+(p+1)m+(p+1)n ≤ = = 15123. (m + n + p + 1)2 3 2132 3

bay đến từ các sân bay B1, B2, . . . , Bn.( Tên các sân bay được đặt sao cho các tia ABi và ABi+1(i = 1, n) là kề nhau và được xếp ngược chiều kim đồng hồ, Bn+1 := B1). Do không có ba sân bay nào thẳng hàng nên ta có

n (cid:88)

(cid:92)BiABi+1 = 360o.

i=1

Suy ra, góc nhỏ nhất trong số các góc trên phải ≤ Mặt khác, theo trên, góc nhỏ nhất này phải lớn hơn 60o . Từ đó ta có:

360o n

Vậy bất kì sân bay nào cũng không thể có quá 5 máy bay đến.

Tiếp theo, ta có một vài ví dụ áp dụng Nguyên lý cực hạn trong các bất đẳng thức có tính tổ hợp, dạng chứng minh tồn tại k số từ n số thỏa mãn một điều kiện nào đó.

Ví dụ 2.18. [Moscow MO 1984]. Trên một vòng tròn người ta xếp ít nhất 4 số thực không âm có tổng bằng 1. Chứng minh rằng tổng tất cả các tích các cặp số kề nhau không lớn hơn

> 60o ⇒ n < 6 ⇒ n ≤ 5. 360o n

Lời giải. Ta cần chứng minh rằng, với mọi n(n ≥ 4), số thực không âm a1, a2, . . . , an có tổng bẳng 1, ta có bất đẳng thức

1 4

Với n chẵn (n = 2m), ta đặt a1 + a3 + · · · + a2m−1 = a. Ta có

. a1a2 + a2a3 + · · · + an−1an + ana1 ≤ 1 4

Với n lẻ và ak là số nhỏ nhất trong các số đã cho. Không mất tính tổng quát, giả sử 1 < k < n. Đặt bi = ai, i = 1, 2, . . . , k − 1; bk = ak + ak+1 và bi = ai+1, i = k + 1, . . . , n − 1. Khi đó n − 1 số b1, b2, . . . , bn−1 cũng là các số không âm và có tổng bằng 1. Áp dụng bất đẳng thức trên cho n − 1 số b1, b2, . . . , bn−1 ta được

. a1a2+a2a3+· · ·+an−1an+ana1 ≤ (a1+a3+· · ·+a2m−1)(a2+a4+· · ·+a2m) = a(1−a) ≤ 1 4

Hay

. b1b2 · · · + bk−2bk−1 + bk−1bk + bkbk+1 + bk+1bk+2 + · · · + bn−1b1 ≤ 1 4

. a1a2 + · · · + ak−2ak−1 + (ak−1ak−2)bk + ak+2ak+3 + · · · + an−1an + ana1 ≤ 1 4

Cuối cùng, ta áp dụng bất đẳng thức

Suy ra điều phải chứng minh. Dấu bằng xảy ra khi 2 trong n số bằng

, còn các số còn lại bằng 0.

ak−1ak + akak+1 + ak+1ak+2 ≤ ak−1ak + ak−1ak+1 + ak+1ak+2 ≤ (ak−1 + ak+2)bk.

Ví dụ 2.19. Tổng bình phương của 100 số thực dương lớn hơn 10000. Tổng của chúng nhỏ hơn 300. Chứng minh rằng tồn tại 3 trong số chúng có tổng lớn hơn 100.

Lời giải.. Giả sử 100 số đó là a1 ≥ a2 ≥ · · · ≥ a100 > 0. Nếu a1 ≥ 100 thì a1 + a2 + a3 > 100. Do đó, ta có thể giả sử rằng a1 < 100. Khi đó 100 − a1 > 0, 100 − a2 > 0, a1 − a3 ≥ 0, a2 − a3 ≥ 0. Vì vậy

1 2

100(a1 + a2 + a3) ≥ 100(a1 + a2 + a3) − (100 − a1)(a1 − a3)(100 − a2)(a2 − a3)

2 + a3(300 − a1 − a2)

= a2

> a2

1 + a2 1 + a2 1 + a2

2 + a3(a3 + a4 + · · · + a100) 2 + a2

3 + · · · + a2

100 > 10000.

Suy ra

≥ a2

Vậy luôn tồn tại 3 trong số 100 số đã cho có tổng lớn hơn 100.

Ngoài ra, nguyên lý cực hạn cũng được áp dụng rất hiệu quả trong các bài

toán hình học tổ hợp.

Ví dụ 2.20. Cho 2013 điểm trên mặt phẳng sao cho các tam giác bất kì có 3 đỉnh là 3 trong số 2013 điểm đã cho đều có diện tích không vượt quá 1(đvdt). Chứng minh rằng có thể đặt 2013 điểm đã cho trong một tam giác có diện tích không vượt quá 4 (đvdt).

Lời giải. Vì số tam giác có 3 đỉnh là 3 trong số 2013 điểm đã cho là hữu hạn, nên theo nguyên lý cực hạn, tồn tại một tam giác có diện tích lớn nhất. Giả sử tam giác đó là tam giác XY Z. Suy ra SXY Z ≤ 1. Xét tam giác ABC sao cho X, Y, Z tương ứng là trung điểm của AB, AC, BC. Ta có

a1 + a2 + a3 > 100.

SABC = 4SXY Z ≤ 4.

Ta chứng minh 2013 điểm đã cho nằm trong tam giác ABC. Thật vậy, giả sử tồn tại điểm M trong số 2013 điểm đã cho nằm ngoài tam giác ABC. Không mất tính tổng quát, giả sử điểm M nằm khác phía điểm A đối với BC . Khi đó

Điều này vô lý vì SXY Z lớn nhất. Suy ra không tồn tại điểm nào trong số 2013 điểm đã cho nằm ngoài tam giác ABC. Vậy ta có thể đặt 2013 điểm đã cho trong một tam giác có diện tích không vượt quá 4 (đvdt). Điều phải chứng minh.

Ví dụ 2.21. [Bài toán Sylvester]. Trong mặt phẳng cho n điểm (n ≥ 3). Biết rằng, mỗi đường thẳng đi qua hai điểm bất kì đều đi qua một điểm thứ 3 khác. Chứng minh rằng n điểm đã cho thẳng hàng.

Lời giải. Gọi S là tập hợp n điểm đã cho. Giả sử n điểm đã cho đó không thẳng hàng. Đặt

SM XY > SXY Z.

Vì n điểm không thẳng hàng nên T (cid:54)= Ø. Vì T có hữu hạn phần tử nên theo nguyên lý cực hạn, tồn tại (A, B, C) ∈ T sao cho d(A, BC) nhỏ nhất. Theo giả thiết, đường thẳng BC còn đi qua điểm thứ ba D ∈ S. Không mất tính tổng quát, giả sử C nằm giữa B và D.

T = {(A, B, C) : A, B, C ∈ S và d(A, BC) > 0}.

Kẻ AH⊥BC, HK⊥AD, CE⊥AD. Ta có

Suy ra, phần tử (A, C, D) ∈ S có d(C, AD) < d(A, BC). Điều này vô lý vì d(A, BC) nhỏ nhất. Vậy n điểm đã cho thẳng hàng.

Ví dụ 2.22. Trên mặt phẳng cho 2013 điểm, khoảng cách giữa các điểm này đôi một khác nhau. Nối một điểm nào đó trong số các điểm này với một điểm gần nhất. Hỏi cứ tiếp tục như vậy, có thể nhận được một đường gấp khúc khép kín hay không?

Lời giải. Giả sử xuất phát từ điểm A1 bất kì. Theo giả thiết, trong số tất cả các đoạn thẳng có đầu mút A1 thì tồn tại duy nhất một điểm A2 sao cho A1A2 ngắn nhất. Tiếp tục xét như vậy đối với điểm A2. Khi đó, xảy ra hai trường hợp: + Trường hợp 1: Đoạn A1A2 ngắn nhất thì đường gấp khúc dừng lại tại A2. + Trường hợp 2: Tồn tại duy nhất điểm A3 sao cho A2A3 ngắn nhất. Khi đó A2A3 < A1A2. Giả sử có đường gấp khúc A1A2 . . . An−1An thì theo lập luận trên ta có A1A2 > A2A3 > · · · > An−1An. Điểm An không thể nối với điểm Ai nào đó với i = 1, 2, . . . , n − 2, vì nếu trái lại ta có AnAi < An−1An < AiAi+1, i = 1, 2, . . . , n − 2, mâu thuẫn với yêu cầu AiAi+1 là đoạn ngắn nhất xuất phát từ Ai. Vậy đường gấp khúc không thể khép kín.

Nguyên lý cực hạn còn được gọi là nguyên lý lùi dần hay nguyên lý xuống thang. Nguyên lý lùi dần là một phương pháp do Piere de Fermat đưa ra khi giải các phương trình nghiệm nguyên. Xét phương trình f (x, y, z) = 0 trong

CE < HK < AH.

(cid:12). Lặp lại, được dãy (cid:12) (cid:12)

(cid:12) > (cid:12) (cid:12)

(cid:12)x0

(cid:12)x1

(cid:12)x2

(cid:12)x1

(cid:12)x0

Z. Giả sử (x0, y0, z0) ∈ Z3 là nghiệm của phương trình f (x, y, z) = 0. Dựa vào giả thiết để suy ra(x1, y1, z1) ∈ Z3 là nghiệm của phương trình f (x, y, z) = 0, với (cid:12) (cid:12) (cid:12) > (cid:12) (cid:12) (cid:12) > . . . . Sau một số hữu hạn bước, ta đi đến lời giải phương trình. Tương tự ta cũng có Nguyên lý tăng dần. Sau đây, ta xét một vài ví dụ để thấy được ứng dụng quan trọng này.

Ví dụ 2.23. Chứng minh rằng phương trình x4 + y4 = z2 (1) không có nghiệm nguyên x, y, z khác 0.

Lời giải. Hiển nhiên, nếu (x, y, z) là nghiệm của phương trình (1) thì (−x. − y, −z) cũng là nghiệm của phương trình (1). Do vậy, ta chỉ cần xét x, y, z > 0. Trước tiên, ta xét phương trình Pythagore:

x2 + y2 = z2.

, 1 − t2 1 + t2

1 + d4y4

Ta biết x2 + y2 − 1 có không điểm tổng quát (cid:0) 2t (cid:1) với t là một biến t2 + 1 ∈ Q, với (m, n) = 1 ta có ngay nghiệm của phương trình là mới. Khi cho t = {(2mn, n2 − m2, n2 + m2)|(m, n) = 1} hoặc {(n2 − m2, 2mn, n2 + m2)|(m, n) = 1}. Tập tất cả các bộ ba Pythagore nguyên thủy của x2 + y2 = z2 là hợp của {(2mn, n2 − m2, n2 + m2)} và {(n2 − m2, 2mn, n2 + m2)} với m, n ∈ N, (m, n) = 1 và n > m ≥ 1 khác tính chẵn lẻ. Giả sử phương trình (1) có nghiệm nguyên (x, y, z) khác 0. Ta có thể giả sử x, y, z nguyên dương và (x, y) = 1. Thật vậy. nếu (x, y) = d thì x = dx1, y = dy1 1 = z2. Do với (x1, y1) = 1, x1, y1 nguyên dương. Vì x4 + y4 = z2 nên d4x4 đó, d4|z2, suy ra d2|z. Đặt z = dz1 . Khi đó, ta có

1 + y4 x4

1 = z2 1.

0 nên {x2

0 = z2

0, y2

Ta nhận được nghiệm của phương trình x4 + y4 = z2 với x = x1, y = y1, z = z1 và (x1, y1) = 1. Ta giả sử nghiệm nguyên dương của phương trình (1) là x0, y0, z0 với (x0, y0) = 1 và z0 nhỏ nhất. Ta sẽ chỉ ra rằng tồn tại nghiệm nguyên dương khác của phương trình gồm các số x1, y1, z1 trong đó (x1, y1) = 1 và z1 < z0. Thật vậy, vì x4 0 + y4 0, z0} và (x0, y0) = 1 là một bộ ba số Pythagore nguyên thủy. Suy ra, tồn tại số nguyên dương m, n sao cho (m, n) = 1, và m, n không

m n

cùng tính chẵn lẻ, sao cho

0 = m2 − n2 x2 y2 0 = 2mn z0 = m2 + n2.

0 là số chẵn.

Trong đó, ta coi y2 Ta lại có x2 + n2 = m2 và (m, n) = 1 nên {x0, m, n} là bộ ba số Pythagore nguyên thủy. Theo kết quả trên, tồn tại các số nguyên dương r, s sao cho (r, s) = 1, r, s khác tính chẵn lẻ, và

x0 = r2 − s2

n = 2rs

Vì m lẻ và (m, n) = 1 ta có (m, 2n) = 1. Do y2 0 = (2n)m nên tồn tại số nguyên 1, 2n = t2. Vì t2 chẵn nên t chẵn, tức t = 2v, v là số dương z1, t sao cho m = z2 n nguyên dương, nên v2 = = rs. Mặt khác (r, s) = 1 nên tồn tại các số nguyên 2 1, s = y2 dương x1, y1 sao cho r = x2

1. Suy ra

1 + y4 x4

1 = z2 1

trong đó x1, y1, z1 là các số nguyên dương với (x1, y1) = 1. Hơn nữa z1 ≤ z4 1 = m2 < m2 + n2 = z0. Mâu thuẫn với giả sử z0 nhỏ nhất. Chứng tỏ, điều giả sử ban đầu là sai. Vậy phương trình x4 + y4 = z2 không có nghiệm nguyên x, y, z khác 0.

Hệ quả 2.1. Phương trình x4 + y4 = z4 không có nghiệm nguyên x, y, z đều khác 0.

Ví dụ 2.24. Giải phương trình x3 − 2y3 − 4z3 = 0 (2) trong Z.

1 − 4z3

1 − 2y3

Lời giải. Ta thấy, (0, 0, 0) là một nghiệm nguyên của phương trình (2). Xét x (cid:54)= 0 hoặc y (cid:54)= 0 hoặc z (cid:54)= 0, chẳng hạn x (cid:54)= 0. Giả sử (x, y, z) là nghiệm nguyên của phương trình đã cho. Đặt d = (x, y, z) và x = dx1, y = dy1, z = dz1. Khi đó (x1; y1, z1) = 1. Từ x3 − 2y3 − 4z3 = 0 suy ra x3 1 = 0. Vậy x1 = 2x2 với x2 ∈ Z và ta lại có y1 = 2y2 với y2 ∈ Z. Từ đó suy ra z1 = 2z2 với z2 ∈ Z. Như vậy (x1, y1, z1) > 1 (mâu thuẫn). Vậy phương trình đã cho có đúng một nghiệm (0, 0, 0).

m = r2 + s2,

Ví dụ 2.25. Tìm tất cả các giá trị của k sao cho phương trình (x + y + z)2 = kxyz có nghiệm nguyên dương.

lời giải. Giả sử k là một giá trị cần tìm. Gọi x0, y0, z0 là nghiệm nguyên dương của phương trình

với x0 + y0 + z0 nhỏ nhất. Không mất tính tổng quát, giả sử x0 ≥ y0 ≥ z0. Viết lại (3) dưới dạng

(x + y + z)2 = kxyz (3)

Suy ra x0 là nghiệm của phương trình bậc hai

x2 − (kyz − 2y − 2z)x + (y + z)2 = 0.

cũng là nghiệm của

Theo định lí Viet x1 = ky0z0 − 2y0 − 2z0 − x0 =

x2 − (ky0z0 − 2y0 − 2z0)x + (y0 + z0)2 = 0. (4)

phương trình (4). Từ đó, x1, y0, z0 cũng là nghiệm của (3). Vì x0 + y0 + z0 nhỏ nhất nên ta có x1 ≥ x0. Từ đây ta có

(y0 + z0)2 x0

≥ x0. ky0z0 − 2y0 − 2z0 − x0 ≥ x0 và (y0 + z0)2 x0

Từ bất đẳng thức thứ hai ta suy ra y0 + z0 ≥ x0. Áp dụng vào bất đẳng thức thứ nhất ta được ky0z0 ≥ 4x0 hay

0 + z2

0 + 2x0y0 + 2y0z0 + 2z0x0 =

≤ x0 y0z0

k 4 Cuối cùng, chia cả hai vế của đẳng thức x2 0 + y2 kx0y0z0 cho x0y0z0 ta được

Từ đó suy ra

+ + + + + = k. x0 y0z0 y0 x0z0 z0 x0y0 2 z0 2 x0 2 y0

. + 1 + 1 + 2 + 2 + 2 ≥ k hay k ≤ 32 3 k 4

Suy ra k ≤ 10. Ta có: Nếu x0 = 1 thì y0 = z0 = 1, suy ra k = 9. Nếu k (cid:54)= 9 thì x0 ≥ 2 và đánh . Suy ra k ≤ 8. Vậy giá ở trên sẽ thành

+ 1 + + 2 + 1 + 2 ≥ k hay k ≤ 1 2 26 3 k 4

k = 10 loại Với k = 1 phương trình có nghiệm, chẳng hạn (9, 9, 9); Với k = 2 phương trình có nghiệm, chẳng hạn (4, 4, 8); Với k = 3 phương trình có nghiệm, chẳng hạn (3, 3, 3); Với k = 4 phương trình có nghiệm, chẳng hạn (2, 2, 4); Với k = 5 phương trình có nghiệm, chẳng hạn (1, 4, 5);

Với k = 6 phương trình có nghiệm, chẳng hạn (1, 2, 3); Với k = 7 phương trình không có nghiệm nguyên dương; Với k = 8 phương trình có nghiệm, chẳng hạn (1, 1, 2); Với k = 9 phương trình có nghiệm, chẳng hạn (1, 1, 1); Vậy k = 1, 2, 3, 4, 5, 6, 8, 9 là các giá trị cần tìm.

2.4 Nguyên lý bất biến

Bất biến là một khái niệm rất quan trọng của toán học. Nó có mặt hầu hết trong các lĩnh vực của toán học như Đại số, Hình học, Tôpô, Lý thuyết số, xác suất, Phương trình vi phân, . . . . Nói đơn giản thì bất biến là đại lượng hay tính chất không thay đổi qua các phép biến đổi. Chẳng hạn, khi thực hiện phép tịnh tiến thì khoảng cách giữa hai điểm sẽ không thay đổi. Với phép vị tự thì khoảng cách có thể thay đổi nhưng tỷ lệ giữa hai đoạn thẳng lại không thay đổi. Trong phần này, chúng ta sẽ tìm hiểu một số bài toán có sử dụng nguyên lý bất biến. Có hai mẫu bài toán tổng quát thường được giải bằng bất biến. Đó là:

Bài toán 2.2. Có một tập hợp các trạng thái Ω và tập hợp các phép biến đổi T từ Ω vào Ω. Có hai trạng thái α và β thuộc Ω. Hỏi có thể dùng hữu hạn các phép biến đổi thuộc T để đưa trạng thái α về trạng thái β được không?.

Bài toán 2.3. Có một tập hợp các trạng thái Ω và tập hợp các phép biến đổi T từ Ω vào Ω. Cần chứng minh rằng, bắt đầu từ một trạng thái α bất kì, sau một số hữu hạn các phép biến đổi từ T , ta sẽ đi đến trạng thái kết thúc (trong nhiều trường hợp, đó là trạng thái ổn định, tức là sẽ không tiếp tục thay đổi khi tác động các phép biến đổi từ T ).

Định nghĩa 2.2. Cho Ω là tập hợp các trạng thái. T là tập hợp các phép biến đổi từ Ω vào Ω. Hàm số f : Ω −→ R được gọi là bất biến trên tập hợp các trạng thái Ω đối với tập các phép biến đổi T nếu

(2.10)

Trong nhiều bài toán, bất biến được sử dụng là tính chẵn lẻ (phần dư khi chia cho 2), phần dư khi chia cho 3, hay chia cho một số nguyên dương nào đó của một đại lượng trong quá trình biến đổi. Cụ thể, ta xét ví dụ sau sau đây để thấy được ứng dụng của nguyên lý bất biến.

f (t(ω)) = f (ω), ∀ω ∈ Ω, t ∈ T.

Ví dụ 2.26. Trên bảng đen ta viết 2013 dấu cộng (+) và 2014 dấu trừ (−). Cho phép xóa 2 dấu tùy ý và viết thay vào đó là một dấu cộng nếu 2 dấu xóa là như nhau và dấu trừ trong trường hợp ngược lại. Lặp lại phép tính đó 4026 lần thì trên bảng còn lại một dấu. Hỏi trên bảng còn lại dấu gì?

Lời giải. Cách 1. Giả sử, thay cho dấu cộng ta viết số 1, thay cho dấu trừ ta viết số −1. Khi đó phép toán đã cho tương đương với việc thay hai số tùy ý bởi tích của chúng. Phép toán này không làm thay đổi tích của tất cả các số đã cho. Như vậy, tích của tất cả các chữ số đã cho là một bất biến trong quá trình lặp lại phép toán. Tại trạng thái xuất phát, tích của các số này bằng 1 và vì nó là một bất biến nên ở trạng thái cuối cùng, tích đó cũng bằng 1. Sau 4026 lần lặp, ta chỉ còn một số trên bảng, vậy đó là số 1. Điều này có nghĩa là dấu còn lại là dấu cộng (+). Cách 2. Ta có thể thay mỗi dấu cộng bằng số 0, mỗi dấu trừ bằng số 1. Khi thực hiện phép toán, tổng của hai số bị xóa có cùng tính chẵn lẻ với số thay thế hai số đó. Như vậy, tính chẵn lẻ của tổng tất cả các số đã cho là một đại lượng bất biến của bài toán. Tại trạng thái xuất phát, tổng các số đã cho là 2014, là số chẵn. Do vậy, tổng của các số cuối cùng phải là số chẵn. Suy ra, sau 4026 bước lặp, số cuối cùng còn lại là số 0, tức là dấu cuối cùng là dấu cộng (+). Cách 3. Ta thấy, sau mỗi phép toán, số các dấu trừ hoặc không đổi hoặc giảm đi 2 đơn vị. Như vậy tính chẵn lẻ của số các dấu trừ cũng là một bất biến. Tại trạng thái xuất phát, số các dấu trừ (2014 dấu trừ) là một số chẵn, nên ở trạng thái kết thúc, số các dấu trừ cũng phải là một số chẵn. Sau 4026 bước lặp, chỉ còn lại một số, thì số các dấu trừ phải bằng 0. Tức là còn lại một dấu cộng (+).

Nhận xét 2.3. Trong ba cách giải trên, ta đã sử dụng tính bất biến của tích, tổng hoặc tính chẵn lẻ của các số. Như vậy, khi gặp những lớp bài toán mà thao tác lặp đi lặp lại, ta phải biến đổi và tìm ra những đại lượng bất biến của thao tác ta thực hiện.

Ví dụ 2.27. Trên bảng có các số

. Mỗi một lần thực hiện,

cho phép xóa đi hai số a, b bất kì trên bảng và thay bằng a + b − 2ab. Hỏi sau 95 lần thực hiện phép xóa, số còn lại trên bảng là số nào?

Lời giải. Giả sử các số đã cho trên bảng là a1, a2, . . . , ak. ta cho tương ứng

, . . . , , , 1 96 2 96 3 96 96 96

bảng này với

Khi đó, sau mỗi lần biến đổi, tích trên bị mất đi hai thừa số (2a − 1)(2b − 1) và được thêm thừa số

(2a1 − 1)(2a2 − 1) . . . (2ak − 1).

2(a + b − 2ab) − 1 = −(2a − 1)(2b − 1).

Do đó, tích trên vẫn không đổi (chỉ đổi dấu).Vì trên bảng có chứa số

= 48 96

. Vậy số cuối cùng còn lại trên bảng là

Ví dụ 2.28. Có 2000 quả cầu trắng trong một chiếc hộp. Bên ngoài chiếc hộp cũng có các quả cầu trắng, xanh và đỏ với số lượng không hạn chế. Trong mỗi lần thay đổi chúng ta có thể thay đổi hai quả cầu trong hộp bởi 1 hoặc 2 quả cầu theo cách sau: Thay 2 quả trắng bởi một quả xanh, 2 quả đỏ bởi một quả xanh, 2 quả xanh bởi một quả trắng và một quả đỏ, một quả trắng và một quả xanh bởi một quả đỏ, hoặc một quả xanh và một quả đỏ bởi một quả trắng. a) Sau một số hữu hạn lần thực hiện như trên còn lại 3 quả cầu trong hộp. Chứng minh rằng có ít nhất một quả xanh trong 3 quả còn lại. b) Liệu có thể xảy ra sau một số hữu hạn lần thực hiện như trên trong hộp còn đúng một quả cầu ?.

Lời giải. Ta gắn giá trị i cho mỗi quả cầu trắng, −i cho mỗi quả cầu đỏ và −1 cho mỗi quả cầu xanh. Ta có thể kiểm tra lại rằng các phép thay thế trên không làm thay đổi tích các giá trị của các quả cầu trong hộp. Tích các giá trị của các quả cầu ban đầu là i2000 = 1. Giả sử, trong hộp còn lại ba quả cầu mà không có quả nào xanh thì tích các giá trị của chúng sẽ là ±i, (mâu thuẫn). Do đó, nếu trong hộp còn lại ba quả cầu thì ít nhất một quả màu xanh. Hơn nữa, vì không có quả nào có giá trị 1 nên trong hộp phải chứa ít nhất hai quả. Do đó, không thể xảy ra trường hợp trong hộp chỉ còn một quả cầu.

Ví dụ 2.29. Cho m và n là các số nguyên dương lớn hơn 3 và bảng ô vuông có kích thước m × n. Cho phép đặt bi vào các ô vuông con của bảng theo cách sau: Mỗi lần đặt vào 4 ô vuông con (mỗi ô một viên bi) mà 4 ô đó tạo thành một trong các hình dưới đây

. 1 2 nên tích ban đầu bằng 0. Suy ra, số cuối cùng s cũng phải cho tích bằng 0. Tức là 2s − 1 = 0 hay s = 1 2 1 2

Hỏi sau một số lần có thể nhận được bảng mà số bi trong các ô bằng nhau hay không nếu m = 2005, n = 2006?

Lời giải. Tô màu các ô vuông con của bảng thuộc hàng lẻ. Dễ thấy mỗi lần đặt bi có 2 viên được đặt vào ô được tô màu và 2 viên được đặt vào ô không được tô màu. Do đó, nếu gọi S(n) là số bi trong các ô được tô màu và T (n) là số bi trong các ô không được tô màu sau lần đặt bi thứ n, thì S(n) − T (n) là một bất biến. Ta có S(n) − T (n) = S(0) − T (0) = 0, ∀n ≥ 0. Do đó, nếu nhận được bảng mà số bi trong các ô bằng nhau thì số ô được tô màu và số ô không được tô màu phải bằng nhau. Điều này không thể xảy ra vì m = 2005 là một số lẻ.

trong số các khoảng cách đó chia hết cho 3.

Ví dụ 2.30. Cho n điểm trên mặt phẳng (n ≥ 4) sao cho khoảng cách giữa hai điểm bất kì trong n điểm đó là một số nguyên. Chứng minh rằng ít nhất 1 6

Lời giải. Ta xét các đồng dư theo modun 3. Trước hết ta chứng minh với n = 4, thì ít nhất có hai điểm rời nhau mà khoảng cách giữa chúng chia hết cho 3. Kí hiệu 4 điểm đó là A, B, C, D. Giả sử các khoảng cách AB, BC, CD, DA, AC, BD không chia hết cho 3. Khi đó, không mất tính tổng quát, ta giả sử (cid:91)BAD > (cid:91)BAC > (cid:91)CAD. Gọi x = (cid:91)BAC, y = (cid:91)CAD và α = 2.AB.AC. cos x, β = 2.AD.AC. cos y, γ = 2.AB.AD. cos (x + y). Áp dụng định lý hàm số Cosin trong tam giác ABC, ACD, ABD ta được :

BC2 = AB2 + AC2 − α;

CD2 = AC2 + AD2 − β;

BD2 = AB2 + AD2 − γ.

Vì bình phương mỗi khoảng cách là một số nguyên nên α, β và γ cũng là các số nguyên. Do đó:

2.AC2.γ = 4.AC2.AB.AD. cos (x + y)

= 4.AC2.AB.AD.(cos x cos y − sin x sin y)

cũng là số nguyên. Vì vậy, 4AC2.AB.AD. sin x. sin y là một số nguyên chẵn và sin x sin y = (cid:112)(1 − cos2 x)(1 − cos2 y) là một số hữu tỷ, khi viết dưới dạng tối giản tử số là số không chia hết cho 3.

và cos y =

. Vì sin x sin y =

= αβ − 4.AC2.AB.AD. sin x sin y

là số hữu tỷ nên tử số ở vế phải cũng là một số nguyên.

Đặt p = 2AB.AC và q = 2AD.AC. Do đó cos x = (cid:112)(p2 − α2)(q2 − β2) pq

n−2 tập con.

α p β q

Vậy có ít nhất

các khoảng chia hết cho 3.

Vì p2 ≡ 1(mod 3) và α2 ≡ 1(mod 3) nên tử số chia hết cho 3. Do đó, khi viết dưới dạng tối giản thì tử số của nó chia hết cho 3, điều này mâu thuẫn. Chứng tỏ, điều giả sử ban đầu là sai. Vậy với n = 4, có ít nhất một khoảng cách chia hết cho 3. Xét với n ≥ 4. Từ một tập có n điểm đã cho, có C4 n các tập con chứa 4 điểm có ít nhất 2 điểm trong mỗi tập con đó có khoảng cách chia hết cho 3 và mỗi khoảng cách đó được đếm ít nhất C2 C4 n C2

n−2

Cuối cùng, ta xét một ứng dụng của bất biến trong hình học.

Ví dụ 2.31. Chứng minh rằng trong một đa diện lồi, luôn tồn tại ít nhất một đỉnh là đỉnh của một góc tam diện hoặc ít nhất là một mặt là tam giác. Ta nhận thấy ví dụ này hơi xa lạ so với các ví dụ trước vì không thấy phép biến đổi nào. Thực ra bất biến không chỉ xuất hiện ở những chỗ có các phép biến đổi mà nó còn xuất hiện khi ta xét một lớp các đối tượng thỏa mãn một số tính chất nào đó. Ví dụ, với các điểm (x, y) nằm trên đường tròn đơn vị thì x2 + y2 là một bất biến. Còn với một đa diện lồi bất kì ta có công thức Euler nổi tiếng

= C2 n 6

trong đó V là số đỉnh, F là số mặt và E là số cạnh của một đa diện lồi bất kì. Ta sẽ dùng công thức này để giải bài toán trên.

V − E + F = 2,

Lời giải. Trước tiên, ta đi chứng minh công thức Euler nêu trên. Xóa bỏ đi một mặt của đa diện, bằng cách kéo các cạnh của mặt bị bỏ đi, ta biến phần còn lại thành một mạng lưới phẳng các điểm và các đường. Sau phép biến đổi này, các mặt nói chung không còn là đều nữa, thậm chí có thể không còn là đa giác. Nhưng số đỉnh, số cạnh, số mặt vẫn giống với đa diện ban đầu (mặt bị xóa bỏ tương ứng với phần ngoài của mạng lưới). Nếu như một mặt nào đó có nhiều hơn ba cạnh, ta vẽ đường chéo, tức là đường cong nằm trên mặt và nối hai đỉnh chưa được nối. Điều này sẽ làm tăng số cạnh lên 1, số mặt tăng lên 1, còn số đỉnh thì không thay đổi, có nghĩa là giá trị V − E + F không đổi. Bằng cách thêm cạnh theo quy tắc này, ta sẽ đi đến tình huống khi tất cả các mặt đều là tam giác. Tiếp theo, ta áp dụng liên tục hai phép biến đổi sau: i) Xóa đi tam giác chỉ có một cạnh giáp với phần ngoài. Điều này sẽ làm giảm số cạnh và số mặt đi một đơn vị nhưng không làm thay đổi số đỉnh, vì thế phép biến đổi này bảo toàn V − E + F . ii) Xóa đi tam giác có hai cạnh tiếp giáp với phần ngoài. Phép xóa này sẽ xóa đi một đỉnh, hai cạnh và một mặt. Vì thế vẫn bảo toàn V − E + F . Lặp lại hai bước này nhiều lần cho đến khi chỉ còn một tam giác. Lúc này, ta có V = 3, E = 3, F = 2 (tính cả phần ngoài). Suy ra V − E + F = 2. Con số này bằng với số V − E + F ban đầu, vì các phép biến đổi mà ta thực hiện bào toàn đại lượng này. Như vậy, ngay từ bước đầu của quá trình biến đổi, ta phải có V − E + F = 2. Công thức Euler được chứng minh. Tức là, trong một đa điện lồi bất kì ta luôn có

Tiếp theo để giải bài toán trên, ta giả sử ngược lại, tồn tại một đa diện mà không có đỉnh nào là đỉnh của một góc tam diện và không có mặt nào là tam giác. Khi đó, do một mặt có ít nhất 4 cạnh và một cạnh chỉ có thể là cạnh

. Với lập luận tương tư, ta có V ≤

. Vì vậy

V − E + F = 2.

E 2 E 2

của hai mặt nên ta có F ≤ E 2

sử là sai. Tức là trong một đa diện lồi, luôn tồn tại ít nhất một đỉnh là đỉnh của một góc tam diện hoặc ít nhất là một mặt là tam giác.

V + F − E ≤ + − E = 0, mâu thuẫn với công thức Euler. Chứng tỏ, giả E 2

Ví dụ 2.32. [VMO 2011] Dãy (an) xác định bởi

a0 = 1, a1 = −1

an+2 = 6an+1 + 5an

  

...2011.

Chứng minh a2012 − 2010

Lời giải. Giả sử dãy (bn) được xác định như sau b0 = a0 = 1, b1 = a1 = −1 và bn+2 = 6bn+1 + 2016bn với mọi số nguyên n ≥ 0. Hiển nhiên an ≡ bn(mod2011).

n ≥ 0.

Đặt cn+1 = bn . Khi đó

bn+1 = 6bn + 2016cn

  

cn+1 = bn, n ≥ 1

Như vậy bn+1 + tcn+1 = 6bn + 2016cn + tbn = (6 + t)bn + 2016cn. Chọn t sao cho 2016 = t(t + 6). Giải ra t1 = 42, t2 = −48. Như vậy ta đã tạo ra được một bất biến 6 + t để bn+1 + tcn+1 = (6 + t)(bn + tcn). Từ bn+1 + tcn+1 = (6 + t)(bn + tcn) = · · · = (6 + t)n(b1 + tc1) ta suy ra

 

b1 = −1, c1 = 1



bn+1 − 48cn+1 = (−42)n(−1 − 48) = −49(−42)n

Suy ra 90cn+1 = 41.48n + 49.(−42)n. Đặc biệt 90b2012 = 41.482012 + 49.(−42)2012. Vì 482010 ≡ 1 ≡ 422010 (theo định lý Fermat) và bn ≡ an(mod2011) nên 90a2012 = 41.482 + 49.(42)2 ≡ 41.293 − 49.247(mod2011). Vậy 90a2012 = 12013 − 12103 = ...2011. −90(mod2011). Ta suy ra a2012 − 2010

Ví dụ 2.33. Dãy (an) xác định bởi a0 = 2, a1 = 89 và an+2 = 89an+1 − 9an với n + 81.9n...1951 và mọi số nguyên n ≥ 0. Chứng minh rằng a2

n+1 − 89anan+1 + 9a2

...1951.

bn+1 + 42cn+1 = (48)n(−1 + 42) = 41.48n

Đặt cn+1 = bn . Khi đó

a1952 − 99

Lời giải. Dãy (bn) được xác định như sau b0 = a0 = 2, b1 = a1 = 89 và bn+2 = 89bn+1 − 1960bn với mọi số nguyên n ≥ 0.   bn+1 = 89bn − 1960cn 

cn+1 = bn, n ≥ 1

Như vậy bn+1 + tcn+1 = 89bn − 1960cn + tbn = (89 + t)bn − 1960cn. Chọn t sao cho −1960 = t(t + 89). Giải ra t1 = −49, t2 = −40. Như vậy ta đã tạo ra được

b1 = 89, c1 = 2

một bất biến 89 + t để bn+1 + tcn+1 = (89 + t)(bn + tcn). Từ bn+1 + tcn+1 = (89 + t)(bn + tcn) = · · · = (89 + t)n(b1 + tc1) ta suy ra

 



bn+1 − 49cn+1 = 40n(89 − 49.2) = −9.40n

n+1 − 89bn+1cn+1 + 1960c2

n+1 = −81.1960n. Ta dễ dàng có được an ≡ n + 81.9n = 0(mod1951).

n+1 − 89an+1an + 9a2

...1951.

Suy ra b2 bn(mod1951) nên ta có a2 Ta lại có 9cn+1 = 9(40n + 49n). Suy ra bn = 40n + 49n. Vì 401950 ≡ 1 ≡ 491950 (theo định lý Fermat) nên b1952 = 401952 + 491952 = 402 + 492 ≡ 99(mod1951). Vậy a1952 − 99

Ví dụ 2.34. Giả sử hai dãy số nguyên (an) và (bn) xác định như sau:



bn+1 − 40cn+1 = 49n(89 − 40.2) = 9.49n

a0 = 3, a1 = 8, a2 = 58

an+2 = 8an+1 − 3an + 3an−1, n ≥ 2;

 

b0 = 3, b1 = 5, b2 = 45

Khi đó ta có các kết quả sau

 

bn+2 = 5bn+1 + 10bn + 7bn−1, n ≥ 2.



b1 + Cn an = C0

n a0.

nbn−1 + · · · + Cn−1 n b0 nan−1 + · · · + (−1)n−1Cn−1

nbn + C1 nan − C1

3 = a0, x1 + x2 + x3 = a1, x2

3 = a2. Tổng

2 + x2

1 + x2

3 = bn, n ≥ 0, trong đó y1, y2, y3 là ba nghiệm của phương

2 + x0 1 + x0 3 = an, n ≥ 0. 2 + yn

2 + xn 1 + yn

3 và bn = yn

2 + xn

1 + xn

1 + yn

2 + yn

Lời giải.. Đây là bài toán về dãy số nguyên nhưng lại xét bài toán trên C. Xét phương trình f (x) = x3 − 8x2 + 3x − 3 = 0. Gọi 3 nghiệm của phương trình trong C là x1, x2, x3. Dễ dàng kiểm tra x0 quát xn 1 + xn Tương tự yn trình g(y) = y3 − 5y2 − 10y − 7 = 0. Bất biến ở đây là an = xn 3 . Kiểm tra trực tiếp được hai bất biến mới là: f (y + 1) = g(y) và g(x − 1) = f (x). Vậy ta nhận được các hệ thức sau:

a1 + (−1)nCn bn = C0

1 + xn

2 + xn

3 = (y1 + 1)n + (y2 + 1)n + (y3 + 1)n

an = xn

1 + yn

2 + yn

3 = (x1 − 1)n + (x2 − 1)n + (x3 − 1)n, n ≥ 0.

bn = yn

Do vậy

 



an = C0 b1 + Cn

n a0.

nbn−1 + · · · + Cn−1 n b0 nan−1 + · · · + (−1)n−1Cn−1

nbn + C1 nan − C1

a1 + (−1)nCn bn = C0

Chương 3

Một vài đồng nhất thức trong tổ

hợp

Trong các kì thi đại học, cao đẳng ta thường thấy xuất hiện các bài toán tổ hợp có sử dụng các đồng nhất thức được xây dựng qua đạo hàm và tích phân. Trong mục này, tác giả xin trình bày một số cách khác xây dựng các đồng nhất thức trong tổ hợp.

3.1 Xây dựng đồng nhất thức qua hệ phương trình

Để có những đồng nhất thức mới trong tổ hợp, ta xét những hệ phương trình tuyến tính nhiều ẩn và giải những hệ đó. Xây dựng các đồng nhất thức liên hệ giữa các nghiệm của hệ phương trình tuyến tính để từ đó có đồng nhất thức mới trong tổ hợp.

Ví dụ 3.1. Với số nguyên dương n và số thực x /∈ {−2n, −n, −2n + 2, −n + 1, . . . , −2, −1, 0} ta luôn có các đồng nhất thức dưới đây:

(i)

n (cid:80) k=0

n (cid:81) k=0

n! . = Ck n (−1)k x + k (x + k)

(ii)

n (cid:80) k=0

n (cid:81) k=0

n!2n = . Ck n (−1)k x + 2k (x + 2k)

Lời giải.. Từ việc tách phân thức

n (cid:80) k=0

n (cid:81) k=0

n!2n n! , = = xk x + k (x + k) (x + 2k)

ta suy ra các kết quả (i) và (ii).

n (cid:80) k=0

Ví dụ 3.2. Phân tích f (x) =

trên R thành tổng

xk x + 2k

1 x(x2 + 1)(x2 + 22) . . . (x2 + n2) các phân thức đơn giản. Từ đó hãy tính các tổng dưới đây:

(i)

n (cid:80) k=0

. (−1)kCn−k 2n 1 + k2

(ii)

n (cid:80) k=0

. (−1)kCn−k 2n n2 + k2

Lời giải.. Ta có f (x) =

n (cid:80) k=1

Từ đây suy ra f (x) =

Cho x = 1 ta nhận được

n (cid:81) k=1

Nhân hai vế với (2n)! được

+ 2 . akx + bk x2 + k2 . n (cid:80) k=1 1 − = (−1)kx (n + k)!(n − k)!(x2 + k2) (−1)k (n + k)!(n − k)!(1 + k2) 1 2(n!)2 . a x 1 (n!)2x n (cid:80) k=1 (1 + k2) 2

n (cid:88)

k=0

n (cid:81) k=0

(2n)! + = (−1)k(2n)! (n + k)!(n − k)!(1 + k2) (2n)! 2(n!)2 (1 + k2) 2

và như vậy ta có

n (cid:80) k=0

(−1)kCn−k (2n)! + 1 + k2 = (2n)! 2(n!)2 . Ta đã có (i). (1 + k2) 2

(ii) Với x = n thay vào biểu diễn trên

n (cid:81) k=0 n (cid:80) k=1

n (cid:81) k=1

1 = − (−1)kn (n + k)!(n − k)!(n2 + k2) 2n (n2 + k2)

n (cid:88)

2n(n!)2 . Nhân hai vế của hệ thức trên với (2n)! ta nhận được

k=0

Ví dụ 3.3. Giả sử các số α1, α2, . . . , αn khác nhau đôi một và αi + j (cid:54)= 0 với

+ (−1)kCn−k n2 + k2 = (2n)! 2n2(n!)2 . 2n2 (n2 + k2) (2n)! n (cid:81) k=0

mọi i, j = 1, 2, . . . , n. Giải hệ phương trình sau đây:



+ + · · · + = 1

+ + · · · + = 1 x2 2 + α1 x2 2 + α2 xn n + α1 xn n + α2

x1 1 + α1 x1 1 + α2 ...

 

+ + · · · + = 1. x1 1 + αn x2 2 + αn xn n + αn

Lời giải:. Xét f (x) =

với đa thức

n (cid:81) i=1

p(x) + · · · + − 1 = + x1 1 + x x2 2 + x xn n + x (i + x)

p(x) bậc n. Vì f (αi) = 0 nên p(αi) = 0, i = 1, . . . , n và như vậy

f (x) = − . (x − α1)(x − α2) . . . (x − αn) (x + 1)(x + 2) . . . (x + n)

Từ

ta có

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

x1(x + 2)(x + 3) . . . (x + n) + x2(x + 1)(x + 3) . . . (x + n)

+ x3(x + 1)(x + 2)(x + 4) . . . (x + n) + x4(x + 1) . . . (x + n)

+ · · ·

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

với x = −1

= −(x − α1)(x − α2) . . . (x − αn).  (−1)n−1 (1 + αi)

x1 =

với x = −2

(−1)n−2 (2 + αi)

Ta nhận được các nghiệm

x2 =

với x = −3

(−1)n−3 (3 + αi)

n (cid:81) i=1 (n − 1)! n (cid:81) i=1 1!(n − 2)! n (cid:81) i=1 2!(n − 3)!

x3 =

...

với x = −n

(−1)n−n (n + αi)

 

n (cid:81) i=1 (n − 1)!

và hệ đã được giải xong.

Ví dụ 3.4. Giả sử ϕ(x) =

xn =

n (cid:81) i=1

(x + αi). Khi đó ta có các đồng nhất thức:

(i)

nϕ(i) = (−1)nn!.

n (cid:80) i=0

(−1)iCi

(ii)

nin = (−1)nn!.

n (cid:80) i=0

(−1)iCi

(iii)

nCi

n+i = (−1)n.

n (cid:80) i=0

Lời giải.. (i) Từ cách giải ở trên ta suy ra đồng nhất thức sau đây:

n (cid:88)

(−1)iCi

i=1

− 1 = − . (−1)n−iϕ(i) (x + i)(i − 1)!(n − i)! (x − α1)(x − α2) . . . (x − αn) (x + 1)(x + 2) . . . (x + n)

Với x = 0 có

hay ta nhận được công thức

n (cid:80) i=1

− 1 = (−1)n−iϕ(i) i!(n − i)! (−1)n+1ϕ(0) n!

nϕ(i) = (−1)nn!. (Chú ý rằng công thức này cũng đúng cho cả trường

n (cid:80) i=0 hợp các αi có thể bằng nhau).

(−1)iCi

(ii) Công thức

nϕ(i) = (−1)nn! đúng cho mọi αi nên khi lấy α1 =

n (cid:80) i=0

(−1)iCi

n (cid:80) i=0

(−1)iCi · · · = αn = 0 ta có

(iii) Khi lấy αi = i với mọi i ta có

nCi

n+i = (−1)n.

nin = (−1)nn!. n (cid:80) i=0

Ví dụ 3.5. Giải hệ phương trình 2n ẩn thực xk, yk dưới đây:



(−1)iCi

n (cid:80) k=1

1 s

sxk + yk  s2 + k2 = s = ±1, . . . , ±n;  xk, yk ∈ R, k = 1, . . . , n.

(s2 + k2)

Từ đó hãy tính tổng sau:

n (cid:81) s=1 (s2 − k2)(1 + k2)

n (cid:80) k=1

k2 (cid:81) s(cid:54)=k

Lời giải.. Xét f (x) = −

n (cid:80) k=1

n (cid:81) k=1

với đa thức p(x) có bậc (cid:54) 2n. Do f (s) = 0 nên p(s) = 0 khi s = ±1, . . . , ±n, và như vậy dễ dàng có

p(x) + 1 x xkx + yk x2 + k2 = (x2 + k2) x

a(x2 − 12)(x2 − 22) . . . (x2 − n2) f (x) = .

n (cid:81) k=1

(x2 + k2) x

Từ −

ta suy ra hệ thức

n (cid:80) k=1

n (cid:81) k=1

a(x2 − 12)(x2 − 22) . . . (x2 − n2) + 1 x xkx + yk x2 + k2 = x (x2 + k2)



− (x2 + 12) . . . (x2 + n2) + x(x1x + y1)(x2 + 22)(x2 + 32) . . . (x2 + n2) + x(x2x + y2)(x2 + 12)(x2 + 32) . . . (x2 + n2) + · · · + x(xnx + yn)(x2 + 12)(x2 + 22) . . . (x2 + (n − 1)2) = a(x2 − 12)(x2 − 22) . . . (x2 − n2).

với x = i

a(−1)n (12 + k2) a = −(−1)n với x = 0 n (cid:81) k=1 −x1 + iy1 = (k2 − 1)

n (cid:81) k=2 a(−1)n

n (cid:81) k=1

với x = 2i

(22 + k2)

Ta nhận được các nghiệm

n (cid:81) k=1,k(cid:54)=2

−22x2 + 2iy2 = (k2 − 22)

...

n (cid:81) k=1

với x = ni.

a(−1)n (n2 + k2)

−n2xn + niyn =

 

n−1 (cid:81) k=1

(k2 − n2)

với

Như vậy hệ được giải xong với y1 = · · · = yn = 0 và xr =

(r2 + k2)

n (cid:81) k=1 n (cid:81) k=1,k(cid:54)=r

r2 (k2 − r2)

nên

Vì −

n (cid:80) k=1

n (cid:81) k=1

a(x2 − 12)(x2 − 22) . . . (x2 − n2) + xk 1 + k2 = 1 hay xkx x2 + k2 = r = 1, . . . , n. n 1 (cid:80) x k=1 (x2 + k2) x

n (cid:81) s=1

(s2 + k2)

n (cid:80) k=1

= 1 với x = 1.

n (cid:81) s(cid:54)=k

k2 (s2 − k2)(1 + k2)

(−1)n−k (s2 + k2)Cn−k

Hệ quả 3.1. Ta luôn có 2

n (cid:81) s=1 1 + k2

n (cid:80) k=1

= (2n)!.

n (cid:81) s=1

Chứng minh.. Từ

(s2 + k2)

n (cid:80) k=1

= 1, theo chứng minh trên, và

n (cid:81) s(cid:54)=k

k2 (s2 − k2)(1 + k2)

suy ra

n (cid:81) s(cid:54)=k

(s2 − k2) = (s − k) (s + k) = (−1)k−1 (n − k)!(n + k)! 2k2

n (cid:81) s=1

n (cid:88)

2 (s2 + k2)

k=1

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

n (cid:81) s=1

Nhân hai vế với (2n)! có 2

n (cid:80) k=1

Ví dụ 3.6. Giả sử ϕ(x) =

(−1)k−1 (s2 + k2)Cn−k 2n = (2n)!. 1 + k2

n (cid:81) i=1

nϕ(i)

(x + αi). Khi đó ta có các đồng nhất thức:

(i)

n (cid:80) i=1

= + (−1)nϕ(0). (−1)iCi 2i − 1 4n! c

(ii)

nin =

n (cid:80) i=1

Lời giải.. Xuất phát từ phương trình

Ci . (−1)i−1 2i − 1 2n(n!)2 (2n)!

ta suy ra (i) khi thay x1, . . . , xn và x = 0; còn (ii) được suy ra từ (i).

Ví dụ 3.7. Với số tự nhiên dương n luôn có các đồng nhất thức

+ + · · · + − = x1 1 + x x2 2 + x xn n + x 4 2x + 1 c(x − α1)(x − α2) . . . (x − αn) (2x + 1)(x + 1)(x + 2) . . . (x + n)

(i)

n (cid:80) k=−n

n (cid:81) k=1

(2n)! = . (−1)kCn+k 2n k2 + 1 (k2 + 1)

(ii)

n (cid:80) k=−n

= 0. (−1)kkCn+k k2 + 1

(iii)

n (cid:80) k=−n

n (cid:81) k=1

(2n)! . (−1)kCn+k k2 + n2 = n2 (k2 + n2)

(iv)

(−1)kkCn+k

n (cid:80) k=−n

k2 + n2 = 0.

Lời giải.. Giả sử

n (cid:80) k=−n

với k = −n, −n + 1, . . . , n − 1, n và ta có biểu

Khi đó có ak =

= . 1 x(x2 − 1)(x2 − 22) . . . (x2 − n2) ak x − k

diễn

n (cid:88)

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

k=−n

(i) và (ii) Với x = i có được

= . (−1)n−kCn+k 2n x − k (2n)! x(x2 − 1)(x2 − 22) . . . (x2 − n2)

n (cid:88)

k=−n

n (cid:81) k=1

(2n)! i = (1 − ki). = (−1)kCn+k i − k (−1)kCn+k 2n k2 + 1 (k2 + 1)

Do vậy

và

n (cid:80) k=−n

n (cid:81) k=1

(iii) và (iv) Với x = ni ta nhận được đồng nhất thức dưới đây:

(2n)! = = 0. (−1)kCn+k 2n k2 + 1 (−1)kkCn+k k2 + 1 (k2 + 1)

n (cid:88)

k=−n

n (cid:81) k=1

(2n)! = ni = (n2 − nki). (−1)kCn+k 2n ni − k (−1)kCn+k 2n k2 + n2 (k2 + n2)

Vậy

và

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

n (cid:80) k=−n

n (cid:81) k=1

3.2 Xây dựng đồng nhất thức qua số phức

Sử dụng công thức Moivre trong số phức để xây dựng các đồng nhất thức hoặc tính một số tổng có liên quan trong tổ hợp.

Ví dụ 3.8. Tính các tổng sau đây:

(i) Tổng T1 = 1 + C4

n + C8

n + . . .

(ii) Tổng T2 = C1

n + C5

n + C9

n + . . .

(iii) Tổng T3 = C2

n + C6

n + C10

n + . . .

(iv) Tổng T4 = C3

n + C7

n + C11

n + . . .

(v) Tổng S = (T1 − T3)2 + (T2 − T4)2.

(v) Tổng P = T 2

1 + T 2

2 + T 2

3 + T 2 4 .

(−1)kCn+k k2 + n2 = k2 + n2 = 0. n2 (k2 + n2)

n − C2

n − iC3

n + C4

n + iC5

n − C6

n − . . . và (1 + i)n =

Lời giải.. Từ (1 + i)n = 1 + iC1 2 (cid:0) cos 2

(cid:1) suy ra

n 2 cos

+ i sin nπ 4 nπ 4

T1 − T3 = 2

n 2 sin

Vì 2n = (1 + 1)n = T1 + T2 + T3 + T4 và 0 = (1 − 1)n = T1 − T2 + T3 − T4 ta suy ra hệ phương trình:



n 2 cos

. T2 − T4 = 2 nπ 4 nπ 4

n 2 sin

T1 − T3 = 2

T2 − T4 = 2 nπ 4 nπ 4

 

T1 + T2 + T3 + T4 = 2n

Giải hệ phương trình ta được

(cid:1)

(cid:0)2n−1 + 2

n 2 cos

T1 − T2 + T3 − T4 = 0.

(cid:1)

(cid:0)2n−1 + 2

n 2 sin

T1 = 1 2 nπ 4

(cid:1)

(cid:0)2n−1 − 2

n 2 cos

T2 =

(cid:1)

(cid:0)2n−1 − 2

n 2 sin

T3 =

Từ đó suy ra S = 2n và P = 22n−2 + 2n−1.

Ví dụ 3.9. Giả sử hai dãy số nguyên (an) và (bn) xác định như sau:



T4 = 1 2 1 2 1 2 nπ 4 nπ 4 nπ 4

a0 = 3, a1 = 8, a2 = 58

an+2 = 8an+1 − 3an + 3an−1, n ≥ 2;

 

b0 = 3, b1 = 5, b2 = 45

2014b2013 + · · · + C2013

2014 b1 + b0 = C1

2014a2013 − C2

2014a2012 + · · · +

Chứng minh: C1 C2013

2014 a1 − a0.

Lời giải.. Đây là bài toán về dãy số nguyên nhưng lại xét bài toán trên C. Xét phương trình f (x) = x3 − 8x2 + 3x − 3 = 0. Gọi 3 nghiệm của phương trình

bn+2 = 5bn+1 + 10bn + 7bn−1, n ≥ 2.

3 = a0, x1 + x2 + x3 = a1, x2

1 + x2

2 + x2

3 = a2. Tổng

1 + x0 2 + x0 3 = an, n ≥ 0. 2 + yn

3 = bn, n ≥ 0, trong đó y1, y2, y3 là ba nghiệm của phương

2 + xn 1 + yn

trong C là x1, x2, x3. Dễ dàng kiểm tra x0 quát xn 1 + xn Tương tự yn trình g(y) = y3 − 5y2 − 10y − 7 = 0. Kiểm tra trực tiếp: f (y + 1) = g(y) và g(x − 1) = f (x). Vậy ta nhận được các hệ thức sau:

1 + xn

2 + xn

3 = (y1 + 1)n + (y2 + 1)n + (y3 + 1)n

an = xn

3 = (x1 − 1)n + (x2 − 1)n + (x3 − 1)n, n ≥ 0.

2 + yn

1 + yn

Do vậy

 

bn = yn



an = C0 b1 + Cn

n a0.

nbn−1 + · · · + Cn−1 n b0 nan−1 + · · · + (−1)n−1Cn−1

nbn + C1 nan − C1

Suy ra

a1 + (−1)nCn bn = C0

2014 b1 + b0 = C1

2014a2013 − C2

2014a2012 + · · · + C2013

2014 a1 − a0.

Ví dụ 3.10. Giả sử hai dãy số nguyên (an) và (bn) xác định như sau:



C1 2014b2013 + · · · + C2013

a0 = 3, a1 = 2, a2 = −6

an+2 = 2an+1 − 5an + an−1, n ≥ 2;

 

b0 = 3, b1 = −4, b2 = −2

Khi đó ta có kết quả sau đây:

(i) an = C0

bn+2 = −4bn+1 − 9bn − 9n−1, n ≥ 2.

nbn + 2C1

nbn−1 + · · · + 2n−1Cn−1

n b0;

(ii) bn = C0

b1 + 2nCn

nan − 2C1

nan−1 + · · · + (−1)n−12n−1Cn−1

n a0.

3 = a0, x1 + x2 + x3 = a1, x2

3 = a2. Tổng

2 + x2

1 + x2

Lời giải.. Đây là bài toán về dãy số nguyên nhưng lại xét bài toán trên C. Xét phương trình f (x) = x3 − 2x2 + 5x − 1 = 0. Gọi 3 nghiệm của phương trình trong C là x1, x2, x3. Dễ dàng kiểm tra x0 1 + xn quát xn

2 + x0 1 + x0 3 = an, n ≥ 0.

2 + xn

a1 + (−1)n2nCn

1 + yn

2 + yn

3 = bn, n ≥ 0, trong đó y1, y2, y3 là ba nghiệm của phương

Tương tự yn trình g(y) = y3 + 4y2 + 9y + 9 = 0. Kiểm tra trực tiếp: f (y + 2) = g(y) và g(x − 2) = f (x). Vậy ta nhận được các hệ thức sau:

1 + xn

2 + xn

3 = (y1 + 2)n + (y2 + 2)n + (y3 + 2)n

an = xn

1 + yn

2 + yn

3 = (x1 − 2)n + (x2 − 2)n + (x3 − 2)n, n ≥ 0.

Do vậy  

bn = yn



n b0; a1 + (−1)n2nCn

an = C0 b1 + 2nCn

n a0.

nbn−1 + · · · + 2n−1Cn−1 nan−1 + · · · + (−1)n−12n−1Cn−1

nbn + 2C1 nan − 2C1

Ta được kết quả (i) và (ii).

Ví dụ 3.11. Với số nguyên dương n ta có

3n−1 (cid:88)

bn = C0

k=0

3n (cid:88)

(−1)kC2k+1 3k = 0;

6n3k = 26n.

k=0 Lời giải.. Xét bài toán trên C. Ta có đồng nhất thức sau

(−1)kC2k

6n3k + i (cid:80)3n−1

k=0(−1)kC2k

k=0 (−1)kC2k+1

Suy ra 26n = (1 + i Do vậy ta có điều phải chứng minh.

3.3 Xây dựng đồng nhất thức qua hàm sinh

k=0 Ck

Một trong những nguồn gốc dẫn đến khái niệm hàm sinh chính là Định lý khai triển Nhị thức Newton (1 + x)n = (cid:80)n nxk và khai triển chuỗi lũy thừa = 1 + x + x2 + x3 + . . . . Đây là một kỹ thuật giải tích với của phân thức

√ (1 + i + i sin )6n = 26n(cos n2π + i sin n2π) = 26n. 3)6n = 26n(cos π 3 π 3 √ 3)6n = (cid:80)3n 3k.

nhiều ứng dụng trong tổ hợp và nghiên cứu dãy số . Trong mục này, tác giả đã sử dụng hàm sinh để xây dựng các đồng nhất thức trong tổ hợp. Trước tiên, ta bắt đầu với khái niệm về hàm sinh.

1 1 − x

Định nghĩa 3.1. Cho dãy số thực (an). Ta lập chuỗi lũy thừa

∞ (cid:88)

3.3.1 Khái niệm hàm sinh

n=0

Khi chuỗi lũy thừa S(x) hội tụ đến hàm f (x) nào đó thì ta gọi hàm f (x) là hàm sinh của dãy (an) đã cho.

Nhận xét 3.1. Trong nhiều trường hợp ta chưa biết dãy số nhưng bằng lập luận ta lại có thể tìm được hàm sinh f (x) của nó. Và từ hàm sinh của nó ta có thể tìm được dãy số, bằng công thức khai triển Maclaurine của hàm f (x):

S(x) = anxn.

Khi giải các bài toán tổ hợp, việc tìm nghiệm của bài toán thường là công việc đầu tiên phải làm. Với nhiều bài toán phần việc này tương đối khó khăn. Kỹ thuật hàm sinh giúp ta giải quyết khá nhiều bài toán hóc búa trong thực tế.

an = 1 n! dn dxn f (x)|x=0, n = 0, 1, 2, 3, . . .

3.3.2 Một số đồng nhất thức liên quan đến hàm sinh

= 1 + x + x2 + x3 + . . .

1 1 − x 1

∞ (cid:88)

1 (1 − x)2 = 1 + 2x + 3x2 + 4x3 + . . . x2 + x3 + . . . (1 − x)n = 1 + nx + n(n + 1) 2! n(n + 1)(n + 2) 3!

i+n−1xi. Ci

i=0

n+r−1.

nx2m − · · · + (−1)nxmn.

nxm + C2

= 1 − x + x2 − x3 + . . .

1 1 + x 1 1 − xr = 1 + xr + x2r + x3r + . . . Mệnh đề 3.1. Cho hàm sinh G(x) = (1 + x + x2 + . . . )n. i) Đặt ar là hệ số của xr trong khai triển của G(x) thì ar = Cr ii) (1 − xm)n = 1 − C1 iii) (1 + x + x2 + · · · + xm−1)n = (1 − xm)n(1 + x + x2 + . . . )n.

Mệnh đề 3.2. [Công thức xác định hệ số tích của hai hàm sinh] Cho hai hàm sinh của hai dãy (an); (bn) lần lượt là:

A(x) = a0 + a1x + a2x2 + . . .

Đặt

B(x) = b0 + b1x + b2x2 + . . .

Khi đó hệ số của xr trong khai triển của G(x) là

G(x) = A(x)B(x) = (a0 + a1x + a2x2 + . . . )(b0 + b1x + b2x2 + . . . ) = a0b0 + (a0b1 + a1b0)x + (a0b2 + a1b1 + a2b0)x2 + . . .

Chú ý 3.1. Gọi A(x) là hàm sinh cho dãy cách chọn các phần tử từ tập A, B(x) là hàm sinh cho dãy cách chọn các phần tử từ tập B. Nếu A và B rời nhau thì hàm sinh cho số cách chọn các phần tử từ tập A ∪ B là A(x)B(x).

a0br + a1br−1 + a2br−2 + · · · + ar−2b2 + ar−1b1 + arb0.

Trong một số bài toán đếm, thay vì đi tính trực tiếp số cách chọn, ta đưa về việc tính hệ số của hàm sinh sinh bởi dãy các cách chọn đó.

Ví dụ 3.12. Giả sử có 4 loại kẹo: Chanh, dâu, sôcôla, sữa. Tìm hàm sinh cho số cách chọn n cái kẹo thỏa mãn các điều kiện sau đây: a. Mỗi loại kẹo xuất hiện lẻ lần. b. Số kẹo của mỗi loại chia hết cho 3. c. Không có kẹo socola và nhiều nhất 2 kẹo chanh.

Lời giải. a. Vì mỗi loại kẹo xuất hiện là như nhau nên ta chỉ cần tìm hàm sinh cho số cách chọn một loại kẹo. Ta có

3.3.3 Ứng dụng của hàm sinh

0 cách chọn 0 cái kẹo

1 cách chọn 1 cái kẹo

0 cách chọn 2 cái kẹo

1 cách chọn 3 cái kẹo

. . .

Vậy hàm sinh cho số cách chọn một loại kẹo là x + x3 + x5 + . . . . Suy ra, hàm sinh cho số cách chọn n cái kẹo từ 4 loại kẹo là

b. Ta có, số cách chọn kẹo thỏa mãn điều kiện số kẹo của mỗi loại chia hết cho 3 là

A(x) = (x + x3 + x5 + . . . )4 = x4(1 + x2 + x4 + . . . )4 = x4 (1 − x2)4 .

1 cách chọn 0 cái kẹo

0 cách chọn 1 cái kẹo

0 cách chọn 2 cái kẹo

1 cách chọn 3 cái kẹo

0 cách chọn 4 cái kẹo

0 cách chọn 5 cái kẹo

1 cách chọn 6 cái kẹo

Hàm sinh cho số cách chọn một loại kẹo thỏa mãn điều kiện là

. . .

Vậy hàm sinh cho số cách chọn n cái kẹo từ 4 loại kẹo thỏa mãn điều kiện là

1 + x3 + x6 + x9 + . . .

c. Lập luận tương tự như trên, ta có: + Hàm sinh cho số cách chọn kẹo sôcôla là 1. + Hàm sinh cho số cách chọn kẹo chanh là 1 + x + x2. + Hàm sinh cho số cách chọn kẹo dâu là

B(x) = (1 + x3 + x6 + x9 + . . . )4 = 1 (1 − x3)4 .

Hàm sinh cho số cách chọn kẹo sữa là

. 1 + x + x2 + x3 + · · · = 1 1 − x

Vậy hàm sinh cho số cách chọn n cái kẹo từ 4 loại kẹo thỏa mãn điều kiện là

1 + x + x2 + x3 + · · · = . 1 1 − x

. = C(x) = 1(1 + x + x2) 1 1 − x 1 1 − x 1 + x + x2 (1 − x)2 .

Ví dụ 3.13. Giả sử có một số lượng đủ lớn các loại hoa quả gồm táo, mận, lê, đào. Hỏi có bao nhiêu cách sắp xếp một giỏ gồm n trái cây thỏa mãn yêu cầu sau đây: + Số táo phải chẵn; + Số quả mận phải chia hết cho 5; + Số quả lê không vượt quá 4; + Số quả đào không nhiều hơn 1.

Lời giải. Gọi an, bn, cn, dn tương ứng là số cách chọn n quả: táo, mận, lê, đào thỏa mãn yêu cầu bài toán. Khi đó, số cách chọn n trái cây thỏa mãn yêu cầu bài toán là

(cid:88)

p+q+r+s=n

Ta có: Hàm sinh của dãy (an) là

Sn = apbqcrds.

Hàm sinh của dãy (bn) là

A(x) = 1 + x2 + x4 + · · · = 1 1 − x2 .

Hàm sinh của dãy (cn) là

B(x) = 1 + x5 + x10 + x15 + · · · = 1 1 − x5 .

Hàm sinh của dãy (dn) là

A(x) = 1 + x + x2 + x3 + x4 = . 1 − x5 1 − x

Do Sn = (cid:80)

p+q+r+s=n apbqcrds nên hàm sinh của dãy Sn là

D(x) = 1 + x.

S(x) = A(x)B(x)C(x)D(x)

.(1 + x) = 1 1 − x5 . 1 − x5 1 − x

= 1 1 − x2 . 1 (1 − x)2 .

Khai triển S(x) =

∞ (cid:88)

(1 − x)2 theo chuỗi lũy thừa ta có

n=0

Vậy Sn = n + 1.

S(x) = 1 + 2x + 3x2 + · · · = (n + 1)xn

Ví dụ 3.14. [VMO 2012] Cho một nhóm gồm 5 cô gái, kí hiệu là G1, G2, G3, G4, G5 và 12 chàng trai. Có 17 chiếc ghế xếp thành một hàng ngang. Người ta xếp nhóm người đã cho ngồi vào các ghế đó sao cho các điều kiện sau đồng thời được thỏa mãn: + Mỗi ghế có đúng một người ngồi; + Thứ tự ngồi của các cô gái xếp theo thứ tự từ trái qua phải là G1, G2, G3, G4, G5; + Giữa G1 và G2 có ít nhất 3 chàng trai; + Giữa G4 và G5 có ít nhất một chàng trai và nhiều nhất 4 chàng trai. Hỏi có bao nhiêu cách xếp như vậy?

Lời giải. Gọi x1 là số chàng trai được xếp bên trái G1. x2 là số chàng trai được xếp giữa G1 và G2. x3 là số chàng trai được xếp giữa G2 và G3. x4 là số chàng trai được xếp giữa G3 và G4. x5 là số chàng trai được xếp giữa G4 và G5. x6 là số chàng trai được xếp bên phải G5. Khi đó, bộ số (x1, x2, x3, x4, x5, x6) hoàn toàn xác định vị trí các cô gái và ta có: i) x1 + x2 + x3 + x4 + x5 + x6 = 12; ii) x2 ≥ 3; iii) 1 ≤ x5 ≤ 4. Ta đi tính số cách chọn bộ (x1, x2, x3, x4, x5, x6). Hàm sinh cho số cách chọn x1, x3, x4, x6 là như nhau và bằng 1+t+t2 +t3 +· · · =

t3 1 − t

1 1 − t Hàm sinh cho số cách chọn x2 là t3 + t4 + t5 + · · · = Hàm sinh cho số cách chọn x5 là t + t2 + t3 + t4 = t(1 + t + t2 + t3). Vây hàm sinh cho số cách chọn bộ (x1, x2, x3, x4, x5, x6) là

t4 f (t) = (1 − t)5 (1 + t + t2 + t3) = t4 (1 − t)5 + t5 (1 − t)5 + t6 (1 − t)5 + t7 (1 − t)5 .

Hệ số của của tk trong khai triển

Số cần tìm chính là hệ số của t12 trong khai triển của f (t) thành lũy thừa hay 1 chính bằng tổng các hệ số của t8, t7, t6, t5 trong khai triển của g(t) = (1 − t)5 . k+4. Suy ra số cách chọn bộ

(1 − x)5 là Ck

12 + C7 C8

11 + C6

10 + C5 9 .

(x1, x2, x3, x4, x5, x6) là

Do vai trò của 12 người nam là như nhau nên số cách xếp thỏa mãn điều kiện bài toán là

12 + C7

11 + C6

10 + C5

9 )12!.

Tiếp theo ta xét bài toán cây nhị phân. Cây nhị phân là cây mà mỗi

đỉnh của nó có không quá hai con.

Ví dụ 3.15. Cho trước n đỉnh trên mặt phẳng. Hỏi có thể xây dựng được bao nhiêu cây nhị phân từ các đỉnh này?

Lời giải. Trong mọi cây nhị phân n đỉnh, ta luôn có đẳng thức:

(C8

trong đó: l là số đỉnh của cây con trái và r là số đỉnh của cây con phải. Kí hiệu cn là số cây nhị phân n đỉnh (n = 0, 1, 2, 3, . . . ). Tập các cây nhị phân n đỉnh có thể phân hoạch thành các lớp theo số đỉnh của cây con trái l = 0, 1, 2, 3, . . . , n − 1. Vậy thì

(3.1)

n = 1 + l + r

Xây dựng hàm sinh

∞ (cid:88)

cn = c0cn−1 + c1cn−2 + c2cn−3 + · · · + cn−1c0, n ≥ 1.

n=0

Theo (3.2) ta có

∞ (cid:88)

C(x) = cnxn.

n=1

∞ (cid:88)

C(x) = 1 + (c0cn−1 + c1cn−2 + c2cn−3 + · · · + cn−1c0)xn

n=0

= 1 + x (c0cn + c1cn−1 + c2cn−2 + · · · + cnc0)xn

Ta được phương trình bậc hai đối với C(x) là

= 1 + x.C2(x).

Giải phương trình ta được hàm sinh

x.C2(x) − C(x) + 1 = 0.

√ 1 ± C(x) = . 1 − 4x 2x

Để khai triểm Maclaurine hàm sinh này ta chỉ cần khai triển hàm nhận được

√ 1 − 4x và

∞ (cid:88)

n=1

Hàm sinh C(x) là hàm dương nên theo khai triển trên thì trong công thức nghiệm trên ta phải lấy dấu trừ và nhận được √

√ 1 − 4x = 1 − 2 Cn−1 2n−2xn. 1 n

∞ (cid:88)

2nxn. Cn

n=1

n=0

Vậy số các cây nhị phân n đỉnh là

1 − C(x) = = Cn−1 2n−2xn−1 = 1 − 4x 2x 1 n 1 n + 1

2n, n = 0, 1, 2, 3, . . .

Dãy số cn được gọi là dãy số Catalan.

Cn cn = 1 n + 1

Kết luận

Trong luận văn này, tác giả đã đặt ra và hoàn thành được một số kết quả như sau:

(i) Trình bày được một số khái niệm cơ bản về tổ hợp và tổ hợp suy rộng;

(ii) Trình bày được bốn nguyên lý cơ bản trong tổ hợp. Đó là Nguyên lý Dirichlet, Nguyên lý bù trừ, Nguyên lý cực hạn, Nguyên lý bất biến;

(iii) Đưa ra được những ứng dụng giải một số bài toán tổ hợp áp dụng các

nguyên lý trên;

(iv) Xây dựng các đồng nhất thức trong tổ hợp;

(v) Sử dụng các kết quả đạt được để giải một số bài toán dạng khác;

Tài liệu tham khảo

[1] Nguyễn Hữu Điển (1999), Phương pháp Dirichlet và ứng dụng, NXB Khoa

học và kỹ thuật.

[2] Nguyễn Văn Mậu (2008), Chuyên đề chọn lọc tổ hợp và toán rời rạc, NXB

Giáo Dục.

[3] Nguyễn Văn Mậu (4/2012), Các chuyên đề toán bồi dưỡng học sinh giỏi

, Kỷ yếu hội nghị khoa học, Hà Nội.

[4] Đinh Thị Kim Phương (11/2012), Các chuyên đề toán bồi dưỡng học sinh

giỏi , Kỷ yếu hội nghị khoa học, Thái Nguyên.

[5] Phạm Minh Phương ( 2010), Một số chuyên đề toán tổ hợp bồi dưỡng học

sinh giỏi THPT, NXB Giáo dục Việt Nam.

[6] Hoàng Chí Thành (2001), Giáo trình tổ hợp, NXB Đại học Quốc gia Hà

Nội.

[7] Tạp chí toán học và tuổi trẻ, Tuyển tập 5 năm, NXB Giáo Dục, 2003.

[8] Alexander Yong(2005), "On combinatorics of Quiver components Formu-

las", Journal of Algebraric Combinatorics, vol 21, 351- 371.

[9] Kenneth H Rosen(1998), Toán học rời rạc ứng dụng trong tin học, NXB

khoa học và kĩ thuật.

[10] Tài liệu từ Internet.

Luận văn Thạc sĩ Khoa học: Nâng cao hiệu quả bài toán sắp xếp với giải thuật song song

MỘT VÀI NGUYÊN LÝ

VÀ

BÀI TOÁN TỔ HỢP

MỘT VÀI NGUYÊN LÝ

VÀ

BÀI TOÁN TỔ HỢP

Mục lục

Lời cảm ơn

Mở đầu

Chương 1

Kiến thức chuẩn bị

Chương 2

Một vài nguyên lý trong tổ hợp

Chương 3

Một vài đồng nhất thức trong tổ

hợp

Kết luận

Tài liệu tham khảo

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

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

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube