1

B GIO DC V O TO
TRNG I HC VINH

NGUYN TH XUN HUY

V BI TON RI RC V I S T HP

Luận văn thạc sĩ toán học

NGHệ AN 2012

B GIO DC V O TO
TRNG I HC VINH

NGUYN TH XUN HUY


2

V BI TON RI RC V I S T HP
CHUYấN NGNH: I S V Lí THUYT S

Mó s: 60 46 05
Luận văn thạc sĩ toán học

Ngi hng dn khoa hc
PGS.TS. NGUYN THNH QUANG

NGHệ AN - 2012

Tổ hợp là một ngành toán học rời rạc nghiên cứu về các cấu hình kết hợp
các phần tử của một tập hữu hạn phần tử. Các cấu hình đó là những phép liệt kê,
hoán vị, chỉnh hợp, tổ hợp các phần tử của một tập hợp. Tổ hợp có liên quan đến
nhiều lĩnh vực khác nhau của toán học, như đại số, lý thuyết xác suất, lý thuyết
ergod (ergodic theory) và hình học, cũng như các ngành ứng dụng như khoa học
máy tính và vật lí thống kê.
Các bài toán tổ hợp cơ bản bao gồm: Bài toán rời rạc và đại số tổ hợp; Bài
toán tô màu; Bài toán trò chơi; Bài toán đồ thị.
Với những lý do như đã trình bày ở trên, chúng tôi lựa chọn đề tài luận
văn này là “Về bài toán rời rạc và đại số tổ hợp” nhằm đi sâu tìm hiểu một
trong năm bài toán cơ bản của Tổ hợp. Tài liệu tham khảo chủ yếu của luận văn
là các tài liệu: [1], [2], [6].


4
Ngoài ra, luận văn còn xây dựng một hệ thống bài tập và ví dụ về các bài
toán rời rạc và đại số tổ hợp nhằm góp phần xây dựng một tài liệu tham khảo cho
các giáo viên, học sinh ở nhà trường phổ thông và sinh viên ngành sư phạm toán
học. Các ví dụ, bài tập minh họa trong luận văn chủ yếu là các bài toán sưu tầm
từ các đề thi vô địch toán quốc tế (IMO) hoặc các đề thi học sinh giỏi quốc gia
thuộc phần tổ hợp.
Tác giả xin trân trọng cảm ơn thầy giáo hướng dẫn khoa học - PGS.TS.
Nguyễn Thành Quang - đã tận tình hướng dẫn, chỉ bảo, giúp đỡ để tác giả hoàn
thành luận văn.
Tác giả xin cảm ơn các thầy cô giáo trong chuyên ngành Đại số và Lý thuyết
số, khoa Toán học, phòng Đào tạo Sau đại học của Trường Đại học Vinh đã giảng
dạy và tổ chức hướng dẫn cho chúng tôi trong học tập và nghiên cứu.
Tác giả xin cảm ơn Trường Đại học Đồng Tháp đã giúp đỡ, tạo điều kiện
thuận lợi cho mỗi học viên chúng tôi trong học tập và nghiên cứu của chương trình
đào tạo sau đại học.

n3: = 30;
k: = 0;
for i1: = 1 to n1 do k: = k + 1;
for i2: = 1 to n2 do k: = k + 1;
for i3: = 1 to n3 do k: = k + 1;
Giải. Đầu tiên giá trị của k được gán bằng 0. Có 3 vòng lặp for độc lập. Sau mỗi
lần lặp của mỗi một trong 3 vòng for, giá trị k tăng lên 1. Vòng for thứ nhất lặp
10 lần, vòng for thứ hai lặp 20 lần, vòng for thứ ba lặp 30 lần. Vậy, kết thúc 3
vòng lặp for giá trị của k sẽ là 10 + 20 + 30 = 60.



1.1.2. Nguyên lý bù trừ. Nếu không có giả thiết gì về sự rời nhau giữa hai tập
hợp A và B thì ta có


6
N ( A ∪ B ) = N ( A) + N ( B ) − N ( A ∩ B ).

Công thức trên được mở rộng cho nhiều tập hợp như sau: Nếu A 1, A2, …, Am là
các tập hữu hạn, thì
N ( A1 ∪ A2 ∪L ∪ Am ) = N1 − N 2 + L + (−1) m −1 N m

trong đó Nk là tổng số các phần tử của tất cả các giao của k tập lấy từ m tập đã
cho nghĩa là N1 = N(A1) + … + N(Am), Nm = N(A1 ∩ A2 ∩ … ∩ Am).
Ví dụ: Hỏi trong tập X = {1, 2, 3, …, 10000} có bao nhiêu số không chia hết
cho bất cứ số nào trong các số 3, 4, 7?
Giải. Gọi Ai = {x∈ X : x chia hết cho i}, i = 3, 4, 7.
Khi đó A3 ∪ A4 ∪ A7 là tập hợp các số trong X chia hết cho ít nhất một trong 3 số
3, 4, 7:

vòng for thứ hai lặp 20 lần, vòng for thứ ba lặp 30 lần. Vậy, theo nguyên lý
nhân, kết thúc 3 vòng lặp for lồng nhau, giá trị của k sẽ là 10 x 20 x 30 = 6000 
1.1.4. Chỉnh hợp lặp. Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ
tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần có thể được lặp lại.
Như thế, một chỉnh hợp lặp chập k của n có thể xem như một phần tử của tích
Đêcac Ak với A là tập đã cho.
Theo nguyên lý nhân, số tất cả các chỉnh hợp lặp chập k của n sẽ là nk.
1.1.5. Chỉnh hợp không lặp. Một chỉnh hợp không lặp chập k của n phần tử là
một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho, trong đó các thành
phần không được lặp lại.
Theo nguyên lý nhân, số chỉnh hợp không lặp chập k của n sẽ là
n(n - 1)…(n – k + 1).
Để tồn tại cấu hình, cần phải thỏa mãn k ≤ n.
1.1.6. Hoán vị. Ta gọi một hoán vị của n phần tử là một cách sắp xếp thứ tự các
phần tử đó. Một hoán vị của n phần tử được xem như một trường hợp riêng của
chỉnh hợp không lặp khi k = n. Do đó số hoán vị của n phần tử là 1.2…n= n!
1.1.7. Tổ hợp. Một tổ hợp chập k của n phần tử là một bộ không kể thứ tự gồm
k thành phần khác nhau lấy từ n phần tử đã cho. Nói cách khác, một tổ hợp chập
k của n phần tử là một tập con k phần tử của tập n phần tử đã cho.


8
k
k
Kí hiệu Cn là số tất cả các tổ hợp chập k của n phần tử và mỗi Cn được

gọi là một hệ số tổ hợp.
Ví dụ. Hỏi có bao nhiêu giao điểm của các đường chéo của một đa giác lồi n
(n ≥ 4) đỉnh nằm ở trong đa giác, nếu biết rằng không có 3 đường chéo nào đồng



d) Công thức đệ qui

Cnk = Cnk−−11 + Cnk−1 , n > k > 0

(4)

e) Khai triển nhị thức Newton

( x + y ) n = Cn0 x n + Cn1 x n −1 y + ... + Cnn −1 xy n −1 + Cnn y n

(5)

n

= ∑ Cnk x n − k y k .
k =0

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


9
1.2.1. Bài toán đếm tổ hợp. Một trong những vấn đề đầu tiên của việc nghiên
cứu tổ hợp là đếm xem có bao nhiêu cấu hình tổ hợp có thể được tạo ra với
những quy tắc đã nêu? Những bài toán như vậy gọi là bài toán đếm tổ hợp.
Ví dụ. Cho một lưới gồm các ô vuông. Các nút được đánh số từ 0 đến n theo
chiều từ trái sang phải và từ 0 đến m theo chiều từ dưới lên trên (hình vẽ). Hỏi
có bao nhiêu đường đi khác nhau từ nút (0,0) đến nút (n,m) nếu chỉ cho phép đi
trên cạnh các ô vuông theo chiều sang phải hoặc lên trên?
(0,m)


N k = Cnk (n − k )! =

n!
k!

và
1 1
(−1) n
)
N = n !(1 − + − ... +
1! 2!
n!

Từ đó xác suất cần tìm là
1 1
(−1) n
1 − + − ... +
1! 2!
n!

Một điều lý thú là xác suất này dần đến e −1 (nghĩa là còn lớn hơn 1/3) khi n khá
lớn. Số N trong bài toán trên được gọi là số mất thứ tự và được ký hiệu là Dn .
Dưới đây là một vài giá trị của Dn , cho ta thấy Dn tăng rất nhanh so với n:

n

Dn

2 3 4 5

bà (ông i là chồng bà i), sau đó đánh số các ghế trống theo nguyên tắc: ghế số i
nằm giữa bà i và bà i + 1 (để tiện trình bày, các phép cộng chỉ số trong phần này
đều được hiểu là thực hiện vòng tròn, nghĩa là n + 1 = 1). Mỗi cách xếp các ông
được biểu diễn bằng một phép thế ϕ trên tập {1, 2, 3, …, n} với quy ước
ϕ (i ) = j có nghĩa là ghế i được xếp cho ông j. Phép thế ϕ phải thỏa mãn

ϕ (i ) ≠ i và ϕ (i ) ≠ i + 1

(*).

Như vậy Un là số tất cả các phép thế ϕ thỏa mãn điều kiện (*).
Ta gọi Un là số phân bố.
Xét tập hợp tất cả các phép thế ϕ của {1, 2, 3, …, n}. Trên tập này, gọi P i
là tính chất ϕ (i) = i và Qi là tính chất ϕ (i) = i +1. Đặt Pn+i = Qi và ta được, theo
nguyên lý bù trừ (tương ứng với 2n tính chất Pi):
Un = N = n! – N1 + N2 – …
trong đó Nk là tổng số tất cả các phép thế thỏa mãn k tính chất lấy từ 2n tính chất
đang xét.
Chú ý rằng, không thể xảy ra đồng thời thỏa mãn P i và Qi hoặc đồng thời
thỏa mãn Pi+1 và Qi, do đó trong các cách lấy ra k tính chất từ 2n tính chất đang
xét, cần thêm vào điều kiện: các Pi và Qi hoặc Pi+1 và Qi không được đồng thời có
mặt. Gọi số các cách này là g(2n, k) (với g(2n, k) = 0 khi k > n). Với mỗi cách
lấy ra k tính chất như vậy (k ≤ n), ta có (n - k)! phép thế thỏa mãn chúng. Từ đó
nhận được Nk = g(2n, k).(n - k)! và
U n = n !− g (2n,1).( n − 1)!+ g (2n, 2).( n − 2)!− ... + ( −1) n g (2 n, n).

Bây giờ còn phải tính các hệ số g(2n, k), k = 1, 2, …, n.
Xếp 2n tính chất đang xét trên một vòng tròn theo thứ tự
P1 , Q1 , P2 , Q2 , …, Pn , Qn
ta thấy rằng g(2n, k) chính là số cách lấy ra k phần tử trong 2n phần tử xếp thành

Dn = (n - 1)(Dn-2 + Dn-1)
Suy ra Dn – nDn-1= -(Dn-1- (n-1)Dn-2).


13
Đặt Vn = Dn – nDn-1, ta có
Dn – nDn-1= Vn = - Vn-1= … = (-1)n-1V1= (-1)n
Hay
Dn
D
(−1) n
− n −1 =
n ! (n − 1)!
n!

Cộng các hệ thức trên, với n = 1, 2, … ta được
Dn
1 1
( −1) n
= 1 − + − ... +
n!
1! 2!
n!
1 1
(−1) n
) .
và nhận lại công thức đã biết: Dn = n !( 1 − + − ... +
1! 2!

n!

nhiều tham số.
1.2.3. Định lý (Giải công thức truy hồi tuyến tính thuần nhất hệ số hằng). Cho
c1, c2 là các hằng số thực. Giả sử phương trình r 2 - c1r - c2 = 0 có hai nghiệm
phân biệt r1 và r2. Khi đó dãy số {an} là nghiệm của công thức truy hồi
an = c1an-1 + c2an-2
khi và chỉ khi

(*)

an = α1r1n + α 2 r2n
n= 0, 1, … trong đó α1 , α 2 là các hằng số
Chứng minh. Trước hết ta chứng minh rằng nếu r1 và r2 là 2 nghiệm phân biệt
của 2 phương trình đặc trưng, và là các hằng số, thì dãy số {an} xác định bởi
công thức (*) là nghiệm của công thức truy hồi đã cho.
Thật vậy, do r1 và r2 là nghiệm đặc trưng nên
r12 = c1r1 + c2 ,

r22 = c1r2 + c2

Từ đó suy ra

c1an −1 + c2 an− 2 = c1 (α1r1n −1 + α 2 r2n −1 ) + c2 (α1r1n − 2 + α 2 r2n − 2 )

= α1r1n − 2 (c1r1 + c2 ) + α 2 r2n − 2 (c1r2 + c2 )
= α1r1n − 2 r12 + α 2 r2n −2 r22

= α1r1n + α 2 r2n
= an



Tìm công thức hiện cho Fn.
Giải. Giải phương trình đặc trưng:

r 2 − r −1 = 0
Ta thu được 2 nghiệm
r1 =

1+ 5
1− 5
, r2 =
.
2
2

Do đó, công thức hiện có dạng
Fn = α1.(r1 ) n + α 2 .(r2 ) n


16
trong đó α1 , α 2 là các hằng số cần xác định từ các giá trị ban đầu F0, F1. Từ công
thức (***), ta có
α1 =

1 1+ 5
,
5 2

α2 = −

n +1

an = α1r0n + α 2 nr0n

n = 0, 1, …, trong đó α1 , α 2 là các hằng số
Ví dụ. Tìm nghiệm cho công thức truy hồi a n = 6an - 1 - 9an – 2 với điều kiện ban
đầu a0 = 1 và a1 = 6
Giải: Phương trình đặc trưng r 2 − 6r + 9 = 0 có nghiệm kép r = 3. Do đó,
nghiệm của hệ thức có dạng:
an = α1 3n + α 2 n3n

Để tìm α1 , α 2 sử dụng điều kiện đầu ta có
a0 = 1 = α1
a1= 6 = α1.3 + α 2 .3
Giải hệ này ta tìm được α1 = 1 và α 2 = 1. Từ đó nghiệm của hệ thức đã cho là:
an = 3n + n3n .
1.2.5. Định lý. Cho c1, c2, …, cn là các số thực. Giả sử phương trình đặc trưng

r k − c1r k −1 − c2 r k − 2 − L − ck = 0


17
có k nghiệm phân biệt r1 , r2 ,..., rk . Khi đó dãy số {an} là nghiệm của hệ thức
an = c1an −1 + c2 an − 2 + ... + ck an − k
khi và chỉ khi

an = α1r1n + α 2 r2n + ... + α k rkn
với n = 0, 1, 2, …, trong đó α1 , α 2 ,..., α k là các hằng số
Ví dụ. Tìm nghiệm của hệ thức an = 6an −1 − 11an− 2 + 6an −3 với điều kiện đầu
a0 = 2, a1 = 5, a2 = 15.
Giải: Phương trình đặc trưng:


Ví dụ. Có bao nhiêu cách chọn ra n quả từ 4 loại quả: táo, chuối, cam, đào (mỗi
loại đều có số ít ra là n) mà trong đó có một số chẵn quả táo, số lẻ quả chuối,
không quá 4 quả cam và ít ra 2 quả đào?
Giải: Hàm sinh để giải bài toán này là
(1 + x 2 + x 4 + x6 + ...)( x 3 + x5 + x 7 + ...)(1 + x + x 2 + x 3 + x 4 )( x 2 + x3 + x 4 + ...)
Trong công thức trên có 4 thừa số để đếm số quả táo (các số mũ chẵn), chuối
(các số mũ lẻ), cam (chỉ có đến số mũ 4) và đào (số mũ bắt đầu từ 2). Hàm sinh
sẽ là
g ( x) = 1/(1 − x 2 )   x /(1 − x 2 )  (1 − x 5 ) /(1 − x)   x 2 /(1 − x)  =  x 3 (1 − x5 )  /  (1 − x 2 ) 2 (1 − x ) 2 

Do đó, số cách cần đếm là hệ số thứ n trong khai triển g(x) dưới dạng
chuỗi lũy thừa. Tuy là chúng không có câu trả lời bằng số, nhưng hàm xây dựng
được chứa dữ liệu để có thể lập trình trên máy tính đưa ra bảng đáp số cho các
giá trị của n mà ta mong muốn.

1.2.7. Phương pháp liệt kê
Ví dụ
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
là một hình chữ nhật Latinh chuẩn trên tập S = { 1, 2,3, 4,5, 6, 7} .
Gọi L(p,n) là số hình chữ nhật Latinh p × n , còn K(p,n) là số hình chữ nhật
la tinh chuẩn p × n . Ta có
L(p, n) = n! K(p, n)
Dễ dàng thấy rằng, số mất thứ tự Dn là số các hình chữ nhật la tinh chuẩn 2 × n ,
còn số phân bố Un là số các hình chữ nhật la tinh chuẩn 3 × n , với 2 dòng đầu là
1

2


hoán vị 1 2 … n. Ví dụ một hình vuông Latinh chuẩn cấp 7
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
4 5 6 7 1 2 3
5 6 7 1 2 3 4
6 7 1 2 3 4 5
7 1 2 3 4 5 6
Gọi ln là số hình vuông Latinh như thế, ta có

L(n, n) = n !(n − 1)!ln .
Việc tìm một công thức cho ln đến nay còn để ngỏ. Những công thức tính K(p, n)
cho thấy rằng điều này không phải đơn giản. Tuy nhiên ta có thể lập một chương
trình cho máy tính, liệt kê tất cả các hình vuông Latinh chuẩn cấp n. Dưới đây là
một vài giá trị tính được:
n
ln

1
1

2 3
1 1

4
4

5
56


Vì A1 ∩ A2 ≠ φ , ta có A1 ∩ A2 ∩ Ai ≠ φ . Như vậy, ta có A1 ∩ A2 ∩ Ai = { x} .
Do đó Ai = { x} ∪ (Ai − A1 ) ∪ ( Ai − A2 ) . Ngoài ra, do các tập Ai – A1 và Ai – A2 có thể
khác rỗng được chọn tương ứng theo 2s – 1 và i cách, nên số lớn nhất các tập
này là (2s – 1)(2r – 1). Cộng thêm các kết quả riêng này vào, ta nhận được số lớn
nhất các tập Ai là 2n-1 – 1 .


21
Ví dụ 2. Gọi S là tập hợp tất cả các n – bộ (X 1, X2, …, Xn), với mỗi Xi là một tập
con của tập {1, 2, …, 1998}. Với mọi k thuộc S (tức là, k là một n – bộ như trên),
ta gọi f(k) là số tất cả các phần tử trong hội của n tập hợp của k. Tìm tổng tất cả
các f(k) khi k chạy trong khắp S.
Giải. Gọi s(n, m) là tổng cần tính trong trường hợp các Xi là một tập con của tập
{1, 2, …, m}. Có tất cả 2m tập con Xi nên suy ra có tất cả 2mn các n- bộ như đề
bài. Cho một n – bộ bất kì (X1, …, Xn) gồm các tập con của tập {1, 2, …, m - 1},
ta có thể chọn để thêm vào phần tử m hoặc không thêm (2 cách chọn) cho mỗi
tập Xi. Bằng cách đó ta nhận được 2 n n – bộ gồm các tập con của tập {1, 2, …,
m}. Số f(k) của mỗi n – bộ này tăng lên 1, riêng có một n – bộ có số f(k) không
tăng. Từ đó ta suy ra được công thức (*) sau đây:
s(n,m) = 2ns(n, m – 1) + (2n – 1)2n(m-1) .

(*)

Dễ thấy s(n,1) = 2n – 1. Từ đó, và từ (*), bằng quy nạp ta chứng minh được
s(n,m) = m(2nm – 2n(m – 1)) .
Thay m = 1998, ta có được tổng cần tính là 1998(21998n – 21997n).
Ví dụ 3. Có bao nhiêu số nguyên không âm sao cho biểu diễn thập phân của nó
không quá 1993 chữ số, và các chữ số đó viết theo thứ tự không giảm?
k
k

m

các khả năng là

Cmm + Cmm+1 + Cmm+ 2 + ... + Cmm+ n − 2 = Cmm++n1−1 ,
theo công thức trên. Vậy kết quả đúng cho m + 1. Suy ra kết quả đúng cho mọi
8+ m − m

m. Đặt biệt, với n = 10, có C8+ m = C8+ m
m

= C88+m số TTKG với m chữ số.

Để ý rằng khi m = 0, theo quy ước, ta có 1 số có 0 chữ số, đó là số 0. Từ
đó, suy ra số các số nguyên không âm TTKG có không quá 1993 chữ số là
8
9
C88 + C98 + ... + C2001
= C2002
(theo công thức trên). Ta có
9
C2002
= 1398276498745133921413500 (có thể sử dụng Maple). 

Ví dụ 4. Gọi S là tập tất cả các hoán vị (a1, a2, …, an) của (1, 2, …, n) sao cho
trong mỗi hoán vị này có đúng một phần tử a i (khác a1) lớn hơn các phần tử
đứng trước nó. Tìm số trung bình của các số a1 trong các phần tử thuộc S.
Giải. Gọi a(n) là số tất cả các hoán vị thuộc S và b(n) là tổng các phần tử đầu
tiên của những hoán vị này. Gọi f(n) là số trung bình của các phần tử đầu tiên đó,
ta có f (n) =

= n!sn-1 – (n – 1).(n – 1)! – n!/ (n – 1) + (n – 2)! + (n – 1)!
= n!sn-1 – (n – 1).(n – 1)! + (n – 2)! ( – n + 1 + n – 1)
= n!sn-1 – (n – 1).(n – 1)! ,
Vậy công thức đúng với mọi n theo quy nạp.
Từ đó ta được f (n) = n −

n −1
1
1
, với sn = 1 + + L + . 
sn −1
2
n

Ví dụ 5. Có 1999 người tham dự một cuộc triển lãm. Cứ chọn ra 50 người một
cách tùy ý thì trong số 50 người này sẽ có ít nhất 2 người không biết nhau.


24
Chứng minh rằng ta có thể tìm được ít nhất 41 người sao cho mỗi người trong
số này biết nhiều nhất là 1958 người khác.
Giải. Gọi Y là tập hợp những người có biết ít nhất là 1959 người khác. Kí hiệu
N(p) là tập hợp những người mà người p có biết đến.
Để giải bài toán, ta giả sử ngược lại rằng có ít hơn 41 người sao cho mỗi
người trong số này biết nhiều nhất là 1958 người khác. Khi đó, Y ≥ 1959 (kí hiệu
. để chỉ số phần tử một tập hợp). Để có mâu thuẩn với giả thiết đề bài, ta sẽ

chứng minh rằng tồn tại một nhóm gồm 50 người mà tất cả đều có biết nhau.
Chọn ra người y1 ∈ Y và đặt B1 = N(y1), ta có B1 ≥ 1959 . Lúc đó B1 + Y > 1999 ,
do đó tồn tại người y2 ∈ B1 ∩ Y . Lại đặt B2 = N ( y1 ) ∩ N ( y2 ) , ta có

Giải. Kí hiệu M là số phần tử của tập (hữu hạn) M.
Gọi B1, B2, …, Bn là các tập con của A thỏa mãn
Bi = 3 , Bi ∩ B j ≠ 2 (i, j = 1, …, n).

Giả sử tồn tại phần tử a ∈ A , mà a thuộc vào 4 tập trong số các tập B1, B2, …, Bn
(chẳng hạn, a ∈ B1 , B2 , B3 , B4 ). Lúc đó, Bi ∩ B j ≥ 1 (i, j = 1, …, 4).
Mà Bi ≠ B j nếu i ≠ j , tức là Bi ∩ B j ≠ 3 . Do đó Bi ∩ B j = 1 (i, j = 1, …, 4).
Từ đây suy ra A ≥ 1 + 4.2 = 9 , điều này mâu thuẫn.
Như vậy, mỗi phần tử của A chỉ thuộc về nhiều nhất là ba trong số các tập B1, B2,
…, Bn . Khi đó, 3n ≤ 8.3 , hay n ≤ 8 .
Giả sử A = {a1, a2, …, ai} Xét các tập hợp con của A:
B1 = {a1, a2, a3} , B2 = {a1, a4, a5} , B3 = {a1, a6, a7} , B4 = {a8, a3, a4}
B5 = {a8, a2, a6} , B6 = {a8, a5, a7} , B7 = {a3, a5, a6} , B8 = {a2, a4, a7}.
Tám tập hợp trên là các tập con gồm ba phần tử của A thỏa mãn
Bi ∩ B j ≠ 2 . Vì vậy số n cần tìm là n = 8. 

Ví dụ 7. Gọi n, k là các số nguyên dương với k ≤ n và gọi S là tập hợp chứa n số
thực phân biệt. Gọi T là tập tất cả số thực có dạng
x1 + x2 + … + xk
với x1 , x2 , … , xk là các phần tử phân biệt của S. Chứng minh rằng, T chứa ít
nhất k(n – k) + 1 phần tử phân biệt.
Giải. Giả sử S1 < S2 < … < Sn là các phần tử của S, ta dùng quy nạp trên n, chú ý
rằng kết quả là tầm thường nếu k = 1 hay k = n. Giả sử rằng k ≤ n − 1 và kết quả
đúng với tập S0 = {s1, s2, …, sn-1}. Gọi T0 là tập con tương ứng. Khi đó,
T0 ≥ k (n − k − 1) + 1 .