Luận văn Thạc sĩ Toán học: Phương pháp đếm hai lần và ứng dụng

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

TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- ĐỖ THỊ THÚY HÒA

PHƢƠNG PHÁP ĐẾM HAI LẦN VÀ ỨNG DỤNG

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

THÁI NGUYÊN - 2019

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

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

ĐỖ THỊ THÚY HÒA

PHƢƠNG PHÁP ĐẾM HAI LẦN VÀ ỨNG DỤNG

Chuyên ngành: Phƣơng pháp Toán sơ cấp

Mã số: 8 46 01 13

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

NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. Trịnh Thanh Hải

THÁI NGUYÊN - 2019

Mục lục

Mở đầu 1

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

1.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1 Cơ sở của phương pháp đếm . . . . . . . . . . . . . . 3

1.1.2 Hoán vị, chỉnh hợp và tổ hợp . . . . . . . . . . . . . 9

1.2 Một số phương pháp giải bài toán đếm của toán tổ hợp . . . 13

1.2.1 Sử dụng công thức bao hàm và loại trừ . . . . . . . . 13

1.2.2 Sử dụng phương pháp hệ thức truy hồi . . . . . . . . 16

1.2.3 Sử dụng phương pháp liệt kê các trường hợp . . . . . 18

1.2.4 Xây dựng song ánh giải một số bài toán tổ hợp . . . 21

2 Vận dụng phương pháp đếm hai lần vào giải bài toán đếm 25

2.1 Ý tưởng của phương pháp đếm hai lần . . . . . . . . . . . . 25

2.2 Một số nguyên lý, tính chất của toán tổ hợp thường được vận

dụng vào giải bài toán đếm . . . . . . . . . . . . . . . . . . 29

2.3 Vận dụng phương pháp đếm hai lần vào giải các bài toán đếm 32

2.3.1 Đếm số tập con, số cặp và số hoán vị . . . . . . . . . 32

2.3.2 Phương pháp đếm hai lần và đồ thị hữu hạn . . . . . 47

2.3.3 Phương pháp ma trận liên thuộc . . . . . . . . . . . 51

2.4 Một số bài toán đề nghị . . . . . . . . . . . . . . . . . . . . 62

Kết luận 63

Tài liệu tham khảo 64

Mở đầu

Toán tổ hợp là một bài toán khó, thường xuất hiện trong các kì thi học

sinh giỏi cấp tỉnh, cấp quốc gia và quốc tế. Chính vì vậy toán tổ hợp luôn

dành được sự quan tâm rất lớn từ các bạn học sinh, các thầy, cô giáo và

các nhà toán học. Mặc dù vậy, tài liệu cho toán tổ hợp dành cho học sinh

giỏi ở Việt nam vẫn còn rất ít và hạn chế.

Phương pháp đếm hai lần “double counting” đã được nhóm tác giả Law

Ka Ho, Leung Tat Wing và Li Kim Jin đăng tải trên tạp chí Mathematical

Excalibur (Volume 13, Number 4, 2008) đưa ra các minh họa sinh động cho

việc vận dụng phương pháp đếm hai lần vào giải một vài đề thi toán quốc

tế.

Xuất phát từ thực tế trên và với mục đích tích lũy thêm các kiến thức

về cách giải các bài toán đếm của toán tổ hợp với phương pháp đếm hai

lần và vận dụng vào giải một số bài toán đếm trong các đề thi học sinh giỏi

trong nước và quốc tế làm tư liệu cho công việc giảng dạy của bản thân,

tôi đã lựa chọn hướng nghiên cứu vận dụng phương pháp đến hai lần vào

giải một số bài toán đếm.

Luận văn tập trung vào hoàn thành các nhiệm vụ chính sau:

• Tìm hiểu bài toán đếm của toán tổ hợp và các nguyên lý, tính chất của

toán tổ hợp thường được vận dụng để đưa ra lời giải cho các bài toán

đếm.

• Cơ sở toán học của phương pháp “Đếm hai lần” trong việc tìm lời giải

cho bài toán đếm của toán tổ hợp.

• Sưu tầm một số bài toán, đề thi và bài toán đếm của toán tổ hợp dành

cho học sinh giỏi.

• Đưa ra lời giải bằng cách vận dụng phương pháp “Đếm hai lần” cho một

số bài toán đếm dành cho học sinh giỏi.

Ngoài ra luận văn cũng đưa ra các cách giải khác nhau của cùng một bài

toán đếm và so sánh những phương pháp giải đó với việc vận dụng phương

pháp đếm hai lần để có những nhận xét thú vị.

Thái Nguyên, ngày 31 tháng 3 năm 2019

Tác giả luận văn

Đỗ Thị Thúy Hòa

Chương 1

Kiến thức chuẩn bị

1.1 Đặt vấn đề

Như chúng ta biết, các khái niệm hoán vị, chỉnh hợp, tổ hợp được hình

thành từ các phép đếm. Các khái niệm này ra đời giúp chúng ta trình bày

bài toán đếm đơn giản hơn. Tuy nhiên, khi gặp các bài chứng minh các

đẳng thức liên quan đến hoán vị, chỉnh hợp, tổ hợp thì chúng ta thường sử

dụng các biến đổi đại số hoặc khai triển nhị thức Newton để chứng minh.

Do đó, việc chứng minh các bài toán tổ hợp và các khái niệm của nó không

có mối quan hệ nào. Điều này ít nhiều làm mất đi vẻ đẹp của các khái niệm

toán học nói chung và các khái niệm về hoán vị, chỉnh hợp nói riêng. Trong

nội dung chương 1 của luận văn, tôi sẽ giới thiệu cách chứng minh các bài

toán tổ hợp bằng phương pháp đếm. Nội dung mục này được tham khảo

chủ yếu trong tài liệu [1] và một số bài toán hay trong các đề thi học sinh

1.1.1 Cơ sở của phương pháp đếm

giỏi được tác giả sưu tầm và trình bày.

Một bài toán tổ hợp thường liên quan mật thiết với việc “đếm” số khả

năng thực hiện một hành động nào đó. Phép đếm có hai quy tắc cơ bản là

phép cộng và phép nhân.

Quy tắc 1.1 (Quy tắc cộng). Giả sử có k công việc T1, T2, . . . , Tk. Các việc này có thể làm tương ứng bằng n1, n2, . . . , nk cách và giả sử không có hai

việc nào có thể làm đồng thời. Khi đó số cách làm một trong k việc đó là n1 + n2 + · · · + nk.

Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp như sau: Cho n tập hợp A1, A2, . . . , An là các tập hợp hữu hạn đôi một rời nhau, tức là ∀1 ≤ i, j ≤ n, Ai ∩ Aj = ∅ nếu i (cid:54)= j. Khi đó số cách chọn a1,

n (cid:83) k=1

hoặc a2, . . . , hoặc an sẽ bằng số cách chọn phần tử a thuộc Ak và bằng

n (cid:83) k=1

n (cid:80) k

| Ak| = |Ak|.

Ví dụ 1.1. Trong một tiết tự học, trên bàn giáo viên có 10 quyển sách tiếng

Anh, 10 quyển bài tập Toán và 5 quyển bài tập Hóa. Hỏi có bao nhiêu cách

chọn một quyển sách?

Chứng minh. Gọi A1, A2, A3 lần lượt là tập các quyển sách tiếng Anh, bài tập Toán và bài tập Hóa. Khi đó, có 10 cách chọn một quyển sách tiếng Anh, tức là |A1| = 10. Có 10 cách chọn một quyển bài tập Toán, tức là |A2| = 10. Có 5 cách chọn một quyển bài tập Hóa, nghĩa là |A3| = 5.

Vậy, theo quy tắc cộng, số cạch chọn một quyển sách là

|A1| + |A2| + |A3| = 10 + 10 + 5 = 25.

Bản chất toán học 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. Tuy nhiên 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 n tập hợp bất kì

(không nhất thiết rời nhau). Khi đó, ta có quy tắc cộng cho số phần tử của

hợp của n tập hợp bất kỳ, thường được gọi là công thức bao hàm và loại

trừ.

Định lý 1.1 (Công thức bao hàm và loại trừ). Cho n ≥ 2 tập hợp hữu hạn

A1, . . . , An. Khi đó ta có

n (cid:88)

i=1

1≤i

(cid:88) (cid:88) |Ai ∩ Aj ∩ Ak| |Ai ∩ Ak| + |A1 ∪ A2 ∪ . . . ∪ An| = |Ai| −

1≤i

1≤i1

+ · · · +

+ · · · + (−1)n+1|A1 ∩ A2 ∩ . . . ∩ An|.

Ví dụ 1.2. Trong tập S = {1, 2, . . . , 280} có bao nhiêu số không chia hết

cho 2, 3, 5, 7?

Chứng minh. Ta sẽ đếm xem trong tập S có bao nhiêu số chia hết cho ít

... 2}, A2 = {k ∈ S| k

S| k nhất một trong các số 2, 3, 5, 7. Kí hiệu A1 = {k ∈ S| k ... 5}, A4 = {k ∈ S| k ... 3}, A3 = {k ∈ ... 7}. Khi đó |A1 ∪ A2 ∪ A3 ∪ A4| là tập hợp

(cid:21) (cid:21) (cid:21) = 56; = 140, |A2| = = 93, |A3| = |A1| = các số chia hết cho ít nhất một trong các số 2, 3, 5, 7. Ta có: (cid:20)280 3 (cid:20)280 5 (cid:21) (cid:21) (cid:21) = 28; |A4| = = 40, |A1 ∩ A2| = = 46, |A1 ∩ A3| = (cid:20)280 2.3 (cid:20)280 2.5 (cid:20)280 2 (cid:20)280 7 (cid:21) (cid:21) (cid:21) = 13; |A1 ∩ A4| = = 20, |A2 ∩ A3| = = 18, |A2 ∩ A4| = (cid:20)280 3.5 (cid:20)280 3.7 (cid:21) (cid:21) = 9; = 8, |A1 ∩ A2 ∩ A3| = |A3 ∩ A4| = (cid:20)280 2.7 (cid:20)280 5.7 (cid:20) 280 2.3.5 (cid:21) (cid:21) = 4; |A1 ∩ A2 ∩ A4| = = 6, |A1 ∩ A3 ∩ A4| = (cid:20) 280 2.5.7 (cid:21) (cid:21) = 1; |A2 ∩ A3 ∩ A4| = = 2, |A1 ∩ A2 ∩ A3 ∩ A4| = (cid:20) 280 2.3.5.7 (cid:20) 280 2.3.7 (cid:20) 280 3.5.7

Sử dụng công thức bao hàm và loại trừ ta được

|A1 ∪ A2 ∪ A3 ∪ A4| = 140 + 93 + 56 + 40 − 46 − 28 − 20 − 18

− 13 − 8 − 9 − 6 − 4 − 2 + 1 = 216.

Như vậy trong tập S có 280 − 216 = 64 số không chia hết cho 2, 3, 5, 7.

Quy tắc 1.2 (Quy tắc nhân). Cho n đối tượng a1, a2, . . . , an. Nếu có m1 cách chọn đối tượng a1 và với mỗi cách chọn a1 có m2 cách chọn đối tượng

a2, sau đó với mỗi cách chọn a1, a2 có m3 cách chọn a3, . . . Cuối cùng với mỗi cách chọn a1, a2, . . . , an−1 có mn cách chọn đối tượng an. Như vậy ta có m1.m2 . . . mn−1.mn cách chọn đối tượng a1, rồi chọn đối tượng a2, rồi đến a3, . . . , rồi đến an.

n (cid:89)

Tương tự như quy tắc cộng, quy tắc nhân phát biểu bằng ngôn ngữ tập hợp như sau: Giả sử có n tập hợp hữu hạn A1, A2, . . . , An. Khi đó, số cách chọn (S) bộ gồm n phần tử (a1, a2, . . . an) với ai ∈ Ai, (1 ≤ i ≤ n) sẽ là

k=1

mk. S = |A1 × A2 × . . . × An| = m1.m2 . . . mn =

Ví dụ 1.3. Từ các chữ số {0, 1, 3, 5, 7} có thể lập được bao nhiêu số tự nhiên

có 3 chữ số đôi một khác nhau?

Chứng minh. Ta gọi số tự nhiên có 3 chữ số cần tìm là abc. Ta thấy, có 4

cách chọn a, 4 cách chọn b và 3 cách chọn c từ các chữ số {0, 1, 3, 5, 7}. Như

vậy theo quy tắc nhân, ta có 4.4.3 = 48 số tự nhiên có 3 chữ số đôi một

khác nhau.

Để áp dụng quy tắc nhân, điều cốt yếu là phải thiết kế một mô hình gồm

việc thực hiện nhiều công đoạn. Số cách thực hiện ở mỗi công đoạn phải

không phụ thuộc vào cách nào đã thực hiện ở công đoạn trước đó. Thành

thử, muốn sử dụng được quy tắc nhân, mô hình của ta bao gồm việc thực

hiện liên tiếp các công đoạn và số cách thực hiện ở mỗi công đoạn phải như

nhau với mọi cách đã thực hiện ở công đoạn trước đó.

Ví dụ 1.4. Có bốn người A, B, C, D cần chọn ba người vào chức Giám đốc,

Kế toán trưởng và Chủ tịch Hội đồng quản trị. Giả sử việc chọn nhân sự

phải thảo mãn yêu cầu: Ông A không thể được chọn làm Giám đốc, chức

Chủ tịch HĐQT phải là ông C hoặc ông D. Hỏi có bao nhiêu cách chọn?

Giải. Việc chọn ba vị trí chức Giám đốc, Kế toán trưởng và Chủ tịch Hội

đồng quản trị tiến hành theo 3 công đoạn:

Công đoạn 1: Chọn Giám đốc: có 3 cách chọn (chọn B, C, D).

Công đoạn 2: Chọn Kế toán trưởng: có 3 cách chọn Kế toán trưởng từ

ba người còn lại.

Công đoạn 3: Chọn Chủ tịch Hội đồng quản trị: có 2 cách chọn (ông C

hoặc D). Theo quy tắc nhân thì có 3.3.2 = 18 cách chọn. Tuy nhiên đáp số

này không chính xác vì số cách thực hiện công đoạn 3 phụ thuộc vào kết

quả của các công đoạn 1 và 2 trước đó. Nếu ở các công đoạn trước, ông C

và ông D đã được chọn thì ở công đoan 3 chỉ có 1 cách hoặc không có.

Tuy nhiên, nếu việc chọn ba vị trí Giám đốc, Kế toán trưởng và Chủ

tịch hội đồng quản trị được tiến hành theo ba công đoạn khác thì vẫn có

thể áp dụng quy tắc nhân. Cụ thể như sau:

Công đoạn 1: Chọn Chủ tịch hội đồng quản trị: có 2 cách chọn C hoặc

Công đoạn 2: Chọn Giám đốc: Ta luôn có 2 cách chọn dù kết quả của

công đoạn 1 thế nào. Sau công đoạn 1 còn 3 người, trong đó có ông A. Bỏ

ông A ra thì còn 2 người có thể chọn vào chức Giám đốc.

Công đoạn 3: Chọn Kế toán trưởng: luôn có 2 cách từ 2 người còn lại.

Vậy có 2.2.2 = 8 cách chọn.

Việc chia giai đoạn trong bài toán trên là ví dụ minh họa cho chúng ta

thấy những bước cụ thể để thực hiện công việc cần làm. Chúng ta có thể

không cần trình bày cụ thể các giai đoạn trong lời giải. Ngoài ra, để giải

quyết một bài toán, chúng ta có thể kết hợp nhiều quy tắc khác nhau. Do

vậy, chúng ta cần nắm rõ các quy tắc để áp dụng trong các trường hợp cụ

thể.

Tiếp theo, chúng ta sẽ đề cập đến Nguyên lý ngăn kéo Dirichlet. Người

đầu tiên đề xuất ra nguyên lý này là nhà toán học người Đức Perter Guster

Dirichlet (1805-1859) khi ông đề cập tới nó với tên gọi “nguyên lý ngăn kéo”

(Schubfachprinzip). Người ta thường gọi “nguyên lý ngăn kéo Dirichlet” hay

đôi khi gọi gọn là "nguyên lý Dirichlet" (tên gọi gọn này có thể gây ra nhầm

lẫn với nguyên lý Dirichlet về hàm điều hòa). Có nhiều cách phát biểu cho

nguyên lý ngăn kéo Diriclet (đối tượng phát biểu là chim hoặc thỏ). Nội

dung nguyên lý như sau: Nếu nhốt n + 1 con thỏ vào n cái chuồng thì bao

giờ cũng có một chuồng chứa ít nhất hai con thỏ. Đây được coi như nguyên

lý Dirichlet cơ bản.

Nguyên lý 1.1 (Nguyên lý ngăn kéo Dirichlet mở rộng). Nếu nhốt n con

(cid:21) thỏ vào m ≥ 2 cái chuồng thì tồn tại một chuồng có ít nhất (cid:20)n + m − 1 m

con thỏ.

Ở đây ta dùng kí hiệu [x] là phần nguyên của số x.

Chứng minh. Giả sử mọi chuồng thỏ không có đến

(cid:21) (cid:21) (cid:21) = + 1 = + 1 (cid:20)n + m − 1 m (cid:20)n − 1 m (cid:20)n − 1 m

(cid:21) con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng con. Từ (cid:20)n − 1 m (cid:21) đó suy ra tổng số con thỏ không vượt quá m. ≥ n − 1 con. Vô lý. (cid:20)n − 1 m

Vậy giả sử ban đầu là sai.

Nguyên lý ngăn kéo Dirichlet tưởng chừng đơn giản như vậy nhưng nó

là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của

toán học. Nó đặc biệt được áp dụng trong các lĩnh vực khác nhau của toán

học. Nguyên lý này thực chất là một định lý về tập hữu hạn. Người ta có

thể phát biểu nguyên lý này dưới dạng tập hợp như sau.

Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số

lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc

nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn

tại ít nhất hai phần tử khác nhau của A mà chúng tương ứng với một phần

tử của B.

Ví dụ 1.5. Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai

người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật

khác nhau.

1.1.2 Hoán vị, chỉnh hợp và tổ hợp

Định nghĩa 1.1. Cho tập hợp A gồm n phần tử, n ≥ 0. Mỗi cách sắp xếp

n phần tử của tập hợp A theo một thứ tự nào đó được gọi là một hoán vị của n phần tử đã cho, kí hiệu là Pn.

Ta có công thức

Pn = n!

Định nghĩa 1.2. Hoán vị 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.

Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần được kí hiệu là P (n1, n2, . . . , nk) và được tính bằng công thức

P (n1, n2, . . . , nk) = n! n1!n2! . . . nk!

Ví dụ 1.6. Với các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm

chín chữ số, trong đó mỗi chữ số 0, 1, 2, 3 xuất hiện đúng một lần, chữ số 4

xuất hiện đúng hai lần và chữ số 5 xuất hiện đúng ba lần?

Chứng minh. Xét một số tùy ý x = 140525345 và kí hiệu các vị trí của x một cách hình thức, ta có x = a1a2a3a4a5a6a7a8a9. Khi đó, mỗi số x tương ứng với một hoán vị của chín phần tử a1, a2, a3, a4, a5, a6, a7, a8, a9.

Số các hoán vị khác nhau của chín phần tử ai (1 ≤ i ≤ 9) là 9! song do a2 = a8 = 4, nên khi đổi chỗ a2 và a8 cho nhau, thì hoán vị a1a2a3a4a5a6a7a8a9 vẫn chỉ cho ta số x. Tương tự đổi chỗ hai trong ba phần tử a4, a6, a9 cho nhau ta vẫn nhận được số x.

Như vậy, khi thực hiện 2! hoán vị a2, a8 và 3! hoán vị a4, a6, a9 ta chỉ

được một số cần tìm x.

Vậy số các số có thể lập được là

= 30240. S = 9! 2!3!

Định nghĩa 1.3. Cho tập hợp A gồm n phần tử, n ≥ 1. Mỗi bộ gồm

k (0 ≤ k ≤ n) phần tử được sắp thứ tự của tập A được gọi là một chỉnh hợp chập k của n phần tử thuộc A và được kí hiệu là Ak n.

Số chỉnh hợp chập k của n phần tử được tính bởi công thức

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

. Ak n! (n − k)!

Nhận xét 1.1. Một chỉnh hợp chập n của n được gọi là một hoán vị của

n phần tử, ta có

n = Pn = n!.

Định nghĩa 1.4. Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của

một tập gồm n phần tử được gọi là một chỉnh hợp lặp chập k của n phần

tử.

n, bằng số ánh xạ từ

Số chỉnh hợp lặp chập k của n phần tử, kí hiệu Ak

tập k phần tử đến tập n phần tử và bằng nk, tức là

n = nk.

Ví dụ 1.7. Từ bốn chữ số 1, 2, 3, 5 có thành lập được bao nhiêu số chẵn

gồm bốn chữ số?

Chứng minh. Vì tập {1, 2, 3, 5} chỉ có duy nhất một số chẵn là 2, nên chúng

ta gọi x = abcd, với a, b, c, d ∈ {1, 2, 3, 5} là các số cần tìm. Do số cần tìm

là chẵn nên d = 2.

Mặt khác a, b, c có thể bằng nhau nên y = abc là một chỉnh hợp lặp chập

3 của bốn phần tử 1, 2, 3, 5.

Để thành lập số x ta chỉ cần lấy một số y nào đó rồi thêm số 2 vào cuối.

4 = 43 = 64.

Bởi vậy, số các số x = abc2 bằng số các số y = abc và bằng A3

Định nghĩa 1.5. Cho tập hợp A gồm n phần tử, n ≥ 1. Mỗi tập con gồm

k (0 ≤ k ≤ n) phần tử của A được gọi là một tổ hợp chập k của n phần tử

đã cho.

Nhận xét 1.2. Hai tổ hợp được coi là khác nhau khi và chỉ khi có ít nhất

một phần tử khác nhau.

n và được

Số tổ hợp chập k (0 ≤ k ≤ n) của n phần tử được kí hiệu là C k

tính theo công thức

n =

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

Định nghĩa 1.6. Cho A = {a1, a2, . . . , an}. Một tổ hợp lặp chập m (m không nhất thiết phải nhỏ hơn n) của một tập hợp là một bộ gồm m phần

tử, mà mỗi phần tử này là một trong nhưng phần tử của A.

n để kí hiệu số tổ hợp lặp chập m của n phần tử.

Ta sử dụng kí hiệu C m

n+k−1.

Mệnh đề 1.1. Số tổ hợp chập k từ tập n phần tử bằng C k

Chứng minh. Mỗi tổ hợp lặp chập k từ tập 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 để

phân cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần

tử thứ i của tập xuất hiện trong tổ hợp. Chẳng hạn, tổ hợp lặp chập 6 của

4 phần tử được biểu thị bởi:

∗ ∗ | ∗ | | ∗ ∗∗

mô tả tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử thứ hai, không có

phần tử thứ ba và 3 phần tử thứ tư của tập hợp.

Mỗi dãy n − 1 thanh và k ngôi sao ứng với một xâu nhị phân có độ dài

n + k − 1 với k số 1. Do đó số các dãy n − 1 thanh đứng và k ngôi sao chính

là số tổ hợp chập k từ tập n + k − 1 phần tử.

Ví dụ 1.8. Giả sử có 4 loại bóng mầu xanh, đỏ, tím, vàng với số lượng mỗi

loại không hạn chế. Hai bộ bóng được xem là khác nhau nếu có ít nhất một

mầu với số lượng thuộc hai bộ khác nhau. Hỏi có bao nhiêu cách chọn ra

các bộ 6 quả bóng khác nhau.

Chứng minh. Vì trong mỗi bộ sáu quả có thể có các quả bóng cùng mầu và

không phân biệt thứ tự chọn, nên số cách chọn khác nhau bằng số tổ hợp

lặp chập 6 của 4 phần tử (tập hợp bóng cùng mầu được coi là một phần

tử) và được tính bằng công thức

6+4−1 =

4 = C 6

C 6 = 84. 9! 6!3!

Mệnh đề 1.2. Số hoán vị của n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2, . . . , nk phần tử như nhau thuộc loại k bằng . n! n1!n2! . . . nk!

n .C n2

n−n1 · · · C nk

n−n1−···−nk−1 =

. Chứng minh. Để xác định số hoán vị trước tiên chúng ta nhận thấy có C n1 n cách giữ n1 chỗ cho n1 phần tử loại 1, còn lại n − n1 chỗ trống. Sau đó có C n2 n−n1 cách đặt n2 phần tử loại 2 vào hoán vị, còn lại n − n1 − n2 chỗ trống. Tương tự ta đặt các phần tử loại 3, loại 4, . . . , loại k − 1 vào các chỗ trống trong hoán vị. Cuối cùng có C nk n−n1−···−nk−1 cách đặt nk phần tử loại k vào hoán vị. Theo quy tác nhân tất cả các hoán vị là C n1 n! n1!n2! . . . nk!

Ví dụ 1.9. Có bao nhiêu cách chia những xấp có 5 quân bài cho mỗi một

người chơi trong bàn chơi có 4 người từ cỗ bài chuẩn có 52 quân bài.

37 =

42.C 5

47.C 5

52.C 5 cách chia 4 người chơi mỗi người một xấp 5 quân bài.

C 5 Chứng minh. Ta nhận thấy người đầu tiên có thể nhận được 5 quân bài bằng C 5 52 cách, còn 47 quân bài. Người thứ hai có thể nhận được 5 quân bài bằng C 5 47 cách, còn 42 quân bài. Người thứ 3 có thể nhận được 5 quân bài bằng C 5 42 cách, còn 37 quân bài. Người thứ tư có thể nhận được 5 quân bài bằng 37 cách. Như vậy theo nguyên lý nhân ta có C 5 52! 5!5!5!5!32!

Ví dụ trên là bài toán điển hình cho việc phân bố các đồ vật khác nhau

vào các hộp khác nhau. Các đồ vật là 52 quân bài, còn 4 hộp là 4 người chơi

và số còn lại để trên bàn. Số cách sắp xếp các đồ vật vào trong hộp được

cho bởi mệnh đề sau.

Mệnh đề 1.3. Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho có ni vật được đặt vào trong hộp thứ i, với i = 1, 2, . . . , k bằng

. n! n1!n2! . . . nk!(n − n1 − · · · − nk)!

Ví dụ 1.10. Trong một buổi giới thiệu sản phẩm, công ty phát 100 sản

phẩm dùng thử cho nhân viên tiếp thị sản phẩm. Mỗi một khách hàng ghé

qua gian hàng trưng bày sản phẩm, nhân viên sẽ phát cho họ 2 sản phẩm

tặng kèm và 1 phiếu mua hàng giảm giá 20% sản phẩm. Có bao nhiêu cách

phát những sản phẩm khuyến mại cho khách hàng biết rằng có 25 khách

96 cách nhận . . .

hàng ghé gian hàng trưng bày.

Chứng minh. Ta nhận thấy, khách hàng đầu tiên có C 2 100 cách để nhận sản phẩm khuyến mại. Chúng ta còn 98 sản phẩm khuyến mại để tặng cho các khách hàng tiếp theo. Người thứ hai có C 2 98 cách nhận sản phẩm khuyến mại. Tương tự người thứ 3 chúng ta có C 2 Như vậy theo quy tắc nhân và áp dụng mệnh đề 1.3 chúng ta có số cách

phát các sản phẩm khuyến mại cho 25 khách hàng là

1.2 Một số phương pháp giải bài toán đếm của toán tổ

hợp

1.2.1 Sử dụng công thức bao hàm và loại trừ

= . 100! 2!2!2! . . . 2!(100 − 2.25)! 100! 2!2! . . . 2!50!

Một trong những kết quả nền tảng của lí thuyết tổ hợp là định lý về

“Công thức bao hàm và loại trừ”. Vì thực chất, công thức tính số phần tử

của hợp các tập hợp đã là công thức bao hàm và loại trừ và được đề cập

trong mục 1.1.1 của luận văn, bởi vì trong công thức này đối với mỗi phần

tử đã tính được số lần nó được đếm và số lần nó không được đếm.

Chúng ta sẽ mở rộng thêm công thức bao hàm và loại trừ: Cho tập hợp A và k tập con của nó Ai ⊂ A, i = 1, k. Nếu đã biết lực lượng của các tập con Ai và của giao 2, 3 . . . , k tập con của A, thì có bao nhiêu phần tử thuộc A, mà không nằm trong bất kỳ một tập con Ai nào.

(i) Cho A là tập hữu hạn và A1 ⊂ A. Khi đó

(1.1) A1 ∪ A1 = A nên |A1| = |A| − |A1|.

(ii) Cho A và A1, A2 ⊂ A. Khi đó

(1.2) |A1 ∩ A2| = |A| − |A1| − |A2| + |A1 ∩ A2|.

(iii) Cho A và A1, A2, A3 ⊂ A. Khi đó

|A1 ∩ A2 ∩ A3| = |A| − |A1| − |A2| − |A3| + |A1 ∩ A2|

(1.3) + |A1 ∩ A3| + |A3 ∩ A2| − |A1 ∩ A2 ∩ A3|.

(iv) Cho A và A1, A2, A3, A4 ⊂ A. Khi đó

|A1 ∩ A2 ∩ A3 ∩ A4| = |A| − |A1| − |A2| − |A3| − |A4| + |A1 ∩ A2|

+ |A1 ∩ A3| + |A1 ∩ A4| + |A3 ∩ A2| + |A4 ∩ A2| + |A3 ∩ A4|

− |A1 ∩ A2 ∩ A3| − |A1 ∩ A2 ∩ A4| − |A2 ∩ A3 ∩ A4|

(1.4) + |A1 ∩ A2 ∩ A3 ∩ A4|.

(v) Bằng phép quy nạp theo n (n ≥ 2) đối với tập hợp A và n tập hợp con

n (cid:92)

n (cid:88)

A1, A2, . . . , An ⊂ A có công thức

i=1

i(cid:54)=j

| Ai| = |A| − |Ai| + |Ai ∩ Aj| − |A1 ∩ A2 ∩ A3|

i=1 − · · · − |An−2 ∩ An−1 ∩ An| + · · · + (−1)n|A1 ∩ A2 ∩ . . . ∩ An|.

(1.5)

Chúng ta sẽ xét một số bài toán trong chương trình trung học phổ thông

sử dụng công thức trên để giải như sau.

Bài toán 1.1. Có bao nhiêu số tự nhiên từ 1 đến 5000 mà không chia hết

cho 2, không chia hết cho 5 và cũng không chia hết cho 9?

Chứng minh. Gọi tập A = {1, 2, . . . , 5000}, A1 = {a ∈ A| a A| a ... 5}, A3 = {a ∈ A| a

... 2}, A2 = {a ∈ ... 9}. Theo nguyên lý bù trừ, số các số nguyên dương từ 1 đến 5000 mà không chia hết cho 2, không chia hết cho 5 và cũng

không chia hết cho 9 là

|A \ (A1 ∪ A2 ∪ A3)| = |A| − (|A1| + |A2| + |A3|) + |A1 ∩ A2| + |A2 ∩ A3|

+ |A1 ∩ A3| − |A1 ∩ A2 ∩ A3|,

trong đó

(cid:21) (cid:21) (cid:21) = 555; |A1| = = 2500, |A2| = (cid:20)5000 2 (cid:20)5000 5 (cid:20)5000 9 (cid:21) (cid:21) = 277; |A1 ∩ A2| = = 500, |A1 ∩ A3| = = 1000, |A3| = (cid:20)5000 2.9 (cid:21) (cid:21) = 55; |A2 ∩ A3| = = 111, |A1 ∩ A2 ∩ A3| = (cid:20)5000 2.5 (cid:20)5000 5.9 (cid:20) 5000 2.5.9

Thay vào công thức trên ta được

|A\(A1∪A2∪A3)| = 5000−(2500+1000+555)+500+277+111−55 = 1778.

Nhận xét 1.3. Chúng ta có thể áp dụng mở rộng của công thức bao hàm và loại trừ để giải bài toán trên như sau: Với cách đặt các tập A, A1, A2, A − 3 như trên thì số các số tự nhiên từ 1 đến 5000 mà không chia hết cho 2,

không chia hết cho 5 và cũng không chia hết cho 9 bằng lực lượng của tập A1 ∩ A2 ∩ A3 và được tính bằng công thức (1.3):

|A1 ∩ A2 ∩ A3| = 5000 − 2500 − 1000 − 555 + 500 + 277 + 111 − 55

= 1778.

Bài toán 1.2. Một cuộc Hội thao cấp xã có bốn môn thi: Cầu lông, bóng

bàn, chạy và cờ tướng. Có 100 vận động viên tham gia. Khi tổng kết, Ban

tổ chức nhận thấy rằng: Môn cầu lông có 18 vận động viên tham gia, môn

bóng bàn có 26 vận động viên tham gia, môn chạy có 19 vận động viên tham

gia và môn cờ tướng có 24 vận động viên tham gia, trong đó 5 người tham

gia cả cầu lông và bóng bàn; 2 người tham gia cả cầu lông và chạy; 3 người

tham gia cầu lông và cờ tướng; 5 người tham gia bóng bàn và chạy; 4 người

tham gia bóng bàn và cờ tướng; 3 người tham gia chạy và cờ tướng; 2 người

tham gia đồng thời cả cầu lông, bóng bàn và chạy; 3 người tham gia cầu

lông, bóng bàn và cờ tướng; 2 người tham gia cầu lông, chạy và cờ tướng; 4

người tham gia bóng bàn, chạy và cờ tướng; 1 người tham gia đồng thời cả

bốn môn của Hội thao. Hỏi có bao nhiêu vận động viên không tham gia thi

đấu một môn nào của Hội thao?

Chứng minh. Gọi A là tập gồm tất cả các vận động viên tham gia Hội thao, A1 tập các vận động viên tham gia môn cầu lông, A2 tập các vận động viên tham gia môn bóng bàn, A3 tập các vận động viên tham gia môn chạy, A4 tập các vận động viên tham gia môn cờ tướng.

Khi đó, số vận động viên không tham gia thi đấu một môn nào của Hội thao chính bằng lực lượng của tập A1 ∩ A2 ∩ A3 ∩ A4 và được tính nhờ công thức (1.4):

|A1 ∩ A2 ∩ A3 ∩ A4| = 100(18 + 26 + 19 + 24) + (5 + 2 + 3 + 5 + 4 + 3)

1.2.2 Sử dụng phương pháp hệ thức truy hồi

− (2 + 3 + 2 + 4) + 1 = 100 − 8 + 22 − 11 + 1 = 25.

Đôi khi rất khó định nghĩa một đối tượng một cách tường minh. Nhưng

có thể dễ dàng định nghĩa đối tượng này qua chính nó. Kỹ thuật này được

gọi là đệ quy. Định nghĩa đệ quy của một dãy số định rõ giá trị của một

hay nhiều hơn các số hạng đầu tiên và quy tác xác định các số hạng tiếp

theo từ các số hạng đi trước. Định nghĩa đệ quy có thể dùng để giải các bài

toán đếm. Khi đó quy tắc tìm các số hạng từ các số hạng đi trước được gọi

là đệ quy truy hồi.

Định nghĩa 1.7. Hệ thức truy hồi (hay công thức truy hồi) đối với dãy số {an} là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dãy. Dãy số được gọi là lời giải hay nghiệm của hệ thức truy hồi nếu các số hạng

của nó thỏa mãn hệ thức truy hồi này.

Nội dung cơ bản của phương pháp này như sau: Thay vì ta đếm trực tiếp an theo yêu cầu bài toán, ta sẽ thiết lập hệ thức quan hệ giữa an, an−1, . . . để từ đó tính được an. Chúng ta sẽ giải một số bài toán sau bằng hệ thức truy hồi.

Bài toán 1.3. Giả sử một người gửi 10 triệu đồng vào tài khoản tiết kiệm

của mình tại ngân hàng với lãi suất 11% mỗi năm. Sau 30 năm anh ta có

bao nhiêu tiền trong tài khoản của mình?

Chứng minh. Gọi Pn là tổng số tiền có trong tài khoản tiết kiệm sau n năm. Vì số tiền có trong tài khoản sau n năm bằng số có sau n − 1 năm cộng lãi suất của năm thứ n, nên ta thấy dãy {Pn} thỏa mãn hệ thức truy hồi sau:

P0 = 10;

P1 = P0 + 0, 11P0 = 1, 11P0 P2 = P1 + 0, 11P1 = 1, 11P1 = (1, 11).(1, 11)P0 = (1, 11)2P0

. . . Pn = Pn−1 + 0, 11Pn−1 = (1, 11)Pn−1 = (1, 11)nP0.

Từ đó suy ra Pn = (1, 11)n.10, thay n = 30 ta được P30 = (1, 11)30.10 ≈ 228, 9 triệu đồng.

Bài toán 1.4. [1] Giả sử Fk là tập hợp tất cả các bộ (A1, A2, . . . , Ak), trong đó Ai (i = 1, 2, . . . , k) là một tập con của {1, 2, . . . , n} (các tập A1, A2, . . . , Ak có thể trùng nhau). Hãy tính

(A1,A2,...,Ak)∈Fk

(cid:88) Sn = |A1 ∪ A2 ∪ . . . ∪ Ak|.

(Trường hợp n = 1998 là bài thi APMO 1998).

Chứng minh. Do có 2n tập con của {1, 2, . . . , n} nên có 2nk bộ (A1, A2, . . . , Ak). Với mỗi k−bộ (A1, A2, . . . , Ak) của tập {1, 2, . . . , n − 1}, ta có thêm hoặc không thêm n vào tập Ai để được k−bộ (A1, A2, . . . , Ak) của {1, 2, . . . , n}. Với chú ý rằng số k−bộ (A1, A2, . . . , Ak) của tập {1, 2, . . . , n − 1} là 2(n−1)k và có 2k − 1 cách thêm n vào k−bộ (A1, A2, . . . , Ak) của tập {1, 2, . . . , n − 1} thì ta có

Sn = 2kSn−1 + (2k − 1).2k(n−1).

Dễ thấy S1 = 2k − 1. Từ đấy bằng quy nạp ta chứng minh được

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

Bài toán 1.5 (IMO 1979, [1]). Cho A và E là hai đỉnh đối tâm của một

hình tám cạnh đều. Có một con ếch bắt đầu nhảy từ A. Tại bất cứ đỉnh nào

trừ E, ếch có thể tới một trong hai đỉnh kề. Nếu ếch nhảy tới E thì nó dừng lại ở đó. Gọi an là số đường đi phân biệt của đúng n bước nhảy để ếch nhảy từ A đến E. Chứng mịnh rằng

√ √ (cid:104) (2 + 2)n−1 − (2 − 2)n−1(cid:105) . a2n−1 = 0, a2n = 1 √ 2

Chứng minh. Ta có a2n−1 = 0 là hiển nhiên. Gọi bn là số đường đi từ C tới E qua n bước nhảy. Qua hai bước đầu tiên, ếch có thể về A hoặc đến C

hoặc đến G. Do đó

(1.6) a2n = 2a2n−2 + b2n−2 ∀n > 0.

Từ C (hoặc G), sau hai bước nhảy, ếch có thể về lại C hoặc tới A, nếu

n > 2, do đó

(1.7) a2n = 2b2n−2 + an−2 ∀n > 1.

Từ (1.6) và (1.7) suy ra

a2n = 4a2n−2 − 2a2n−4.

Cùng với a2 = 0, a4 = 2 ta dễ dàng chứng minh

1.2.3 Sử dụng phương pháp liệt kê các trường hợp

√ √ (cid:104) (2 + 2)n−1 − (2 − 2)n−1(cid:105) . a2n = 1 √ 2

Đối với một bài toán, khi chưa tìm ra được phương pháp tốt để giải thì

liệt kê là biện pháp cuối cùng để thực hiện. Có thể nói, liệt kê là phương

pháp phổ dụng nhất để giải quyết các bài toán đếm trong chương trình toán

trung học phổ thông.

Bài toán 1.6. Người đưa thư phân phát thư đến 19 nhà ở một dãy phố.

Người đưa thư phát hiện ra rằng không có hai nhà liền kề nhau cùng nhận

thư trong cùng một ngày và không có nhiều hơn hai nhà cùng không nhận

thư trong cùng một ngày. Hỏi có bao nhiêu cách phân phối thư?

Chứng minh. Từ giả thiết cho thấy cứ hai nhà liền kề nhau có một nhà

không nhận thư. Suy ra số nhà không nhận thư là ít nhất là 9 và số nhà

nhận thư nhiều nhất là 10. Như vậy, có nhiều nhất 10 người nhận thư trong

cùng một ngày.

Từ giả thiết không có nhiều hơn hai nhà cùng không nhận thư trong

cùng một ngày, như vậy cứ ba nhà liên tiếp có một nhà nhận thư. Vì vậy

có ít nhất có 6 nhà nhận thư trong cùng một ngày. Ta liệt kê các trường

hợp của bài toán:

Trường hợp 1: Có 6 nhà nhận thư.

Gán số 1 vào 6 vị trí nhận thư và gán số 0 vào những nhà không nhận thư.

Hơn nữa, giữa hai vị trí 1 phải có một số nhà số 0 nên suy ra có 5 nhà

không nhận thư. Còn 8 nhà không được nhận thư sắp xếp như sau: 2 nhà

5 = 5 cách sắp xếp.

không nhận thư ở hai vị trí đầu và ở hai vị trí cuối, 4 nhà còn lại được sắp

6 = 15

6 = 20

6 = 15

6 = 6 cách

xếp vào 5 vị trí xen kẽ với các nhà nhận thư. Như vậy, trường hợp này có C 4 Trường hợp 2: Có 7 nhà nhận thư. 7 nhà này xen kẽ với 6 nhà không nhận

6 = 6 cách

thư nên còn 6 nhà không nhận thư được sắp xếp như sau: 2 nhà đầu, 2 nhà cuối, 2 nhà còn lại xếp vào 6 vị trí xen kẽ: có C 2 cách sắp xếp. 2 nhà đầu, 1 nhà cuối, 3 nhà còn lại xếp vào 6 vị trí xen kẽ: có C 3 cách sắp xếp. 1 nhà đầu, 2 nhà cuối, 3 nhà còn lại sắp xếp vào 6 vị trí xen kẽ: có C 3 cách sắp xếp. 1 nhà đầu, 1 nhà cuối, 4 nhà còn lại sắp xếp vào 6 vị trí xen kẽ: có C 4 cách sắp xếp. 2 nhà đầu, 0 nhà cuối, 4 nhà còn lại xếp vào 6 vị trí xen kẽ: có C 4 cách sắp xếp. 0 nhà đầu, 2 nhà cuối, 4 nhà còn lại xếp vào 6 vị trí xen kẽ: có C 4 cách sắp xếp. 1 nhà đầu, 0 nhà cuối, 5 nhà còn lại xếp vào 6 vị trí xen kẽ: có C 5 sắp xếp. 0 nhà đầu, 1 nhà cuối, 5 nhà còn lại xếp vào 6 vị trí xen kẽ: có C 5

6 = 1 cách

sắp xếp. 0 nhà đầu, 0 nhà cuối, 6 nhà còn lại xếp vào 6 vị trí xen kẽ: có C 6 sắp xếp.

Như vậy, có 113 cách sắp xếp.

Trường hợp 3: Có 8 nhà nhận thư. 8 nhà này xen kẽ với 7 nhà không nhận

7 = 7 cách

7 = 21 cách

7 = 7 cách

7 = 35 cách

thư nên còn 4 nhà không nhận thư sẽ được sắp xếp như sau

2 nhà đầu, 2 nhà cuối: có 1 cách sắp xếp 2 nhà đầu, 1 nhà cuối, 1 nhà còn lại sắp xếp vào 7 vị trí: có C 1 sắp xếp. 1 nhà đầu, 2 nhà cuối, 1 nhà còn lại sắp xếp vào 7 vị trí: có C 1 sắp xếp. 1 nhà đầu, 1 nhà cuối, 2 nhà còn lại sắp xếp vào 7 vị trí: có C 2 sắp xếp. 2 nhà đầu, 0 nhà cuối, 2 nhà còn lại sắp xếp vào 7 vị trí: có C 2 sắp xếp. 0 nhà đầu, 2 nhà cuối, 1 nhà còn lại sắp xếp vào 7 vị trí: có C 1 sắp xếp. 0 nhà đầu, 1 nhà cuối, 3 nhà còn lại sắp xếp vào 7 vị trí: có C 3 sắp xếp. 1 nhà đầu, 0 nhà cuối, 3 nhà còn lại sắp xếp vào 7 vị trí: có C 3 sắp xếp. 0 nhà đầu, 0 nhà cuối, 4 nhà còn lại sắp xếp vào 7 vị trí: có C 4 sắp xếp.

Như vậy, có 183 cách sắp xếp.

Tương tự, trường hợp có 9 nhà nhận thư, chúng ta có 47 cách sắp xếp.

Trường hợp 10 nhà nhận thư, chúng ta có 1 cách sắp xếp.

Vậy tổng cộng người đưa thư có 5 + 113 + 183 + 47 + 1 = 349 cách phân

phối thư.

Bài toán 1.7. Có hai học sinh lớp A, 3 học sinh lớp B và 4 học sinh lớp

C xếp thành một hàng ngang sao cho giữa hai học sinh lớp A không có học

sinh lớp B. Hỏi có bao nhiêu cách xếp hàng như vậy?

Chứng minh. Xét các trường hợp sau:

• Trường hợp 1: Hai học sinh lớp A đứng cạnh nhau: có 2!.8! cách xếp

hàng.

4.7!

• Trường hợp 2: Giữa hai học sinh lớp A có 1 học sinh lớp C: có 2!A1

cách xếp hàng.

4.6!

• Trường hợp 3: Giữa hai học sinh lớp A có 2 học sinh lớp C: có 2!A2

cách xếp hàng.

4.5!

• Trường hợp 4: Giữa hai học sinh lớp A có 3 học sinh lớp C: có 2!A3

cách xếp hàng.

4.4!

• Trường hợp 5: Giữa hai học sinh lớp A có 4 học sinh lớp C: có 2!A4

4.4!) = 145152

4.5! + A4

4.6! + A3

4.7! + A2

cách xếp hàng.

1.2.4 Xây dựng song ánh giải một số bài toán tổ hợp

Vậy theo quy tắc cộng có 2!(8! + A1 cách xếp hàng.

Trở ngại lớn nhất khi giải một bài toán tổ hợp là xác định hướng đi. Rõ

ràng để có thể xác định hướng đi tốt thì việc rèn luyện các phương pháp

tiếp cận là rất cần thiết. Mục này sẽ giới thiệu một phương pháp hiệu quả

trong nhiều bài toán tổ hợp và được gọi là phương pháp song ánh.

Định nghĩa 1.8. Cho ánh xạ f : A → B. Ánh xạ f được gọi là một đơn ánh nếu với hai phần tử bất kì a1, a2 ∈ A mà a1 (cid:54)= a2 thì f (a1) (cid:54)= f (a2), tức là f (a1) = f (a2) ⇔ a1 = a2.

Ánh xạ f được gọi là một toàn ánh nếu với mọi b ∈ B đều tồn tại a ∈ A

để f (a) = b.

Ánh xạ f được gọi là một song ánh nếu với mọi b ∈ B tồn tại và duy

nhất a ∈ A để f (a) = b. Nói cách khác, f là song ánh khi và chỉ khi nó

đồng thời là đơn ánh và toàn ánh.

Định lý 1.2. Cho A, B là hai tập hữu hạn. Khi đó

• Nếu có một đơn ánh f : A → B thì |A| < |B|.

• Nếu có một toàn ánh f : A → B thì |A| ≥ |B|.

• Nếu có một song ánh f : A → B thì |A| = |B|.

Như vậy, phương pháp xây dựng song ánh để giải một số bài toán tổ

hợp nâng cao dựa trên kết quả của định lý trên. Một cách tự nhiên, kết quả

trên hướng chúng ta đến ý tưởng sử dụng song ánh để so sánh lực lượng hai

tập hợp.

Bài toán 1.8. Cho tập A = {1, 2, . . . , 2n}. Một tập con B của A được gọi

là một tập cân nếu trong tập đó số các số chẵn và số các số lẻ bằng nhau.

(Tập rỗng là một tập cân vì số các số chẵn và số các số lẻ trong tập rỗng

bằng 0). Hỏi A có chứa bao nhiêu tập cân?

Chẳng hạn với n = 2, A = {1, 2, 3, 4}. A có 6 tập con cân là các tập:

∅, {1, 2}, {1, 4}, {3, 2}, {3, 4}, {1, 2, 3, 4}.

Chứng minh. Kí hiệu X = {2, 4, . . . , 2n} là tập tất cả các số chẵn của A và

Y = {1, 3, . . . , 2n − 1} là tập tất cả các số lẻ của A. Gọi C là họ tất cả các

tập cân của A và D là họ các tập con của A có đúng n phần tử.

Ta lập một ánh xạ f : C → D. Giả sử B là một tập cân. Kí hiệu B1, B2

tương ứng là tập các số chẵn và tập các số lẻ của B. Khi đó đặt

f (B) = B1 ∩ (Y \ B2).

Do B là tập cân nên |B1| = |B2|. Thành thử

|f (B)| = |B1| + |Y \ B2| = |B1| + |Y | − |B2| = |Y | = n.

Vậy f (B) ∈ D.

Tiếp theo ta chứng minh f là một song ánh.

+ f là đơn ánh: Giả sử f (B) = f (C), suy ra

B1 ∩ (Y \ B2) = C1 ∩ (Y \ C2).

Vì B1, C1 là tập các số chẵn; (Y \ B2), (Y \ C2) là tập các số lẻ nên từ đó suy ra B1 = C1; Y \ B2 = Y \ C2. Do đó B1 = C1, B2 = C2 hay B = C.

+ f là toàn ánh: Giả sử M ∈ D là một tập con thuộc A có n phần tử. Kí hiệu M1, M2 tương ứng là tập các số chẵn và tập các số lẻ của M . Đặt M1 = B1, B2 = Y \ M2 và B = B1 ∪ B2. Ta có

|B1| = |M1|; |B2| = |Y | − |M2| = n − |M2| = |M | − |M2| = |M1|.

Vậy nên |B1| = |B2|, tức là B là một tập cân. Rõ ràng

f (B) = B1 ∩ (Y \ B2) = M1 ∪ M2 = M.

Vì có một song ánh giữa họ các tập cân và họ các tập con có n phần tử của

2n tập cân.

A nên theo định lý 1.2, số các tập cân của A bằng số các tập con có n phần tử của A. Vậy A có tất cả C n

Bài toán 1.9 (VMO 2002, [1]). Cho tập S gồm tất cả các số nguyên trong

đoạn [1, 2002]. Gọi T là tập tất cả các tập con khác rỗng của S. Với mỗi X

thuộc T kí hiệu m(X) là trung bình cộng các phần tử của X. Tính

m = , (cid:80) m(X) |T |

trong đó, lấy tổng theo tất cả các tập X thuộc T.

Chứng minh. Xây dựng song ánh:

f : T → T

X (cid:55)→ f (X) = 2003 − x, ∀x ∈ X, X ∈ T.

Rõ ràng

m(X) + m(f (X)) = 2003.

Do đó

(cid:88) (cid:88) 2 m(X) = (m(X) + m(f (X))) = |T |.2003

⇒ m = = . (cid:80) m(X) |T | 2003 2

Từ việc so sánh lực lượng của các tập hợp, phương pháp song ánh có

thể giúp chúng ta đếm số phần tử của một tập hợp thông qua sự so sánh

lực lượng của tập hợp đó với một tập khác mà ta đã biết số phần tử của

nó.

Chú ý 1.1. Chúng ta đã trình bày các phương pháp để giải các bài toán

đếm cơ bản và một số bài toán đếm nâng cao. Đối với nhiều bài toán đếm

phức tạp hơn, đặc biệt là đối với các bài toán đếm dành cho học sinh giỏi

hay trong các đề thi chọn học sinh giỏi thì các phương pháp trên chưa chắc

đã cho ta lời giải hoặc có thì cũng là một lời giải phức tạp. Trong trường

hợp này, chúng ta cần sử dụng đến các phương pháp đếm khác, chẳng hạn

là phương pháp đếm 2 lần (sẽ được trình bày trong chương 2).

Chương 2

Vận dụng phương pháp đếm hai lần vào giải bài toán đếm

Nội dung Chương 2 chủ yếu nói về phương pháp đếm hai lần để giải các

bài toán đếm có mức độ khó cao, chủ yếu các bài toán của các kỳ thi quốc

tế qua các năm. Các bài toán được trích dẫn chủ yếu trong các tài liệu [4],

2.1 Ý tưởng của phương pháp đếm hai lần

[5].

Giả sử ta cần chứng minh bài toán có dạng A = B. Ta sẽ đi đếm số cách

thực hiện một công việc X nào đó theo hai cách:

Cách 1 ta được kết quả số cách thực hiện công việc X là A.

Cách 2 cho ta kết quả số cách thực hiện công việc X là B.

Từ đó ta có được A = B. Nguyên lý đếm bằng hai cách được phát biểu như

Nguyên lý 2.1 (Nguyên lý đếm bằng hai cách). Nếu cùng một số lượng

được đếm theo hai cách thì kết quả thu được phải bằng nhau.

Như vậy, không chỉ những bài toán tổ hợp có thể áp dụng phương pháp

đếm hai lần mà các bài toán đếm khác cũng có thể vận dụng phương pháp

này. Chúng ta xét ví dụ đơn giản sau.

n = C n−k

với mọi k, n ∈ N; n ≥ 1; 0 ≤ k ≤

Ví dụ 2.1. Chứng minh rằng C k n.

Chứng minh. Bài toán này đã được chứng minh trong chương trình toán

trung học phổ thông bằng cách khai triển ta có thể dễ dàng thu được kết

quả mong muốn. Ta có:

n =

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

Tuy nhiên, ta có thể giải bài toán trên bằng phương pháp đếm hai lần như sau. Trước tiên, xét tập X = {x1, x2, . . . , xn}. Ta thấy vế trái của đẳng thức trên là số tập con A gồm k phần tử của tập X. Để tính số tập A ta làm

theo hai cách sau:

Cách 1: Mỗi cách lấy k phần tử trong X, ta có một tập con A gồm k phần tử của tập X, nên số tập con A là C k n.

Cách 2: Mỗi cách lấy n − k phần tử của tập X và loại n − k phần tử

này đi, ta có được k phần tử còn lại là một tập con A gồm k phần tử của X, nên số tập con A là C n−k .

n = C n−k

. Do đó ta có C k

Nhận xét 2.1. Cả hai cách giải trên đều thu về được cùng một kết quả

nhưng trong giới hạn chương trình toán trung học phổ thông, giáo viên

thường dạy phương pháp đơn giản và dễ nhớ cho học sinh. Việc giải bài

toán bằng phương pháp đếm hai lần tuy phức tạp hơn, nhưng nó giữ nguyên

được vẻ đẹp của các khái niệm toán học, đồng thời cũng mở rộng các cách

chứng minh của một bài toán và được áp dụng nhiều trong các đề thi học

sinh giỏi.

Ví dụ 2.2 (Đẳng thức Pascal). Cho n ≥ 2, k là các số tự nhiên thỏa mãn

1 ≤ k ≤ n. Chứng minh rằng

n = C k

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

C k (2.1)

Chứng minh. Sử dụng các phép biến đổi đơn giản ta cũng có thể chứng

minh được đẳng thức trên. Thật vậy,

n−1 + C k−1

n−1 =

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

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

= [n − k + k] = = C k n. (n − 1)! k!(n − k)! n(n − 1)! k!(n − k)!

Ngoài sử dụng biến đổi đẳng thức như trên, chúng ta có thể giải bài toán

trên bằng phương pháp đếm hai lần. Ta thấy vế trái của (2.1) là số tập con

gồm k phần tử của tập gồm n phần tử nên ta đi đếm số tập con A gồm k phần tử của tập X = {x1, x2, . . . , xn}. Ta có hai cách thực hiện việc này:

Cách 1: Mỗi cách lấy k phần tử trong X, ta có một tập con A gồm k phần tử của tập X, nên số tập con A là C k n.

Cách 2: Số tập con A bao gồm 2 loại, ta sẽ đi đếm số tập thuộc loại này

(i) Gồm những tập con chứa phần tử xn. Mỗi tập con A thuộc loại này cho ta một tập A(cid:48) = A \ {xn} là tập con gồm k − 1 phần tử của tập X \ {xn}. Và ngược lại mỗi tập A(cid:48) cho ta một tập A nên suy ra số tập A thuộc loại này chính bằng số tập A(cid:48) và bằng C k−1 n−1.

n−1.

(ii) Gồm những tập con không chứa phần tử xn. Như vậy các phần tử của tập A được lấy từ tập X \ {xn} gồm n − 1 phần tử nên số tập A loại này là C k

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

Do đó theo cách 2 thì số tập A là C k

n = C k

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

Vậy ta có C k

Qua 2 ví dụ trên đã phần nào giúp chúng ta hiểu được cách phân tích

một bài toán tổ hợp, đưa việc giải một bài toán tổ hợp dựa trên phương

pháp đếm hai lần. Chúng ta sẽ giải các ví dụ tiếp theo bằng phương pháp

đếm hai lần.

Ví dụ 2.3. Cho n ≥ 1 là số tự nhiên. Chứng minh đẳng thức sau

n)2 + (C 1

n)2 + · · · + (C n

n )2 = C n 2n.

(C 0

Chứng minh. Ta thấy vế phái của đẳng thức chính là số tập con A gồm n

phần tử của tập X gồm 2n phần tử nên ta xét bài toán sau: Hãy tính số tập con A gồm n phần tử của tập X = {x1, x2, . . . , x2n}.

Cách 1: Mỗi cách lấy n phần tử trong X, ta có một tập con A gồm n phần tử của tập X, nên số tập con A là C n 2n.

n = (C k

nC n−k

Cách 2: Chia tập X thành hai tập X1 = {x1, x2, . . . , xn} và X2 = {xn+1, xn+2, . . . , x2n}. Để tính số tập con A ta làm như sau:

Lấy k phần tử (k = 0, n) thuộc tập X1 gồm n phần tử, rồi lấy n − k phần tử còn lại từ tập X2 gồm n phần tử và ta có số tập con A là n)2 (theo ví dụ 2.1) ứng với mỗi k. Cho k chạy từ 0 đến n C k rồi lấy tổng ta có được kết quả chính là số tập A cần tìm, hay

n)2 + (C 1

n)2 + · · · + (C n

n )2 = C n 2n.

(C 0

Ví dụ 2.4. Chứng minh đẳng thức sau với n ≥ 1 là số tự nhiên

n + 2C 2

n + 3C 3

n + · · · + nC n

n = n2n−1.

C 1

Chứng minh. Xét vế phải của đẳng thức trên ta thấy: n là số cách chọn 1 phần tử từ một tập có n phần tử, còn 2n−1 chính là số tập con của tập có n−1 phần tử. Do đó ta xét bài toán: Cho tập hợp X = {x1, x2, . . . , xn}. Hãy đếm số cặp (a, A) trong đó a ∈ X và A là một tập con của tập X (cid:48) = X \{a}.

Cách 1: Ta có n cách chọn a, với mỗi cách chọn a ta có 2n−1 cách chọn A. Do đó có n2n−1 cách chọn cặp (a, A).

n = C n−k

Cách 2: Ta chọn A là một tập con gồm k phần tử, với k = 0, n − 1 nên ta có C k cách chọn A. Mỗi cách chọn A ta sẽ chọn a ∈ X \ A

nên có n − k cách chọn a. Khi cho k chạy từ 0 đến n − 1 và lấy tổng thì

n−1 (cid:88)

ta có được cặp số (a, A) hay là ta có

n = C 1

n + 2C 2

n + 3C 3

n + · · · + nC n

n cặp (a, A).

k=0

(n − k)C n−k

So sánh kết quả của hai cách đếm ta có

n + 2C 2

n + 3C 3

n + · · · + nC n

n = n2n−1.

C 1

Nhận xét 2.2. Qua các ví dụ trên ta thấy, để vận dụng tốt phương pháp

này chúng ta cần hiểu rõ ý nghĩa của các đối tượng có trong đẳng thức. Với

việc xét một bài toán đếm và đếm theo nhiều cách sẽ cho chúng ta các kết

2.2 Một số nguyên lý, tính chất của toán tổ hợp thường

được vận dụng vào giải bài toán đếm

quả khác nhau về mặt hình thức và từ đó có được các đẳng thức tổ hợp.

Có rất nhiều cách khác nhau để chứng minh một bài toán đếm (sử dụng

song ánh, đại số tuyến tính và các dạng đề quy), tuy nhiên các nguyên lý

dưới đây được xem là các kết quả đẹp nhất của chúng. Việc vận dụng các

nguyên lý trên với từng bài toán khác nhau dựa trên tính sáng tạo của các

đối tượng người đọc.

Trước hết chúng ta sẽ đến với một cách phát biểu khác của nguyên lý

đếm bằng hai cách.

p∈R

q∈C

Nguyên lý 2.2 (Nguyên lý Fubini). Cho hai tập hữu hạn R, C và S ⊆ R × C. Nếu (p, q) ∈ S, ta nói rằng p và q liên thuộc với nhau. Đặt rp là số các phần tử liên thuộc với p ∈ R và cq là số các phần tử liên thuộc với q ∈ C. Khi đó (cid:88) (cid:88) rp = |S| = cq.

Để minh họa cho tập S, ta sẽ dùng đến khái niệm ma trận liên thuộc

của S.

Định nghĩa 2.1. Ma trận M = (apq) là ma trận mà các cột và các hàng của nó tương ứng được đánh số theo các phần tử của R và C với

1 nếu (p, q) ∈ S   apq = 0 nếu (p, q) /∈ S 

Khi đó rp là tổng các phần tử ở cột p, cq là tổng các phần tử ở cột q và |S| là tổng tất cả các phần tử của ma trận M .

Với một số bài toán, phương pháp ma trận liên thuộc sẽ giúp chúng ta

dễ hình dung hơn về cấu trúc của bài toán, từ đó đưa ra lời giải cho bài

toán. Việc vận dụng nguyên lý Fubini sẽ được trình bày trong mục 2.3.3

tới.

Ứng dụng của phép đếm hai lần còn được sử dụng trong lý thuyết đồ

thị để đếm số các cây từ n đỉnh phân biệt. Có nhiều phương pháp để chứng

minh công thức Cayley (như chứng minh bằng song ánh, sử dụng đệ quy

hay đại số tuyến tính) nhưng phương pháp đếm hai lần được xem là một

trong những phương pháp chứng minh đẹp nhất.

Nguyên lý 2.3 (Công thức Cayley). Chứng minh rằng có đúng nn−1 cây có thể tạo thành từ n đỉnh phân biệt.

Chứng minh. Ta sẽ đếm số N các dãy các cạnh có hướng có thể thêm vào n

đỉnh trên để tạo thành một cây có gốc. Các cạnh có hướng được thêm vào

có hướng sao cho với mỗi đỉnh V thì các cạnh thuộc đường nối gốc R của

cây với V có hướng từ R đến V . Gọi Tn là số các cây biểu diễn khác nhau của đồ thị đầy đủ Kn. Với mỗi cây trong số Tn cây chưa có gốc, ta chọn ra một trong số n đỉnh làm gốc và chọn một trong số (n − 1)! hoán vị của n − 1 cạnh của cây để tạo thành

một dãy cạnh có hướng (chú ý rằng hướng của mỗi cạnh được xác định duy

nhất vì giữa hai đỉnh bất kỳ của một cây chỉ có đúng một đường nối duy

nhất). Suy ra

N = Tn.n.(n − 1)! = n!Tn

Ta sẽ xây dựng một cây có gốc như trên bằng cách thêm từng cạnh vào n đỉnh đã cho. Giả sử rằng ta đã thêm n − k cạnh (k = 2, n) vào K n. Khi

đó ta thu được một bụi có gốc gồm k cây. Có n(k − 1) cách thêm vào một

cạnh: đỉnh đầu của nó là một trong số n đỉnh và đỉnh cuối của nó là một

n (cid:89)

trong số k − 1 gốc của k − 1 cây không chứa đỉnh đầu. Vì vậy ta có

k=2

n(k − 1) = nn−1.(n − 1)! = n!.nn−2. N =

Từ hai đẳng thức trên ta suy ra n!Tn = n!.nn−2 hay Tn = nn−2.

Một số bài toán có thể được giải quyết bằng cách sử dụng lý thuyết đồ

thị kết hợp với phương pháp đếm bằng hai cách.

Một ứng dụng bất ngờ của phương pháp đếm hai lần trong chứng minh

định lý Fermat nhỏ.

Định lý 2.1 (Định lý Fermat nhỏ, [5]). Nếu a là một số nguyên và p là

một số nguyên tố, khi đó

ap ≡ a (mod p).

Chứng minh. Xét tập các dãy có độ dài p dùng các kí hiệu chữ cái trong

bảng alphabet với a kí hiệu khác nhau. Chú ý rằng các dãy này có thể phân

chia làm hai lớp tương đương. Hai lớp được gọi là tương đương với nhau

nếu chúng luân phiên lẫn nhau. Đây là ví dụ các lớp tương đương (được gọi

là “chuỗi hạt”) với p = 5 :

{BBCCC, BCCCB, CCCBB, CCBBC, CBBCC}.

Ta gọi một dãy gồm ít nhất 2 kí hiệu khác nhau là dãy không tầm

thường. Tất cả sự luân phiên của một dãy không tầm thường là rời nhau -

vì p là nguyên tố, một dãy không thể chứa vài dãy con giống hệt nhau có

kích thước lớn hơn 1. Do đó tất cả các lớp tương đương có size p, ngoại trừ

các dãy tầm thường thì có size 1.

Vì vậy, có 2 cách để đếm số các dãy không tầm thường. Vì tổng có tất cả ap dãy, a dãy tầm thường nên ta có ap − a dãy không tầm thường. Do đó, số các dãy không tầm thường là p lần số các lớp tương đương không phải dạng tầm thường. Do đó p là ước của ap − a.

2.3 Vận dụng phương pháp đếm hai lần vào giải các bài

toán đếm

2.3.1 Đếm số tập con, số cặp và số hoán vị

Bài toán 2.1. Chứng minh rằng với mọi n, k là các số nguyên và 1 ≤ k ≤ n,

ta luôn có đẳng thức

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) n n − 1 n k = n = (n − k + 1) . k k − 1 k − 1

Chứng minh. Trước tiên ta sẽ chứng minh đẳng thức

(cid:32) (cid:33) (cid:32) (cid:33) n n − 1 k = n (2.2) k k − 1

(cid:33) (cid:32) n gợi ý cho chúng ta sử dụng quy Vế trái của đẳng thức (2.2) là tích k và k (cid:33) (cid:32) n tắc nhân. là số các tập con gồm k phần tử của tập X = {x1, x2, . . . , xn} k

và k là số cách chọn ra một phần tử từ một tập hợp có k phần tử. Do đó (cid:33) (cid:32) n sẽ cho chúng ta số N số các cặp (e, S) trong đó e ∈ S ⊆ X và tích k k (cid:32) (cid:33) n − 1 |S| = k. Để tính vế phải của (2.2), với mỗi phần tử e của X, ta có k − 1 (cid:32) (cid:33) n − 1 tập con có k phần tử của X chứa e. Do đó N = n . k − 1

Tiếp theo chúng ta chứng minh đẳng thức

(cid:32) (cid:33) (cid:32) (cid:33) n n . k = (n − k + 1) (2.3) k k − 1

Vế trái của (2.3) đã được tính ở trên, ta chỉ cần chỉ đếm vế phải của đẳng

thức. Nếu ta chọn trước k − 1 phần tử của S, sau đó chọn e từ n − k + 1 (cid:32) (cid:33) n phần tử còn lại để bổ sung vào S. Khi đó N = (n − k + 1) . Theo k − 1

nguyên lý đếm bằng hai cách, ta có điều phải chứng minh.

Bài toán 2.2. Chứng minh với mọi số tự nhiên n, ta có

n (cid:88)

i=0

(cid:32) (cid:33) n = 2n. i

Chứng minh. Ta nhận thấy vế phải của đẳng thức là số tập con của tập

X gồm n phần tử. Do vậy ta xét bài toán sau: đếm số tập con S của tập X = {x1, x2, . . . , xn}. Ta có, |S| = 2n. Để tính vế trái, đặt Sn là tập hợp (cid:32) (cid:33) n tập có 0 tất cả các tập con của tập X gồm n phần tử. Vì trong Sn có 0 (cid:32) (cid:32) (cid:33) (cid:33) n n phần tử, tập có 1 phần tử, . . ., tập có n phần tử. Do đó ta có 1 n

n (cid:88)

i=0

(cid:32) (cid:33) n . |Sn| = i

Chú ý 2.1. Từ kết quả số tập con của tập X gồm n phần tử bằng 2n, ta còn kí hiệu 2S là tập hợp tất cả các tập con của một tập hợp S bất kì.

Bài toán 2.3. Chứng minh rằng với mọi số tự nhiên n, ta có

n (cid:88)

i=0

(cid:33) (cid:32) n = 0. (−1)i i

(cid:32) (cid:33) Chứng minh. Trước hết, ta sẽ đếm số tập con có chẵn phần tử của tập có n n . Để có một tập con có chẵn phần phần tử. Số các tập con này là (cid:80)

2k tử của tập X gồm n, trước hết ta chọn ra n − 1 phần tử cố định và chọn

tiếp một tập con bất kỳ của n − 1 phần tử này. Nếu tập con đã chọn ra có

một số chẵn phần tử thì ta đã có một tập con có chẵn phần tử của tập X,

nếu tập con đã chọn có một số lẻ phần tử thì ta sẽ bổ sung thêm phần tử

còn lại của tập X vào tập con này. Khi đó ta cũng có một tập con có chẵn

phần tử của tập X.

Vì vậy số tập con có một số chẵn phần tử của X cũng bằng số tập con của tập có n − 1 phần tử và bằng 2n−1. Vì số tập con của X là 2n nên số

tập con có số chẵn phần tử của X bằng số tập con có số lẻ phần tử của X.

Từ đó suy ra điều phải chứng minh.

Nhận xét 2.3. Sự xuất hiện của (−1)i trong số hạng tổng quát của tổng khiến chúng ta nghĩ đến việc tách ra làm hai tổng nhỏ: một tổng với k chẵn,

một tổng với k lẻ. Nếu như đẳng thức ta cần chứng minh là đúng (và hiển

nhiên rằng nó đúng) thì ta sẽ suy ra rằng số các tập con có một số chẵn phần tử bằng một nửa số các tập con của tập có n phần tử và bằng 2n−1. Con số này lại chính bằng số tập con của tập có n − 1 phần tử, từ đó dẫn

đến cách chứng minh trên. Nếu suy nghĩ theo hướng chứng minh trực tiếp

số tập con có một số chẵn phần tử bằng số tập con có một số lẻ phần tử

thì sẽ tương đối khó khăn để thực hiện điều này.

Bài toán 2.4. Chứng minh rằng với mọi số nguyên dương n, ta có

(cid:98)n/2(cid:99) (cid:88)

i=0

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) n − i 2n n 2n−2i = . i n i

Chứng minh. Vế phải của đẳng thức cần chứng minh là số tập con có n

phần tử của tập X gồm 2n phần tử. Như vậy, ta sẽ đếm số tập con này

bằng cách phân hoạch tập X thành hai tập con A, B với |A| = |B| = n. Gọi các phần tử của A, B lần lượt là a1, a2, . . . , an; b1, b2, . . . , bn và ghép cặp (aj, bj), j = 1, n. Xét một tập con S của X với |S| = n. Ta gọi một phần tử của X là “tốt” nếu nó thuộc S. Dễ thấy rằng với một tập con S có n phần

tử của X, số các cặp (a, b) mà a, b cùng “tốt” bằng số các cặp (a, b) mà a, b

cùng không “tốt”. Đặt số cặp này là i. Rõ ràng 0 ≤ i ≤ (cid:98)n/2(cid:99). (cid:32) (cid:33) (cid:32) (cid:33) n − i n cách chọn ra i cặp “tốt” và i cặp không “tốt”. Còn Ta có i i

lại n − 2i cặp, ta sẽ chọn từ mỗi cặp một phần tử và đánh dấu phần tử đó

là “tốt”. Như vậy ta đã chọn được đủ n phần tử “tốt”. Mặt khác, dễ thấy

rằng mỗi cách chọn trên xác định duy nhất một tập con có n phần tử của

(cid:98)n/2(cid:99) (cid:88)

i=0

X. Vì vậy ta có (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) n − i 2n n = . 2n−2i i n i

Nhận xét 2.4. Điểm đặc biệt trong lời giải trên là ghép cặp các phần tử của X và sử dụng biểu thức 2n−2i để chọn ra đúng n − 2i phần tử thay vì một nhóm bất kỳ trong số n − 2i như công thức về số tập con quen thuộc.

n (cid:88)

Bài toán 2.5 (Vô địch Trung Quốc 1994, [1]). Chứng minh rằng

nC [(n−k)/2]

2n+1, ∀n ∈ Z+.

n−k

k=0

2kC k = C n

Chứng minh. Ta nhận thấy vế phải là số cách chọn n phần tử từ tập có 2n + 1 phần tử. Như vậy có C n 2n+1 cách chọn. Ta biến đổi vế trái để chọn được n phần tử từ 2n + 1 phần tử như sau:

Trước hết, từ 2n + 1 số, ta chia ra n cặp và số x.

2kC k (cid:21) cặp trong n − k cặp còn lại. Ngoài ra, số x sẽ Bước 1: Ta chọn ra k cặp rồi từ mỗi cặp chọn ra một số. Như vậy ta có n cách chọn. Bước 2: Chọn (cid:20)(n − k) 2

cách chọn và ta chọn được tổng cộng n số, trong đó k chạy từ 0 được chọn nếu n − k lẻ và không được chọn nếu n − k chẵn. Như vậy có C [(n−k)/2] n−k

nC [(n−k)/2]

n−k

n (cid:80) k=0

. Theo nguyên đến n. Như vậy vế trái ta có số cách chọn là 2kC k

n (cid:88)

lý đếm bằng hai cách ta suy ra

nC [(n−k)/2]

2n+1, ∀n ∈ Z+.

n−k

k=0

2kC k = C n

Định nghĩa 2.2. Cho số tự nhiên n ≥ 1. Một hoán vị của tập A =

{1, 2, . . . , n} được gọi là hoán vị bảo tồn a ∈ A nếu như phần tử a ở nguyên vị trí cũ của nó trong hoán vị mới. Kí hiệu Pn(k) là số hoán vị bảo tồn đúng k phần tử của A.

n (cid:80) k=0

Bài toán 2.6 (IMO 1987 (cid:93)1, [4]). Chứng minh rằng kPn(k) = n!,

với Pn(k) là số hoán vị bảo tồn đúng k phần tử của tập {1, 2, . . . , n}.

Chứng minh. Trước tiên, ta có thể nghĩ đến việc tìm Pn(k), sau đó nhân chúng với k rồi tính tổng chúng lên . . . có thể thu được kết quả như mong

muốn. Tuy nhiên, nếu chúng ta nhìn vào biểu thức, chúng ta sẽ đếm một

cách thông thường như sau. Vế trái là tổng số các điểm cố định trên tất

cả các hoán vị bảo tồn. Vế phải thu được nếu ta xét mỗi phần tử của tập

{1, 2, . . . , n} là một điểm cố định trong (n − 1)! hoán vị bảo tồn, do đó tổng

số hoán vị là n(n − 1)! = n!.

Bài toán trên cũng có lời giải khác nếu ta đếm số cặp (i, f ) trong đó f

bảo tồn đúng k vị trí và f (i) = i, (k = 1, 2, . . . , n). Gọi tập A = {1, 2, . . . , n}

là tập có n phần tử đã cho.

Trước tiên, để chứng minh đẳng thức trên ta cần có một kết quả bổ trợ sau:

(2.4) kPn(k) = nPn−1(k − 1).

Thật vậy, với mỗi k = 1, 2, . . . , n biểu thức (2.4) được đếm theo hai cách

Cách 1: Ta có số cách chọn i là k và số cách chọn f là Pn(k) nên số cặp (i, f ) là kPn(k).

Cách 2: Ta xét i là một phần tử cố định (tức là f (i) = i). Khi đó ta có một hoán vị bảo tồn k − 1 phần tử của tập A(cid:48) = A \ {i} và với mỗi hoán vị bảo tồn k − 1 phần tử của A(cid:48) ta bổ sung thêm i vào ta sẽ thu được một hoán vị bảo tồn k phần tử của tập A. Vì có n cách chọn i và Pn−1(k − 1) hoán vị bảo tồn k − 1 phần tử của tập A(cid:48) nên số cặp (i, f ) là nPn−1(k − 1).

Từ đó ta suy ra

kPn(k) = nPn−1(k − 1).

n (cid:88)

Theo (2.4), ta có

k=1

kPn(k) = n Pn−1(k − 1).

Mà Pn−1(0) + Pn−1(1) + · · · + Pn−1(n − 1) chính là số hoán vị của tập B gồm n − 1 phần tử mà trong đó hoán vị đó bảo tồn 0, 1, 2, . . . , n − 1 phần

n (cid:88)

tử, do đó tổng này chính bằng số hoán vị của tập B và bằng (n − 1)! Vậy

k=0

kPn(k) = n.(n − 1)! = n!.

m (cid:88)

m+n

k=0

Bài toán 2.7. Cho n, m ∈ N∗. Chứng minh rằng n (cid:88) = C 2 m+n 2nC m (−1)k.m.C k n 2k.(m + k)

bài toán trên là bài toán trong một tờ báo USA khá nổi tiếng và trở

thành một định lý. Mục đích đưa bài toán khó này ra đây là để người đọc

tiếp cận nó theo nhiều hướng đi khác nhau. Những hướng đi sau cũng chính

là nhứng hướng đi cho một bài toán đẳng thức tổ hợp nói chung.

Chứng minh. Đẳng thức đã cho tương đương với

m+n

n .m 22k.(m + 2k)

n.m 22k.(m + k)

n (cid:80) k=0

n (cid:80) k=0 4nC m

m+n

C 2k C k 2 − C k (−1)k.C k n.m 2k.(m + k) [ n 2 ] (cid:80) k=0 = = 2n 2n

n .m 22k.(m + 2k)

n.m 22k.(m + 2k)

C 2k C k

n (cid:80) k=0

[ n 2 ] (cid:80) k=0 = − . 2n−1 2n

Chúng ta cần kết quả của các bổ đề dưới đây.

Bổ đề 2.1. Với n, m ∈ N∗ ta có

n (cid:80) k=0

n (cid:88)

m+n

k=1

(cid:33) (cid:19)n (cid:32) mC k n 2k(m + k) 1 − = . 2n (cid:18)3 4 2k−1Cm+n−k 3kC m

Chứng minh. Giả sử rằng có m+n viên gạch được chia làm hai nhóm: nhóm

1 chứa m viên và nhóm 2 chứa n viên. Ta tiến hành tô m viên nhóm 1 sơn

mầu G. Với n viên gạch ở nhóm 2 tiến hành sơn bất kỳ mỗi viên mầu Y

hoặc B. Sau đó, với n viên nhóm này, tiến hành chọn ngẫu nhiên để sơn lại mầu R. Có tất cả 3n cách sơn mầu nhưng có 4n cách chọn mầu cho m + n viên gạch này. Ta dễ dàng chứng minh được xác suất chọn không có viên

B và 1 viên G là

n (cid:80) k=0

mC k n 2k(m + k) .

2n Gọi p2(n) là xác suất chọn ra một viên mầu G, ta dễ dàng chứng minh được

+ + p2(n) = p2(n−1) → p2(n) = 1− p2(n−1). m m + n n m + n 2 3 n m + n n m + n 2 3

Đặt q2(n) = 1 − p2(n) ta có

(cid:19) (cid:18) (cid:19) 1 − = + . q2(n) = p2(n − 1) q2(n − 1) n m + n (cid:18)1 3 2 3 n m + n 2 3

n (cid:88)

m+n−k

Từ q2(0) = 0 ta suy ra

m+n

k=1

m+n−k

. q2(n) = 2k−1C m 3kC m

n (cid:80) k=1

m+n

Xác suất chọn 1 viên G khi không có viên B là 1 − . 2k−1C m 3kC m

Do đó xác suất chọn không có viên B và 1 viên G là

n (cid:88)

m+n−k

m+n

k=1

(cid:33) (cid:19)n (cid:32) 1 − . (cid:18)3 4 2k−1C m 3kC m

Từ đó, suy ra

n (cid:80) k=0

n (cid:88)

m+n

k=1

(cid:33) (cid:19)n (cid:32) mC k n 2k(m + k) = 1 − . 2n (cid:18)3 4 2k−1Cm+n−k 3kC m

Cho n viên gạch, có 2n−1 cách chọn một số chẵn viên mầu B hoặc Y . Nếu có 2k viên có mầu B hoặc mầu Y thì xác suất không có viên mầu B

và chọn được một viên mầu G là . Cho k chạy thì ta thấy tổng m 22k(m + 2k)

xác suất không có viên mầu B và chọn được 1 viên màu G là

n .m 22k.(m + 2k)

C 2k

[ n 2 ] (cid:80) k=0 . 2n−1

Bổ đề 2.2. Với điều kiện không có ô mầu B và không chọn được ô màu G, (cid:19) xác suất chọn được một ô mầu R là 2 . (cid:18)1 + 3n−1 1 + 3n

Chứng minh. Gọi r(n) là xác suất có điều kiện thì n.r(n) đúng bằng số các

ô mầu đỏ. Ta có

2 ] [ n (cid:80) k=0

(n − 2k)2n−2kC 2k n

nr(n) =

2n−2kC 2k n [ n 2 ] (cid:80) k=0

2n−2kC 2k n−1 2n−2k−1C 2k n−1

= 2 = → r(n) = . 2an−1 an

2 ] [ n (cid:80) k=0 2 ] [ n (cid:80) k=0

2n−2kC 2k n 2n−2kC 2k n [ n−1 2 ] (cid:80) k=0 2 ] [ n (cid:80) k=0

2 ] [ n (cid:80) k=0

Với an = 2n−2kC 2k n .

AC B

A =

k ta có

A (cid:80) k=B

C k Sử dụng đẳng thức 2A−BC B

j = 2j−1. Do đó ta có

Bây giờ với j ≥ 1, C 2k [ n 2 ] (cid:80) k=0

n + 1

n (cid:80) j=0

n (cid:88)

2jC j

n + 1 =

n + 1 +

j=1

j=0

2j−1C j 2j−1C j = an = 2 1 2

(cid:19) . → r(n) = 2 → an = 3n + 1 2 (cid:18)1 + 3n−1 1 + 3n

Bổ đề 2.3. Với điều kiện số ô hoặc mầu B hoặc mầu Y là chẵn thì xác

suất không có ô mầu B và chọn ra được 1 ô mầu G là

n−1 (cid:88)

m+n

k=1

(cid:33) (cid:19) (cid:32) 3n + 1 − (3n−k − 1) . (cid:18) 1 4n 2k−1 C m m+n−k C m

Chứng minh.

[ n 2 ] (cid:80) k=0

1 22k C 2k 2n−1

+ r(n) .p1(n). Dễ dàng kiểm chứng được p1(n) = Đặt p1(n) là xác suất chọn ra 1 ô mầu G khi đã cho rằng không có ô nào mầu B. Tổng sác xuất để không có ô mầu B và chọn ra được 1 ô mầu G là 3n + 1 p1(n − 4n m m + n n m + n 1).

Đặt q1(n) = 1 − p1(n) từ đó áp dụng bổ đề 2.2 ta có

(cid:19) n + 2 p1(n) = m m + n (cid:18)1 + 3n−1 1 + 3n

p1(n − 1) (cid:19) n 0 = 1 − − p1(n) + p1(n − 1) n m + n

+ → q1(n) =

+ = n m + n n m + n (cid:18)3n−1 − 1 3n + 1 3n−1 − 1 3n + 1 m + n (cid:18)2 + 3n−12 1 + 3n m + n (cid:19) 2 + 3n−12 1 + 3n q1(n − 1) (cid:18)2 + 3n−12 n m + n (cid:19) 1 + 3n q1(n − 1)

n−1 (cid:88)

Ta có

m+n

k=1

· p1(1) = 1, q1(1) = 0 → q1(n) = 2k−1 C m m+n−k C m 3n−1 − 1 3n + 1

n−1 (cid:88)

m+n

k=1

(cid:33) (cid:19) (cid:19) (cid:32) 1 − · p1(n) = (cid:18)3n + 1 4n 3n−1 − 1 3n + 1

n−1 (cid:88)

m+n

k=1

(cid:33) (cid:18)3n + 1 4n (cid:19) (cid:32) (3n−k − 1) = 3n + 1 − (cid:18) 1 4n 2k−1 C m m+n−k C m 2k−1 C m m+n−k C m

Từ đó suy ra

n−1 (cid:88)

m+n

k=1

(cid:33) (cid:19) (cid:32) m.C 2k n 22k(m + 2k) [ n 2 ] (cid:80) k=0 = 3n + 1 − (3n−k − 1) . 2n−1 (cid:18) 1 4n 2k−1 C m m+n−k C m

Như vậy ta có

n (cid:80) k=0

(−1)km.C 2k n 2k(m + k) m.C 2k n 22k(m + 2k) m.C 2k n 2k(m + k) [ n 2 ] (cid:80) k=0 − = 2n 2n−1 2n

n−1 (cid:88)

(cid:33) (cid:19) (cid:32) 3n + 1 − (3n−k − 1) =

n (cid:88)

m+n−k

2k−1 C m m+n−k C m m+n (cid:33)

k=1 2k−1C m 3kC m

m+n−k

k=1

m+n−k

− 1 − (cid:18) 1 4n (cid:19)n (cid:32) (cid:18)3 4

n−1 (cid:80) k=1

n (cid:80) k=1

m+n

1 − (3n−k − 1) + 2k−1 C m m+n−k C m 2k−13n−kC m C m =

m+n −

m+n−k

n (cid:80) k=1

n−1 (cid:80) k=1

C m 2k−1C m 2k−13n−kC m 4n m+n−k(3n−k − 1) +

m+n

= 4nC m

m+n −

m+n−k + 2n−1

m+n−k

n−1 (cid:80) k=1

C m 2k−1C m C m 2k−1C m

n (cid:80) k=1 4nC m

m+n

= = 4nC m

m+n −

m+n−k−1

2kC m C m

n−1 (cid:80) k=1 4nC m

m+n

. =

n−1 (cid:88)

Bổ đề 2.4. Với m, n ∈ N∗ ta có

m+n−1−k =

m+n.

k=0

k=1

2k.C m C k

Chứng minh. Ta đếm số cách chọn, mỗi lần chọn ít nhất m + 1 số nguyên

m+n (cid:88)

n−1 (cid:88)

từ m + n số nguyên cho trước. Tổng số cách chọn là

m+n =

m+n.

k=m+1

k=0

C k C m+n−k C k

m+n (cid:88)

n−1 (cid:88)

Ta có

k−1 =

m+n−1−k =

m+n.

k=m+1

k=0

2m+n−kC m 2kC m C k

Do đó ta có

m+n −

m+n

n (cid:80) k=0

n−1 (cid:80) k=0 4nC m

n (cid:80) k=0 4nC m

m+n

C m C k C k (−1)km.C k n 2k(m + k) = = 2n

Từ đó, suy ra

m+n

n (cid:88)

C k

m (cid:80) k=0 2n.C m

m+n

k=0

= . (−1)kmC k m 2k(m + k)

Bài toán 2.8 (China Hong Kong MO 2007, [4]). Trong một trường học có

2007 nữ và 2007 nam. Mỗi sinh viên tham dự không quá 100 câu lạc bộ

trong trường học. Biết rằng hai sinh viên khác giới bất kỳ đều tham gia ít

nhất chung một câu lạc bộ. Chứng minh rằng tồn tại một câu lạc bộ mà có

ít nhất 11 nam và 11 nữ cùng tham gia.

Chứng minh. Thông tin duy nhất chúng ta được cung cấp là số thành viên

câu lạc bộ gồm cả nam và nữ, do đó chúng gợi ý chúng ta xét bộ ba (nam,

nữ, câu lạc bộ), trong đó nam và nữ cùng tham gia câu lạc bộ. Giả sử số

bộ ba này là T .

Với mỗi cặp (nam, nữ), theo giả thiết cùng tham gia ít nhất 1 câu lạc

bộ, do đó có 20072 cặp thỏa mãn,

T ≥ 20072.1.

Giả sử không có câu lạc bộ nào có ít nhất 11 nam và 11 nữ. Gọi X là số bộ

ba các câu lạc bộ nhiều nhất 10 nam và Y là số bộ ba câu lạc bộ nhiều nhất

10 nữ tham gia. Vì bất kỳ sinh viên nào tham dự được tối đa 100 câu lạc bộ

nên số cặp (nữ, câu lạc bộ) có nhiều nhất 2007.100, do đó X ≤ 2007.100.10.

Tương tự như vậy Y ≤ 2007.100.10. Do đó

20072 ≤ T ≤ X + Y ≤ 2.2007.1000 = 2007.2000

vô lý. Do đó tồn tại một câu lạc bộ với ít nhất 11 nam và 11 nữ tham

gia.

Bài toán 2.9 (IMO HK Prelim 2003). Có 15 sinh viên tham dự một khóa

học mùa hè. Mỗi ngày, 3 sinh viên chịu trách nhiệm vệ sinh lớp học sau khi

tan học. Sau khóa học này, người ta nhận thấy rằng mỗi cặp sinh viên có

trách nhiệm vệ sinh lớp học cùng nhau là đúng một lần. Hỏi khóa học này

kéo dài trong bao nhiêu ngày?

Chứng minh. Gọi số ngày khóa học kéo dài là k. Chúng ta đếm tổng số các

cặp sinh viên đã chịu trách nhiện vệ sinh lớp học cùng nhau trong k ngày.

Theo đề bài, mỗi cặp sinh viên này vệ sinh lớp học là đúng một lần nên nó bằng C 2 15.1 = 105. Mặt khác, từ việc 3 sinh viên cùng chịu trách nhiệm vệ sinh lớp học mỗi ngày, nên nó cũng bằng C 2 3 .k = 3k. Do đó, theo nguyên lý đếm hai lần, ta có 3k = 105 suy ra k = 35.

Bài toán 2.10 (IMO Shortlisted 2004). Có 10001 sinh viên ở một trường

đại học. Một số sinh viên cùng nhau tham gia để lập nên một số câu lạc

bộ (một sinh viên có thể thuộc các câu lạc bộ khác nhau). Một số câu lạc

bộ tham gia cùng nhau để lập nên một số đoàn thể (một câu lạc bộ có thể

thuộc nhiều đoàn thể khác nhau). Có tổng cộng k đoàn thể.Giả sử các điều

kiện sau được thỏa mãn

(i) Mỗi cặp sinh viên có đúng một câu lạc bộ.

(ii) Đối với mỗi sinh viên và mỗi đoàn thể thì sinh viên này thuộc đúng một

câu lạc bộ của đoàn thể này.

(iii) Mỗi câu lạc bộ có một số lẻ các sinh viên. Thêm vào đó, một câu lạc bộ

với 2m + 1 sinh viên (m là số nguyên dương) thuộc đúng m đoàn thể.

Tìm tất cả các giá trị có thể có của k?

Chứng minh. Một bộ ba có thứ tự (a, C, S) sẽ được gọi là chấp nhận được

nếu a là một sinh viên, C là một câu lạc bộ và S là một đoàn thể thỏa mãn

a ∈ C và C ∈ S. Ta sẽ đếm số bộ ba có thứ tự chấp nhận được theo hai

cách.

Cách 1: Đối với mỗi sinh viên a và đoàn thể S, theo (ii) có duy nhất

một câu lạc bộ C thỏa mãn (a, C, S) là chấp nhận được. Do đó có 10001k

bộ ba có thứ tự chấp nhận được.

Cách 2: Đối với mỗi câu lạc bộ C, gọi số thành viên trong câu lạc bộ là

đoàn thể. Vì thế có các bộ |C|. Theo (iii), C có đúng |C| − 1 2 |C|(|C| − 1) 2

bộ ba có thứ |C|(|C| − 1) 2 ba có thứ tự chấp nhận được với C có thể xem như các tọa độ thứ hai. Gọi Γ là tập tất cả các câu lạc bộ. Do đó ta có (cid:80) C∈Γ

tự có thể chấp nhận được. Theo (i), điều này bằng số các cặp sinh viên, là

10001 × 5000. Do đó,

C∈Γ

(cid:88) 10001k = = 10001 × 5000 |C|(|C| − 1) 2

Suy ra k = 5000.

Nhận xét 2.5. Khi chuyển sang ngôn ngữ toán học thì dù đề bài trông có

vẻ phức tạp nhưng khi đã xác định rõ hướng đi thì hiển nhiên, sự phức tạp

của đề chỉ là hình thức.

Bài toán 2.11 (IMO 2001). Có 21 học sinh nam và 21 học sinh nữa cùng

tham gia cuộc thi giải toán. Biết rằng:

(i) Mỗi thí sinh giải được nhiều nhất 6 bài toán.

(ii) Với bất kỳ một cặp học sinh khác giới, cả hai người sẽ giải được ít nhất

một bài toán chung.

Chứng minh rằng nếu tồn tại một bài toán sao cho có 3 học sinh nam và 3

học sinh nữ cùng giải được.

Chứng minh. Kí hiệu G là tập hợp học sinh nữ, B là tập hợp hoc sinh nam,

P là tập hợp các bài toán. Ngoài ra ta kí hiệu thêm:

P (g), P (b) lần lượt là tập các bài toán mà học sinh g ∈ G, b ∈ B làm

được.

G(p), B(p) lần lượt là tập các học sinh nam, nữ cùng giải được bài toán

p ∈ P.

Khi đó theo giả thiết đã cho ta suy ra

(i) |P (g)| ≤ 6, |P (b)| ≤ 6.

(ii) P (g) ∩ P (b) (cid:54)= ∅.

Ta cần chứng minh ∃p ∈ P : G(p) ≥ 3, B(p) ≥ 3. Ta sẽ đếm số các bộ

T = {(g, b, p)} sao cho p ∈ P (g) ∩ P (b) theo hai cách.

Cách 1: Từ (ii) nên ta có

g∈G

b∈B

(cid:88) (cid:88) |P (g) ∩ P (b)| ≥ |G|.|B| = 212. T =

Cách 2: Ta kí hiệu thêm

P− = {p ∈ P : |G(p)| ≤ 2}, P+ = {p ∈ P : |G(p)| ≥ 3}

|G(p)| ≥ |G|. Trước tiên ta sẽ chứng minh (cid:80) p∈P−

Lấy g ∈ G bất kì, khi đó từ (i) và (ii) ta suy r với mỗi bài toán p mà (cid:21) được giải bởi bởi ít nhất = 4 nam sinh thì theo nguyên lý Dirichlet g (cid:20)21 6

sẽ giải được bài toán p đó.

Với mỗi p ∈ P− thì hiển nhiên B(p) ≥ 4. Do đó tồn tại một nữ sinh giải

|G(p)| ≥ |G|.

|G(p)| ≥ |G| → được ít nhất một bài toán trong P−. Vì thế ta có (cid:80) p∈P− G(p) = (cid:80) g∈G Ngoài ra, ta có (cid:80) p∈P P (g) ≤ 6|G|. Do vậy (cid:80) p∈P

|G(p)| ≤ 5|G|. (cid:80) p∈P+

|B(p)| ≤ 5|B|. Chứng minh tương tự ta có (cid:80) p∈P+ |B(p)| ≥ |B| → (cid:80) p∈P−

Từ đó suy ra

p∈P

b∈B

g∈G (cid:88)

(cid:88) (cid:88) (cid:88) |T | = |P (g) ∩ P (b)| = |G(p)|.|B(p)|

p∈P−

p∈P+

(cid:88) → |T | = |G(p)|.|B(p)| + |G(p)|.|B(p)|

p∈P+

p∈P−

(cid:88) (cid:88) → |T | ≤ 2 |G(p)| + 2 |B(p)| ≤ 10|G| + 10|B|

→ |T | ≤ 20.21.

Hai kết quả ở hai cách là khác nhau nên điều giả sử là sai. Vậy tồn tại một

bài toán sao cho có 3 học sinh nam và 3 học sinh nữ cùng giải được.

|G(p)| ≥ |G| bằng cách dùng nguyên lý Dirichlet. Ứng dụng của bài Nhận xét 2.6. Bài toán này chỉ cần thêm điểm nhấn là bất đẳng thức (cid:80) p∈P−

toán đếm bằng hai cách không chỉ ở trong những bài toán quy về tập hợp

mà còn nằm ngay ở những bài toán hình học tổ hợp.

Bài toán 2.12 (Dự tuyển Olympic 30/4 năm 2007). Cho n điểm A1, A2, . . . , An trên cùng một mặt phẳng sao cho không có 3 điểm nào thẳng hàng, không có 4 điểm nào tạo thành hình bình hành. Gọi I2, I2, . . . , Im là tất cả các trung điểm của các đoạn tạo thành từ các đoạn AiAj (1 ≤ i < j ≤ n). Gọi N là tổng độ dài của mọi đoạn thẳng với hai đầu mút là Ai.Aj. M là tổng độ dài của mọi đoạn thẳng với hai đầu mút là Ii, Ij. Chứng minh rằng

· N (2.5) M ≤ n2 − 3n + 2 4

Nhận xét 2.7. Ta nhận thấy một tính chất rất quan trọng để giải bài toán này là với mỗi đoạn IiIj thì đoạn đó hoặc là đường trung bình của một tam giác hoặc là đường trung bình của một tứ giác1.

Chứng minh. Trước tiên ta sẽ chứng minh bài toán trên với 3 điểm cho trước

A, B, C. Gọi M, N, P, là trung điểm của các cạnh AB, BC, CA. Khi đó các

đường thẳng M N, N P, M P là đường trung bình của tam giác ABC. Ta có

M N + N P + M P = AC + AC + BC). (2.6) 1 2

Thỏa mãn công thức (2.5) với n = 3. Với 4 điểm cho trước A, B, C, D; gọi các

điểm M, N, P, Q, R, S lần lượt là trung điểm của AB, BC, CD, DA, AC, BD.

Ta có nhận xét sau:

P Q ≤ P K + KQ = (AB + CD). 1 2

Do đó

M N + P Q + RS ≤ (AB + BC + AD + CD + AC + BD). (2.7) 1 2

Thỏa mãn công thức (2.5) với n = 4.

Khi đó, với n điểm A1, A2, . . . , An ta thiết lập các tam giác và tứ giác; rồi lập ra mọi đẳng thức (2.6) và mọi bất đẳng thức (2.7) và cộng vế với vế

ta thu được bất đẳng thức mới gán tên là (∗). Bây giờ với bất đẳng thức

1Đường trung bình của một tứ giác là đoạn nối hai trung điểm của một tứ giác

(∗) ta xét các giá trị của hai về theo cách khác nhau.

n−2 tứ giác nên vế

Cách 1: Mỗi đoạn IiIj thuộc đúng một tam giác hoặc đúng một tứ giác nên vế trái của (∗) chính là M.

Cách 2: Mỗi đoạn IiIj thuộc vào n − 2 tam giác và C 2 phải của (∗) bằng

n−2)N =

(n − 2 + C 2 N. 1 2 n2 − 3n + 2 4

2.3.2 Phương pháp đếm hai lần và đồ thị hữu hạn

Như vậy theo nguyên lý đếm hai lần ta thu được M ≤ N. n2 − 3n + 2 4

Ví dụ 2.5 (Iran 2010 (cid:93)2, [4]). Giả sử có n điểm trên mặt phẳng sao cho

không có 3 điểm nào thẳng hàng. Chứng minh rằng số các tam giác mà các

(n2 − n). đỉnh được lấy từ n điểm và có diện tích bằng 1 không lớn hơn 2 3

Chứng minh. Giả sử số các tam giác thỏa mãn là k. Với mỗi cạnh được tạo

thành từ việc nối liền hai điểm trong tập chúng ta đếm số tam giác được

tạo thành bởi các cạnh đó. Gọi tổng số các cạnh là T . Mặt khác, với mỗi

cạnh AB có nhiều nhất 4 điểm sao cho các tam giác được tạo thành có cùng

diện tích. Do các điểm cách đều từ đường thẳng AB và không có ba điểm (cid:33) (cid:32) n nào thẳng hàng. Do vậy, T < 4 . Mặt khác, mỗi tam giác có 3 cạnh 2

nên T ≥ 3k. Do đó

(cid:32) (cid:33) n ≤ = (n2 − n). k ≤ T 3 4 3 2 3 2

Đây là một ví dụ thú vị để xét phương pháp đếm hai lần nếu bài toán

phát triển trên một cặp như số các học sinh và số các rằng buộc hay một

dãy các số hoặc các bài toán đồ thị thường gặp.

Sau đây là một số mẹo để thiết lập phương pháp đếm hai lần

1. Xét một cách đếm thông thường (như ví dụ trên, điều rõ ràng nhất là

chúng ta có thể tính tổng tất cả các điểm, các cạnh và các tam giác.

Trường hợp các cạnh dễ hơn các điểm vì chúng ta có thể dễ dàng giới

hạn số các tam giác hay các cạnh được phát triển từ chúng. Do đó chúng

ta có thể tính tổng các cạnh hoặc các tam giác được.)

2. Xét đếm cặp hoặc bộ ba các vật (như ví dụ 2.5 chúng ta đếm các cặp

cạnh)

3. Nếu giá trị mong muốn của bài toán chưa biết, cố tìm hai cách để tính

một số giá trị, trong đó một giá trị chưa biết, một giá trị có thể tính

được (xét ví dụ 2.5, chúng ta biểu diễn giá trị chưa biết k thông qua

T = 3k)

Bài toán 2.13 (IMO 1989 (cid:93) 3,[5]). Gọi n, k lần lượt là các số nguyên dương

và S là tập có n điểm trên mặt phẳng sao cho không có ba điểm nào của S

thẳng hàng. Với một điểm P bất kỳ của S có ít nhất k điểm cách đều điểm √ + 2n. P của S. Chứng minh rằng k < 1 2

Chứng minh. Bất đẳng thức cần chứng minh tương đương với

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

n cách.

Từ n và k là các số nguyên dương, bất đẳng thức này trương đương với n − 1 ≥ C 2 k. Bây giờ ta nối hai đỉnh bất kỳ của S bằng một cạnh và đếm số cạnh theo hai cách.

Cách 1: nối hai đỉnh bất kỳ của S ta có C 2 Cách 2: từ điểm bất kỳ của S có ít nhất k điểm cách đều nó. Do đó

nếu ta vẽ đường tròn với tâm xem như điểm này và khoảng cách giữa các điểm coi như bán kính thì có ít nhất C 2 k dây xem như cạnh. Tổng số các dây như thế, được đếm bội lần, ít nhất là nC 2 k. Hai đường tròn bất kỳ có

n dây (đối với

thể có nhiều nhất một dây chung và do đó có thể có tối đa C 2 mỗi cặp có thể có của đường tròn) được đếm hai lần.

n ≤ C 2

k − C 2

n. Bất đẳng này đơn giản thành n − 1 ≥ C 2 k.

Vì vậy, nC 2

Chúng ta xét các bài toán của lý thuyết đồ thị được giải quyết bằng phương

pháp đếm hai lần. Chủ yếu các bài toán được đề cập dưới đây áp dụng

nguyên lý Cayley.

Bài toán 2.14. Giả sử rằng đồ thị G = (V, E) có |V | = n và không chứa một chu trình độ dài 4 (kí hiệu C4). Tìm số cạnh lớn nhất có thể của G.

Chứng minh. Đặt d(u) là bậc của đỉnh u; S là tập các cạnh (u, {v, w}) trong

u∈V

đó u kề với v và w, v (cid:54)= w. Với mỗi đỉnh u của G, số các cặp như trên là (cid:32) (cid:33) d(u) . Vì vậy ta có 2 (cid:32) (cid:33) d(u) (cid:88) |S| = . 2

Mặt khác, với mỗi cặp {v, w} chỉ tồn tại nhiều nhất một đỉnh u ∈ V sao (cid:33) (cid:32) n . Do đó cho (u, {v, w}) ∈ S (vì G không chứa C4). Suy ra |S| ≤ 2

u∈V

(cid:32) (cid:33) (cid:32) (cid:33) d(u) n (cid:88) ≤ 2 2

Tương đương với

u∈V

(cid:88) (cid:88) d(u)2 ≤ n(n − 1) + d(u).

Áp dụng bất đẳng thức Cauchy-Schwarz, ta có

u∈V

(cid:33)2 (cid:32) (cid:88) (cid:88) (cid:88) n2(n − 1) + n d(u) ≥ n d(u)2 ≥ d(u) .

d(u) = 2|E|, ta có Chú ý rằng (cid:80) u∈V

n2(n − 1) + 2n|E| ≥ 4|E|2

hay

|E|2 − .|E| − ≤ 0 n 2 n2(n − 1) 4

Giải bất phương trình bậc 2 trên ta được √ |E| ≤ (cid:98) (1 + 4n − 3)(cid:99) n 4

Bài toán 2.15. Cho các số nguyên 0 ≤ k ≤ n. Chứng minh rằng

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) n k n − k = + k(n − k) + . 2 2 2

Chứng minh. Xét đồ thị đầy đủ Kn. Ta chọn ra từ k đỉnh tùy ý của Kn và xếp các cạnh của Kn vào ba nhóm:

(cid:32) (cid:33) k (i) cạnh của đồ thị con đầy đủ tạo từ k đỉnh đã chọn; 2

(cid:33) (cid:32) n − k cạnh của đồ thị con đầy đủ tạo thành từ n − k đỉnh còn lại; (ii) 2

(iii) k(n − k) cạnh nối giữa các đỉnh của 2 đồ thị con trên.

Rõ ràng rằng tất cả các cạnh của đồ thị ban đầu phải thuộc vào một và chỉ

một trong ba trường hợp trên. Vì vậy, tổng số các cạnh của ba nhóm trên

bằng số cạnh của đồ thị ban đầu hay ta có

(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) n − k n k = + k(n − k) + . 2 2 2

Bài toán 2.16 (Bổ đề Sperner). Cho một tam giác V1V2V3 được phân hoạch thành các tam giác nhỏ sao cho không có một đỉnh nào của các tam giác nhỏ

nằm trên cạnh một tam giác nhỏ khác (có thể nằm trên cạnh của tam giác ban đầu). Giả sử rằng các đỉnh được đánh số 1, 2, 3 sao cho Vi được đánh số i và chỉ hai số i, j được đánh số cho các đỉnh nằm trên cạnh ViVj(i, j = 1, 3, i (cid:54)= j). Chứng minh rằng tồn tại một tam giác nhỏ mà 3 đỉnh của nó

được đánh số bởi cả 3 số 1, 2, 3.

Chứng minh. Gọi tam giác nhỏ mà 3 đỉnh của nó được đánh số bởi cả 3 số

1, 2, 3 là tam giác “tốt”. Ta sẽ chứng minh một kết quả mạnh hơn: số các

tam giác “tốt” là một số lẻ.

Xét đồ thị đối ngẫu 2 G của các phân hoạch tam giác V1V2V3 nhưng không lấy tất cả các cạnh của nó. Hai đỉnh của G được nối với nhau bởi

một cạnh khi và chỉ khi hai miền mặt phẳng tương ứng với hai đỉnh đó có

cạnh chung mà hai đầu mút của nó được đánh số bởi 1 và 2. Dễ thấy rằng

với mỗi tam giác “tốt” thì bậc của đỉnh tương ứng với nó bằng 1 hoặc bậc

2 với các tam giác mà 3 đỉnh của nó được đánh số bởi một trong hai số 1, 2

và bậc bằng 0 đối với tam giác không có đồng thời hai đỉnh được đánh số

1, 2. Khi đó chỉ các tam giác “tốt” mới tương ứng với một đỉnh bậc lẻ. Mặt khác, trên cạnh V1V2 ta có một số lẻ các cạnh của các tam giác nhỏ có dạng 1 − 2 và vì các cạnh có dạng 1 − 2 chỉ xuất hiện trên cạnh V1V2 nên ta suy ra bậc của đỉnh tương ứng với phần mặt phẳng nằm ngoài tam giác

ban đầu có bậc lẻ.

Từ kết quả quen thuộc: số các đỉnh bậc lẻ của một đồ thị hữu hạn là

2.3.3 Phương pháp ma trận liên thuộc

một số chẵn, ta suy ra rằng số các tam giác “tốt” là một số lẻ.

Phương pháp ma trận liên thuộc giúp ta có thể dễ hình dung hơn về

cấu trúc của bài toán, từ đó đưa ra lời giải cho bài toán. Ta sẽ xét bài toán

2Đồ thị đối ngẫu của một đồ thị phẳng G là một đồ thị G(cid:48) trong đó mỗi đỉnh tương ứng với một miền

mặt phẳng của đồ thị G và các cạnh được nối giữa hai đỉnh tương ứng với hai miền kề nhau.

2.17 dưới đây và trình bày hai lời giải khác nhau của cùng một bài toán

giúp người đọc có thể dễ dàng so sánh ưu điểm của phương pháp ma trận

liên thuộc. Nội dung mục này được tham khảo chủ yếu trong tài liệu [6] và

một phần nhỏ trong tài liệu [4].

Bài toán 2.17 (IMO 1998, [4]). Trong một cuộc thi có a thí sinh và b giám

khảo, trong đó b ≥ 3 và là số nguyên lẻ. Mỗi giám khảo đánh giá “đạt” hoặc

“trượt”. Giả sử rằng với hai giám khảo bất kì, họ đánh giá giống nhau với

tối đa k thí sinh. Chứng minh rằng

≥ . k a b − 1 2b

Chứng minh. Trước tiên chúng ta sử dụng phương pháp ma trận liên thuộc

kết hợp với nguyên lý Fubini để giải bài toán.

Xét ma trận liên thuộc b × a với các hàng được đánh số theo các thí

sinh. Phần tử tương ứng của ma trận nhận giá trị bằng 1 nếu giám khảo

đánh giá thí sinh là “đạt” và nhận giá trị bằng 0 nếu ngược lại. Đặt T là

tập hợp các cặp số 0 hoặc 1 trong cùng một cột. Vì hai giám khảo đánh giá

giống nhau nhiều nhất k thí sinh nên với hai hàng bất kỳ, có nhiều nhất k

cặp thuộc T . Do đó (cid:32) (cid:33) b T ≤ k = . kb(b − 1) 2 2

(cid:33) (cid:32) (cid:33) Với mỗi cột trong ma trận, giả sử có p số 0 và q số 1. Khi đó sẽ có đúng (cid:32) p q cặp thuộc T . Mà p + q = b lẻ nên ta có bất đẳng thức sau + 2 2

(cid:32) (cid:33) (cid:32) (cid:33) p q + ≥ (b − 1)2 4 2 2

Vì có a cột nên ta có T ≥ . Vậy ta có a(b − 1)2 4

≤ |T | ≤ . a(b − 1)2 4 kb(b − 1) 2

Suy ra ≤ kb hay ≥ . a(b − 1) 2 k a b − 1 2b

Chú ý 2.2. Ta sẽ đưa ra lời giải khác cho bài toán 2.17 bằng cách xét các

bộ (x, y, i) trong đó i là một thí sinh và x, y là hai giám khảo đánh giá thí

sinh i giống nhau.

i − xi + y2 x2

i − yi

2 + C yi C xi

2 =

Với mỗi i, 1 ≤ i ≤ m giả sử có xi giám thị đánh giá đạt, yi giám thị đánh giá trượt. Mặt khác, số cặp giám thị có cùng đánh giá với một thí sinh là

≥ − xi + yi 2

= (cid:2)(b − 1)2 − 1(cid:3) . = (xi + yi)2/2 2 b b2 − 2 1 4 1 4

2 + C yi

2 là số nguyên có giá trị tối thiểu

Vì b lẻ và C xi . (b − 1)2 4

m (cid:88)

đa k thí sinh nên số cặp giám khảo có cùng đánh giá tối đa là kC b Mặt khác, b giám khảo và hai giám khảo bất kỳ đánh giá giống nhau tối 2. Do vậy

2 ≥

2 + C yi

2 ) ≥

i=1

kC b (C xi a(b − 1)2 4

Suy ra

≥ . k a b − 1 2b

Nhận xét 2.8. Qua hai cách giải của bài toán 2.17, ta nhận thấy rằng việc

giải bài toán bằng ma trận liên thuộc giúp chúng ta có thể dễ dàng hình

dung được cấu trúc bài toán, cũng kiến học sinh dễ đưa ra được định hướng

giải các bài toán tương tự.

Bài toán 2.18 (IMC 2002,[6]). Có 200 thí sinh tham gia một cuộc thi. Họ

được đề nghị giải 6 bài toán. Biết rằng mỗi bài toán được giải đúng bởi ít

nhất 120 thí sinh. Chứng minh rằng phải có 2 thí sinh mà với mỗi bài toán,

có ít nhất một trong hai thí sinh này giải được bài toán đó.

Chứng minh. Xét ma trận liên thuộc 6 × 200, trong đó mỗi hàng đại diện

cho một bài toán và mỗi cột đại diện cho một thí sinh tham gia cuộc thi.

Mỗi phần tử của ma trận nhận giá trị 1 nếu thí sinh tương ứng với cột

không giải được bài toán tương ứng với hàng và nhận giá trị 0 nếu ngược

lại. Ta có ví dụ ma trận minh họa dưới đây để dễ hình dung bài toán.

  Problem 1 0 1 0 . . . 0

Problem 2 1 1 0 . . . 0

Problem 3 0 0 0 . . . 1

Problem 4 0 1 1 . . . 1

Problem 5 1 0 1 . . . 1                     Problem 6 0 1 0 . . . 0

Đặt T là số các cặp các số 1 ở cùng một hàng. Chúng ta sẽ đếm số T bằng

hai cách.

Đếm theo các cột: Giả sử rằng với hai thí sinh bất kỳ, tồn tại một bài

toán mà cả 2 đều không giải được. Khi đó, với hai cột bất kỳ, có ít nhất

một cặp số 1 trong hai cột này nằm cũng một hàng. Như vậy chúng ta có (cid:33) (cid:32) 200 thể tìm số phần tử của T trong mỗi cặp của các cột. Mà ta có đúng 2

cặp các cột. Do đó (cid:33) (cid:32) 200 (2.8) = 19900. |T | ≥ 2

Đếm theo các hàng: Theo giả thiết, mỗi bài toán được giải bởi ít nhất

120 thí sinh. Điều này có nghĩa có tối đa 80 số 1 ở mỗi hàng và vì vậy có (cid:33) (cid:32) 80 cặp số 1 ở cùng hàng. Vì có 6 hàng nên suy ra nhiều nhất 2

(cid:32) (cid:33) 80 |T | ≤ 6 × = 18960. (2.9) 2

Từ (2.8) và (2.9) ta suy ra 19900 ≤ |T | ≤ 18960, vô lý. Do đó điều giả sử

ban đầu của chúng ta sai và bài toán được chứng minh.

Bài toán 2.19. Số Turan T (n, k, l); l ≤ k ≤ n là số nhỏ nhất các tập con

có l phần tử của X = {1, 2, . . . , n} sao cho với mọi tập con có k phần tử

của tập X đều chứa ít nhất một tập con trên. Chứng minh rằng với mọi số

nguyên dương l ≤ k ≤ n, ta có

(cid:32) (cid:33) n

l T (n, k, l) ≥ (cid:32) (cid:33) . k

Chứng minh. Đặt F là họ nhỏ nhất các tập con l phần tử của tập X đều chứa ít nhất một phần tử của F. Xét ma trận liên thuộc M = (mA,B) với các phần tử được đánh số theo các tập con A của F, các cột được đánh số theo các tập con k phần tử B của X và mA,B = 1 khi và chỉ khi A ⊆ B, trong các trường hợp khác mA,B = 0.

Đặt rA là số các số 1 trong hàng A và cB là số các số 1 trong cột B. Theo giải thiết thì cB ≥ 1 với mọi B. Mặt khác, rA là số các tập con k phần (cid:32) (cid:33) r − l với mọi A ∈ F. Vì vậy, tử chứa tập con l phần tử A. Suy ra rA = k − l

A∈F

B⊆[n]

theo nguyên lý Fubini, ta có (cid:33) (cid:32) (cid:32) (cid:33) n − l n (cid:88) (cid:88) F. = rA = cB ≥ k − l k

Do đó (cid:32) (cid:33) (cid:33) (cid:32) n n

l k T (n, k, l) = |F| ≥ (cid:33) = (cid:32) (cid:33) (cid:32) n − l k

k − l l

Bài toán 2.20 (IMO Shortlisted Problem 2003, [4]). Cho x1, x2, . . . , xn và y1, y2, . . . , yn là các số thực. Gọi A = {aij}1≤i,j≤n là ma trận với các hệ số

1,   nếu xi + yi ≥ 0; aij = 0,  nếu xi + yi < 0.

Giả sử B là ma trận cấp n × n với các hệ số là 0 và 1 sao cho tổng của các

phần tử trên mỗi hàng và mỗi cột của B tương ứng với tổng mỗi hàng, mỗi

cột của ma trận A. Chứng minh rằng A = B.

n (cid:88)

Chứng minh. Kí hiệu

i=1

j=1

S = (xi + yj)(aij − bij).

Ta có

n (cid:88)

i=1

j=1

i=1

(cid:32) n (cid:33) (cid:32) n (cid:33) (cid:88) (cid:88) S = + xi aij − bij yj aij − bij

= 0.

Vì tổng các phần tử của các hàng, các cột của A bằng tổng các phần tử của các hàng, các cột của B. Theo giả thiết về aij ta có

• Khi xi + yj ≥ 0, aij − bij = 1 − bij ≥ 0;

• Khi xi + yj < 0, aij − bij = −bij ≤ 0;

do đó, (xi + yj)(aij − bij) ≥ 0, ∀i, j. Vì S = 0 kéo theo (xi + yj)(aij − bij) = 0, ∀i, j. Suy ra aij = bij, ∀i, j.

Bài toán 2.21. [6] Trong một ủy ban nhất định, mỗi thành viên thuộc đúng

ba tiểu ban và mỗi tiểu ban có đúng ba thành viên. Chứng minh rằng tổng

số các thành viên bằng tổng số các tiểu ban.

Chứng minh. Xét ma trận liên thuộc cấp m × n, trong đó mỗi hàng biểu

diễn cho các thành viên và mỗi cột biểu diễn cho các tiểu ban. Mỗi phần tử

của ma trận nhận giá trị 1 nếu thành viên tương ứng với hàng thuộc tiểu

ban tương ứng với cột và nhận giá trị 0 nếu ngược lại. Vai trò của các hàng

và các cột có thể đổi chỗ cho nhau. Sau đây là hai ví dụ miêu tả bài toán

2.21 để chúng ta có thể dễ hình dung hơn.

  1 1 1 0 0 0 0 0 0   0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0

0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0

1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1

0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0

0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1

1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1                           0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0                                     0 0 1 1 0 0 0 1 0

Chúng ta sẽ đếm số các chữ số 1 theo hai cách. Theo giả thiết, mỗi hàng

chứa ba số 1, như vậy với m hàng chúng ta có tổng số 3m số 1. Mặt khác,

mỗi cột cũng chứa ba số 1 nên chúng ta có tổng cộng 3n số 1. Theo nguyên

lý đếm hai lần, chúng ta có 3m = 3n suy ra m = n.

Xuất phát từ ý tưởng trên, ta thu được các kết quả sau

r (cid:88)

c (cid:88)

Mệnh đề 2.1. [6] Nếu A = (ai,j) là ma trận cấp r × c với tổng của các hàng là Ri, i = 1, 2, . . . , r và tổng của các cột là Cj, j = 1, 2, . . . , c thì

i=1

j=1

Ri = Cj.

c (cid:88)

j=1

Mệnh đề 2.2. [6] Cho A = (ai,j) là ma trận (0, 1)3 cấp r × c với tổng các cột là Cj. Giả sử mỗi hai cột, tồn tại đúng t cột có chứa số 1 ở cả hai hàng, khi đó (cid:32) (cid:33) (cid:32) (cid:33) r = t . 2 Cj 2

Chứng minh. Đặt T là tập tất cả các cặp các số 1 không có thứ tự nằm

trên cùng một cột. Chúng ta sẽ đếm số phần tử của T theo hai cạch.

3ma trận có các phần tử chỉ là 0 và 1.

(cid:32) Đếm theo hàng: Với hai hàng bất kỳ, có đúng t cặp số 1 trong số các (cid:33) r cột thuộc tập T , do vậy |T | = t . 2

(cid:32) (cid:33)

cặp. Ta Đếm theo cột: Trong cột thứ j, có Cj số 1 và do đó có Cj 2 (cid:32) (cid:33)

c (cid:80) j=1

đếm tất cả các cột sẽ cho ta |T | = . Cj 2

Như vậy, theo nguyên lý đếm hai cách ta có

c (cid:88)

j=1

(cid:32) (cid:33) (cid:32) (cid:33) r t = . 2 Cj 2

Bài toán 2.22 (Iran 1999,[6]). Gọi C1, C2, . . . , Cn (n ≥ 2) lần lượt là bán kính của các hình tròn trong mặt phẳng sao cho không có hai trong số chúng

là tiếp tuyến và tập con của mặt phẳng được tạo bởi hợp các hình tròn kết

nối với nhau. Gọi S là tập các điểm thuộc ít nhất hai hình tròn. Chứng

minh rằng |S| ≥ n.

Chứng minh. Xét ma trận với n cột, mỗi cột đại diện duy nhất một hình

tròn và |S| hàng, mỗi hàng đại diện cho một giao điểm. Mỗi phần tử nhận

giá trị 1 tương ứng với điểm đó thuộc hình tròn tương ứng và nhận giá trị 0

nếu ngược lại. Vì không có hình tròn nào tách rời các hình còn lại nên mỗi

cột chứa ít nhất hai số 1 vì không có hai hình tròn nào tiếp xúc với nhau.

Theo giả sử ta cũng có mỗi cột cũng có ít nhất hai số 1.

Chúng ta sẽ tập trung vào các số 1 trong ma trận liên thuộc, đặt là ai,j = 1. Mỗi vị trí trên hàng i phân biệt với ai,j tương ứng với một hình tròn đi qua điểm được biểu thị ở hàng i. Hình tròn bất kỳ nào giao với hình tròn Cj tại đúng hai điểm thì không có tiếp tuyến. Như vậy chúng ta liên kết mỗi điểm trong hàng i khác với ai,j với một điểm từ cột j khác điểm ai,j đại diện cho giao điểm thứ hai. Chú ý rằng không một vị trí nào trên cột j liên kết với hai điểm 1 phân biệt trên hàng i, tứ là có ba hình tròn

khác nhau cùng đi qua hai điểm 1 khác nhau trên hàng i, mâu thuẫn. Vậy,

đây là một đơn ánh từ số 1 trên hàng i vào số 1 trên cột j.

 

1 →

↓

← 1                     ... 1 · · · 1 · · · ai,j = 1 · · · 1 · · · ... 1 ...

Chúng ta quay lại việc đếm các phần tử 1. Tuy nhiên, chúng ta gán một

“trọng lượng” cho mỗi phần tử 1. Như trong bài toán 2.22, trong ma trận

liên thuộc chúng ta có ba số 1 trên mỗi hàng, do đó chúng ta gán một trọng

lượng cho số 1. Khi đó, tổng của tất cả các trọng lượng trên các hàng là 1 3 r.

Sử dụng cùng ý tưởng trên, nếu chúng ta kết nối mỗi một với một trọng

lượng như cách chúng ta gán các trọng lượng cho mỗi số 1 trên mỗi hàng

tổng tới 1, sau đó lấy tổng các trọng lượng của tất cả các số 1 trong ma

trận bằng r. Để kết thúc chứng minh bài toán chúng ta xét các mệnh đề

sau đây.

Mệnh đề 2.3. [6] Cho A = (ai,j) là ma trận cấp r × c với tổng của các hàng là Ri và tổng các cột là Cj. Nếu Ri > 0 với 1 ≤ i ≤ r, khi đó

i,j

(cid:88) = r. ai,j Ri

Tương tự vậy, nếu Cj > 0 với 1 ≤ j ≤ c thì

i,j

(cid:88) = c. ai,j Cj

Chứng minh. Ta có

r (cid:88)

c (cid:88)

r (cid:88)

i=1

i,j

i=1

j=1

i=1

(cid:33) (cid:32) (cid:19) (cid:88) = = = 1 = r. ai,j Ri ai,j Ri 1 Ri (cid:18) 1 Ri

Chứng minh đẳng thức dưới hoàn toàn tương tự.

Mệnh đề 2.4. [6] Cho A = (ai,j) là ma trận (0, 1) cấp r×c với tổng các hàng là Ri và tổng các cột là Cj thỏa mãn Ri > 0, Cj > 0 với 1 ≤ i ≤ r, 1 ≤ j ≤ c. Nếu Cj > Ri bất cứ khi nào ai,j = 1 thì r ≥ c.

≥ . Do đó ≥ Chứng minh. Khi ai,j = 1, Ri ≤ Cj kéo theo 1 Ri 1 Cj ai,j Ri ai,j Cj

với mọi 1 ≤ i ≤ r, 1 ≤ j ≤ c. Theo mệnh đề 2.3 ta có

i,j

(cid:88) (cid:88) r = ≥ = c. ai,j Ri ai,j Cj

Quay trở lại chứng minh bài toán 2.22. Vì đây là đơn ánh từ số 1 trong hàng i vào số 1 trong cột j nên Cj ≥ Ri bất cứ khi nào ai,j = 1. Do đó r ≥ c hay |S| ≥ n.

Mở rộng thêm bài toán 2.22 trong trường hợp không thể so sánh Ri và Cj khi ai,j = 1 nhưng ta có thể so sánh hai giá trị này tại ai,j = 0. Mệnh đề dưới đây tương tự như mệnh đề 2.4.

Mệnh đề 2.5. [6] Cho A = (ai,j) là ma trận (0, 1) cấp r × c với tổng các hàng là Ri và tổng các cột là Cj. Nếu 0 < Ri < c và 0 < Cj < r với 1 ≤ i ≤ r, 1 ≤ j ≤ c và Cj > Ri tại bất cứ ai,j = 0 thì r ≥ c.

Chứng minh. Giả sử ngược lại, r < c. Khi đó 0 < r − Cj < c − Ri tại bất kỳ ai,j = 0. Do đó

< ⇒ < . 1 c − Ri 1 r − Cj Ri c − Ri Cj r − Cj

Kí hiệu M là số các số 1 trong ma trận A, ta có

r (cid:88)

i=1

(cid:33) (cid:32) c (cid:88) = M = (1 − ai,j) Ri = (c − Ri) Ri c − Ri

i=1 c (cid:88)

i=1 (1 − ai,j)Cj r − Cj

i,j

j=1

i=1

i,j c (cid:88)

Ri c − Ri (cid:33) (cid:32) r (cid:88) (cid:88) (cid:88) = < = (1 − ai,j) (1 − ai,j)Ri c − Ri Cj r − Cj

j=1

= M. = (r − Cj) Cj r − Cj

Mâu thuẫn. Do vậy giả sử ban đầu của ta sai, nghĩa là r ≥ c.

Bài toán 2.23. [6] Gọi S1, S2, . . . , Sm là các tập con rời nhau của {1, 2, . . . , n} thảo mãn |Si ∩ Sj| = 1 với mọi i (cid:54)= j. Chứng minh rằng m ≤ n.

Bài toán 2.23 là trường hợp đặc biệt của bất đẳng thức Fisher. Để chứng

minh bài toán này chúng ta có thể đơn giản sử dụng đại số tuyến tính. Tuy

nhiên chúng ta có thể áp dụng phương pháp đếm hai lần để giải bài toán

này.

Chứng minh. Hiển nhiên bài toán đúng với trường hợp m = 0 hoặc m = 1. Chúng ta giả sử m ≥ 2. Dễ thấy các tập Si khác rỗng. Nên giả thiết với m ≥ 2 và tất cả các tập khác rỗng.

Xét ma trận liên thuộc A cho họ tất cả các tập. m hàng của ma trận A

tương ứng với các tập và n cột của ma trận A tương ứng với các phần tử, trong đó ai,j bằng 1 nếu phần tử j thuộc tập Si và bằng 0 nếu ngược lại.

Chúng ta sẽ chỉ ra các giả thiết trong mệnh đề 2.5 được thỏa mãn. Nếu

bất kỳ hàng nào có tất cả các phần tử là 1, không mất tổng quát giả sử đó là hàng đầu tiên thì khi đó với giả thiết |Si ∩ Sj| = 1 với mọi i (cid:54)= j kéo theo |Si| = 1 suy ra m = 2 và n ≥ 2 bởi vì các tập rời nhau. Nếu bất kỳ cột nào có tất cả các phần tử 0 thì các phần tử đó không thuộc tập nào và chúng

ta có thể đơn giản xóa cột đó đi. Chúng ta thực hiện điều này đến khi mỗi cột có Cj ≥ 1 bởi vì kết quả trên thu được cho ma trận thu gọn, nó cũng có thể thỏa mãn với ma trận ban đầu A. Cuối cùng, nếu tất cả các cột đều là các số 1, không mất tổng quát giả sử đó là cột đầu tiên, thì |Si ∩ Sj| = 1 kéo theo không có cột nào chứa hai số 1. Như vây, nhiều nhất một hàng có

thể chứa toàn số 1 (trên cột đầu tiên) và mỗi hàng thứ r − 1 phải có hàng

thứ hai khác các cột. Do đó, số các cột phải lớn hơn hoặc bằng số các hàng,

hay m ≤ n. Khi đó các giả thiết của mệnh đề 2.5 đã được thỏa mãn.

 

1 →

↑

1 ←                     ... 1 · · · 1 · · · ai,j = 0 · · · 1 · · · ... 1 ...

Chúng ta xét với ai,j = 0. Theo giả thiết của bài toán, với mỗi một phần tử trên cột j đại diện cho một tập con giao với Ai. Vì chúng ta biểu diễn mỗi Cj với một phần tử trên hàng i sao cho các phần tử biểu diễn bởi Ri cũng thuộc tập con tương ứng bởi Cj. Chú ý rằng phép biểu diễn này là đơn ánh, vì có hai phần tử 1 trên Cj đồng thời biểu diễn cho cùng Ri kéo theo vài hai tập con giao nhau tại ít nhất hai phần tử. Ánh xạ đơn ánh suy

ra có ít nhất rất nhiều số 1 trên hàng thứ i cũng như nhiều số 1 trên cột

thứ j.

2.4 Một số bài toán đề nghị

Do đó, Ri ≥ Cj với mọi ai,j = 0 và theo mệnh đề 2.5 suy ra m ≤ n.

Bài toán 2.24 (Iran 2010 (cid:93) 6,[5]). Một trường có n sinh viên, mỗi sinh viên

có thể tham dự bất kỳ lớp học nào. Mỗi lớp học có ít nhất 2 sinh viên. Biết

rằng nếu có 2 lớp học cùng có ít nhất chung 2 sinh viên thì số sinh viên của

hai lớp học đó khác nhau. Chứng minh rằng số các lớp học không lớn hơn (n − 1)2.

Bài toán 2.25 (MOP pratice test 2007,[5]). Trong một bảng n × n, mỗi

phần tử từ tập {1, 2, . . . , n} xuất hiện đúng n lần. Chứng minh rằng có một √ cột hoặc một hàng với ít nhất n số khác nhau.

Bài toán 2.26 (China 1993). Có một nhóm 10 học sinh vào trong một hiệu

sách. Biết rằng

(i) Mỗi người mua đúng 3 quyển sách;

(ii) Với mỗi cặp học sinh, có ít nhất một quyển sách được chọn mua giống

nhau.

Có ít nhất bao nhiêu người mua quyển sách được chọn bỏi nhiều người nhất?

Bài toán 2.27 (China 1996). Tám ca sĩ cùng luyện tập biểu diễn trong lễ

hội văn hóa trong đó có m ca khúc được trình bày. Mỗi ca khúc được trình

bày bởi 4 ca sĩ và mỗi cặp ca sĩ cùng nhau biểu diễn cùng số bài. Tìm số m

nhỏ nhất có thể có.

Kết luận

Với mục tiêu tích lũy thêm các kiến thức và các phương pháp giải bài

toán đếm, luận văn đã tập trung vào tìm hiểu "Phương pháp đếm hai lần"

và ứng dụng của nó vào giải một số bài toán đếm trong các đề thi học sinh

giỏi làm hướng nghiên cứu của luận văn.

Luận văn đã hoàn thành nhiệm vụ:

1. Đọc bài báo “double counting” của nhóm tác giả Law Ka Ho, Leung Tat

Wing và Li Kim Jin được đăng tải trên tạp chí Mathematical Excalibur

(Volume 13, Number 4, 2008) để tìm hiểu cơ sở toán học của phương

pháp “Đếm hai lần” và ý tưởng của phương pháp “Đếm hai lần” để tìm

lời giải cho bài toán tổ hợp.

2. Đọc và nghiên cứu các bài toán được nhắc đến trong MOP 2007 Black

Group về “Đếm hai lần” của tác giả Yufei Zhao và ý tưởng giải cho các

bài toán giải bằng phương pháp ma trận liên thuộc.

3. Sưu tầm một số bài toán tổ hợp dành cho học sinh khá, giỏi.

Luận văn đã thu được các kết quả cơ bản sau:

1. Trình bày ý tưởng về phương pháp đếm 2 lần trong giải toán tổ hợp.

2. Trình bày việc vận dụng phương pháp “Đếm hai lần” để đưa ra lời giải

cho một số bài toán.

3. Đối với một số bài toán, luận văn cũng đã cố gắng để đưa ra các cách

giải khác nhau của cùng một bài toán đếm và so sánh những phương

pháp giải đó với việc vận dụng phương pháp đếm hai lần để có những

nhận xét thú vị.

Hướng nghiên cứu của luận văn là mở và kết quả nội dung luận văn là tư

liệu cho bản thân trong việc giảng dạy ở Trường trung học phổ thông.

Tài liệu tham khảo

Tiếng Việt

[1] Nguyễn Văn Mậu, Trần Nam Dũng, Vũ Đình Hòa, Đặng Huy Ruận,

Đặng Hùng Thắng (2008), Chuyên đề chọn lọc về tổ hợp và toán rời

rạc, Nhà xuất bản giáo dục.

[2] Nguyễn Văn Thông (2012), Bồi dưỡng học sinh giỏi Toán tổ hợp - rời

rạc, Nhà xuất bản Đại học quốc gia Hà Nội.

[3] Vũ Dương Thụy, Nguyễn Văn Nho (2002), 40 năm Olimpic Toán học

Tiếng Anh

quốc tế (1959-2000), NXB Giáo dục.

[4] Law Ka Ho, Leung Tat Wing and Li Kim Jin (2008), Double counting,

Mathematical Excalibur (Volume 13, Number 4).

[5] Victoria Krakovna (2010), Double counting, IMO Training 2010:

http://euclid.ucc.ie/mathenr/IMOTraining/2010.

[6] Yufei Zhao (2007), Counting in Two Ways Incidence Matrices, MOP

2007 Black Group, 26 June.

Luận văn Thạc sĩ Toán học: Phương pháp đếm hai lần và ứng dụng

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

TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- ĐỖ THỊ THÚY HÒA

PHƢƠNG PHÁP ĐẾM HAI LẦN VÀ ỨNG DỤNG

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

THÁI NGUYÊN - 2019

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

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

ĐỖ THỊ THÚY HÒA

PHƢƠNG PHÁP ĐẾM HAI LẦN VÀ ỨNG DỤNG

Chuyên ngành: Phƣơng pháp Toán sơ cấp

Mã số: 8 46 01 13

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

NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. Trịnh Thanh Hải

THÁI NGUYÊN - 2019

Mục lục

Mở đầu

Chương 1

Kiến thức chuẩn bị

Chương 2

Vận dụng phương pháp đếm hai lần vào giải bài toán đếm

Kết luận

Tài liệu tham khảo

Có thể bạn quan tâm

Tài liêu mới

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

TikTok