ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐÀO DUY HẢO
ĐẲNG THỨC, BẤT ĐẲNG THỨC VÀ CÁC BÀI
TOÁN CỰC TRỊ TRONG TỔ HỢP
LUẬN VĂN THẠC SỸ TOÁN HỌC
THÁI NGUYÊN - NĂM 2014
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐÀO DUY HẢO
ĐẲNG THỨC, BẤT ĐẲNG THỨC VÀ CÁC BÀI
TOÁN CỰC TRỊ TRONG TỔ HỢP
LUẬN VĂN THẠC SỸ TOÁN HỌC
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số 60.46.01.13
Người hướng dẫn khoa học
GS. TSKH. NGUYỄN VĂN MẬU
THÁI NGUYÊN - NĂM 2014
Mục lục
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chương 1. Tổ hợp và các hệ thức liên quan . . . . . . . . . . . . . . . . . . . . . 3
1.1. Nguyên lý Dirichlet và một số bài toán áp dụng. . . . 3
1.2. Ý tưởng và lời giải tường minh một số bài toán tổ hợp . 7
1.3. Cách xây dựng song ánh giải một số bài toán tổ hợp. . . . . . 14
1.4. Phương pháp thiết lập hệ thức truy hồi trong tổ hợp 20
1.5. Khai triển nhị thức Newton . . . . . . 27
1.6. Phương pháp quỹ đạo . . . . . . . . . . . . . . . . . . . 28
1.7. Ứng dụng đẳng thức tổ hợp vào số học . . . . . . . . . . . . . . . 30
Chương 2. Bất đẳng thức trong tổ hợp . . . . . . . . . . . . . . . . . . . . . . 33
2.1. Các bất đẳng thức cơ bản trong tổ hợp . 33
2.2. Hệ phương trình và tính toán tổng. . . . . . . . 36

Chương 3. Một số dạng toán cực trị trong tập rời rạc và tổ hợp.
Luận văn này được hoàn thành dưới sự hướng dẫn nhiệt tình của GS.
TSKH. Nguyễn Văn Mậu, thầy đã giúp tôi hiểu sâu hơn về các khái niệm,
thuật toán liên quan đến đề tài của mình. Tôi xin bày tỏ sự kính trọng và
1
lòng biết ơn sâu sắc đến thầy.
Tôi xin chân thành cảm ơn quý thầy cô trong trường ĐH Khoa học- Đại
học Thái Nguyên, các thầy ở Viện Toán học, ĐHKHTN-ĐHQG Hà Nội
đã tận tình giảng dạy và tạo điều kiện thuận lợi cho chúng tôi có những
kiến thức cơ sở đủ vững để thực hiện đề tài.
Trong quá trình biên không tránh khỏi những sai sót, tôi rất mong nhận
được ý kiến đóng góp của độc giả để đề tài được hoàn thiện hơn.
Xin chân thành cảm ơn.
2
Chương 1
Tổ hợp và các hệ thức liên quan
1.1. Nguyên lý Dirichlet và một số bài toán áp dụng
Nguyên lý Dirichlet (thuật ngữ tiếng Anh: the pigeonhole principle, cũng có
nơi gọi là the drawer principle) - ở dạng đơn giản nhất - được phát biểu đầu tiên
bởi G.Lejeune Dirichlet (1805-1859), một nhà toán học Đức gốc Pháp, như sau:
"Nếu nhốt n + 1 con thỏ vào n cái chuồng (n ∈ N
∗
) thì luôn có (ít nhất là)
hai con thỏ bị nhốt trong cùng một chuồng".
Một cách tổng quát, ta có nguyên lý Dirichlet mở rộng:
"Nếu nhốt m con thỏ vào n cái chuồng (m, n ∈ N
∗
) thì luôn tồn tại một
chuồng chứa ít nhất là 1 +


Hiệu của hai số này là 11 1

n−k( so)
.10
k
với (n > k) Mà ta có (2011, 10
k
) = 1.
Do đó 11 1

n−k( so)
.
.
.2011.
Bài toán được chứng minh.
Bài toán 1.2. [Vô địch Cộng hoà Czech 1998] Cho X là một tập hợp gồm 14
số nguyên dương phân biệt. Chứng minh rằng có một số nguyên dương k ≤ 7 và
có hai tập con k-phần tử:
{a
1
; a
2
; . . . ; a
k
}, {b
1
; b
2
; . . . ; b
k

k




<
1
1000
.
Lời giải.
Xét C
7
14
= 3432 tập con 7-phần tử của X. Tổng (các) nghịch đảo của các phần
tử trong mỗi tập con này rõ ràng là không vượt quá
1
1
+
1
2
+ ··· +
1
7
< 2, 6 nên
phải thuộc vào một trong số 2600 nửa khoảng:

0
1000
;
1

2
là một số nguyên tố.
4
Lời giải.
Ta thấy, nếu a, b cùng chẵn thì a
2
+ b
2
là hợp số. Do đó tập con X của A có hai
phần tử phân biệt a, b mà a
2
+ b
2
là một số nguyên tố thì X không thể chỉ chứa
các số chẵn. Suy ra k ≥ 9. Ta chứng tỏ k = 9 là giá trị nhỏ nhất cần tìm. Điều
đó có nghĩa là với mọi tập con X gồm 9 phần tử bất kì luôn tồn tại hai phần
tử phân biệt a, b mà a
2
+ b
2
là một số nguyên tố. Để chứng minh khẳng định
trên ta chia tập A thành các cặp hai phần tử phân biệt a, b mà a
2
+ b
2
là một
số nguyên tố, ta có tất cả 8 cặp
(1; 4), (2; 3), (5; 8), (6; 11), (7; 10), (9; 16), (12; 13), (14; 15).
Theo nguyên lí Dirichlet thì trong 9 phần tử của X có hai phần tử thuộc cùng
một cặp và ta có điều phải chứng minh.


k=1
A(i − 1; k), A(i; j) := B
i
+ A(i − 1; j)
với mọi i, j nguyên dương mà i ≥ 2, j ≤ 1999. Từ cách xây dựng trên, dễ dàng
chứng minh A(m; j) < A(n; j), A(m; j)/A(n; j) với mọi bộ ba số nguyên dương
m, n, j mà j ≤ 1999 và m < n. Từ cách xây dựng trên, cũng dễ thấy (với mỗi
i ∈ N
∗
: A(i; 1), A(i; 2), . . . , A(i; 1999)) là 1999 số nguyên dương liên tiếp (không bé
hơn a
1
) do đó, theo giả thiết của bài toán về tập hợp A, thì tồn tại j
i
∈ Z∩[1; 1999]
để A(i; j
i
) ∈ A.
Bấy giờ, vì j
1
, j
2
, . . . , j
2000
∈ Z ∩[1 : 1999], nên theo nguyên lý Dirichlet, có hai
số nguyên dương m < n ≤ 2000 mà j
m
= j
n

3
) ∈ A
được gọi là trội hơn bộ y = (y
1
; y
2
; y
3
) ∈ A nếu x = y và x
i
≥ y
i
với mọi i ∈ {1; 2; 3};
khi đó, ta viết x > y. Tìm số tự nhiên n bé nhất sao cho mọi tập con n-phần tử
của A đều chứa ít nhất là hai bộ x, y mà x > y.
Lời giải.
1/ Trước hết, xét tập hợp B := {x ∈ A|x
1
+ x
2
+ x
3
= 11}. Có thể kiểm tra trực
tiếp rằng B là một tập con 48-phần tử của A (B gồm đúng: 4 phần tử có dạng
x = (0; x
2
; 11 − x
2
) với 4 ≤ x
2

2
) với 0 ≤ x
2
≤ 6; 6 phần tử có
dạng x = (6; x
2
; 4 −x
2
) với 0 ≤ x
2
≤ 5; và 5 phần tử có dạng x = (7; x
2
; 4 −x
2
) với
0 ≤ x
2
≤ 4.
Rõ ràng B không chứa hai bộ x, y nào mà x > y.
2/ Tiếp theo, cho N  n ≥ 49, và B là một tập con n-phần tử bất kỳ của A.
Ta sẽ chứng minh rằng B chứa ít nhất hai bộ x, y mà x > y.
Muốn vậy, xét các tập con sau đây của A:
C
1
:= {x ∈ A|x
1
= 0 ∨ x
2
= 7}, C
2

= 4)}, C :=
4

i=1
C
i
,
D := A \ C ≡ {x ∈ A|x
1
≥ 4 ∨ x
2
≤ 3},
C
i,j
:= {x ∈ C
i
|x
3
= j} (i, j ∈ Z; 1 ≤ i ≤ 4; 0 ≤ j ≤ 7),
D
p,q
:= {x ∈ D|x
1
= p, x
2
= q} (p, q ∈ Z; 4 ≤ p ≤ 7; 0 ≤ q ≤ 3);
và chỉ cần khảo sát hai trường hợp:
(i) Nếu B ∩C là một tập hợp có nhiều hơn 32 phần tử, thì do chỉ có 32 tập
con C
i,j

giải của tác giả một cách khá dễ dàng. Tại sao lại như vậy?
Một số BTTH thường đề cập một số yếu tố ràng buộc theo những quy tắc
nào đó. Yêu cầu của bài toán là đánh giá một đại lượng nào đó liên quan đến
các yếu tố đã đề cập, hoặc chứng minh một quy tắc nào đó luôn thực hiện được,
hoặc chứng minh một quy luật nào đó nghiệm đúng.
Lược đồ tự nhiên để tiếp cận việc giải loại bài toán này đã được hình thành
cho học sinh từ các lớp dưới gồm các bước:
1. Chọn ẩn để mô tả các yếu tố trong đầu bài thành một phương trình, một
bất phương trình hoặc một hệ hỗn hợp chứa ẩn đã chọn.
2. Xử lý các điều vừa mô tả theo yêu cầu của bài toán bằng cách giải ra
nghiệm hoặc biến đổi thành những kết quả giúp cho việc hình thành quy tắc
hay quy luật thỏa yêu cầu bài toán.
7
Từ ý tưởng giải như thế thì khâu then chốt nhất là thể hiện tường minh ra
một lời giải cụ thể. Do bài toán khó, người giải được bài toán chắc chắn phải
chỉ ra được mối quan hệ nội tại của các yếu tố trong bài toán thông qua các kỹ
năng biến đổi tinh xảo hoặc những nhận xét tinh tế, bản chất nhất từ hệ đã mô
tả được.
Ngay ở bước 1, việc khéo chọn ẩn, hoặc đặt thêm ẩn phụ hoặc tích hợp các
yếu tố trong đầu bài là sự sáng tạo rất cá biệt riêng của người giải.
Hoàn thành bước 1 đã là một thành công mà không phải học sinh nào cũng
làm tốt, nhưng điều cốt yếu là xử lý thành công ở bước 2. Trong bước này
thường nảy sinh một số vấn đề là các kết quả thu được thường là do các phép
biến đổi hệ quả. Việc khảo sát ngược lại là cần thiết, hoặc ít ra giải quyết được
vấn đề tồn tại tình huống mà đã chỉ ra. Đưa ra một ví dụ cụ thể để chứng tỏ
tồn tại tình huống cũng không phải dễ dàng, còn tạo được một quy trình hợp
lý, chặt chẽ, có hệ thống để xây dựng được tình huống đôi lúc lại khó hơn yêu
cầu của đầu bài.
Các BTTH này đều do các nhà toán học lừng danh trên thế giới sáng tác
nên trong lời giải của họ thường thông báo một khám phá mới về tri thức toán,

A
8
mà không có ba đường chéo nào của nó cắt nhau tại một
điểm. Ta gọi mỗi giao điểm của hai đường chéo của bát giác là một nút. Xét các
tứ giác lồi mà mỗi tứ giác đều có cả bốn đỉnh là đỉnh của bát giác đã cho. Ta
gọi mỗi tứ giác như vậy là tứ giác con.
Hãy tìm số nguyên n nhỏ nhất có tính chất: có thể tô màu nút sao cho với
mọi i, k ∈ {1, 2, 3, 4, 5, 6, 7, 8} và i = k, nếu ký hiệu s(i, k) là số tứ giác con nhận
A
i
, A
k
làm đỉnh và đồng thời có giao điểm hai đường chéo là một nút đã được
tô màu thì tất cả các giá trị s(i, k) đều bằng nhau.
Lời giải.
Gọi n là số nguyên nhỏ nhất thoả bài toán. Ta có s(i, k) = s(1, 2) với mọi i, k ∈
{1, 2, 3, 4, 5, 6, 7, 8} và i = k.
Do một nút tương ứng với C
2
4
cặp đỉnh nên:
n.C
2
4
=

i<j
s(i, j) = C
2
8

+ ··· + x
k
(1)
48 = 1x
1
+ 2x
2
+ ··· + kx
k
(2)
+) Gọi y là số cách chọn hai hộp không có chung màu nào. Do hai hộp bất
kỳ có chung không quá một màu nên:
C
2
8
= C
2
2
x
2
+ C
2
3
x
3
+ ··· + C
2
k
x
k

+

i2
(i − 2)(i − 3)
6
x
i
+
1
3
y  0.
Từ đó:
n  23.
+) Cách tô sau của 23 màu thỏa bài toán (gọi tên màu là: 1, 2, . . . , 23)
Hộp I 1 3 4 5 6 7
Hộp II 1 8 9 10 11 12
Hộp III 1 13 14 15 16 17
Hộp IV 2 3 8 13 18 19
Hộp V 2 4 9 14 20 21
Hộp VI 2 5 10 15 22 23
Hộp VII 6 11 16 18 20 22
Hộp VIII 7 12 17 19 21 23
10
Nhận xét 1.2. +) Ở hình dưới, mỗi đường tượng trưng cho mỗi hộp, các giao
điểm ở trên đường tượng trưng cho các banh.
+) Có đúng 8 đường, mỗi đường chứa đúng 6 giao điểm và có tất cả 23 giao
điểm. Hai đường bất kỳ có tối đa một điểm chung.
+) Mỗi cách đánh số 23 giao điểm, từ 1 đến 23, cho ta một cách tô màu trên
các banh ở 8 hộp thỏa các điều kiện bài toán.
Bài toán 1.8. [IMO 2005, Bài 6] Trong một kỳ thi học sinh giỏi, các thí sinh

+) Với i, j và i = j, gọi s(i, j) = s(j, i) là số thí sinh giải được cả bài i và bài
j, (i, j = 1, 2, 3, 4, 5, 6).
Theo giả thiết luôn có: 5s(i, j) > 2n. Do đó: 5s(i, j)  2n+1. Có tất cả C
2
6
= 15
cặp (i, j) mà i < j nên:

i<j
5s(i, j)  15(2n + 1).
Do đó:
S =

i<j
s(i, j)  3(2n + 1) (5)
+) Ta cũng có:
S = C
2
2
x
2
+ C
2
3
x
3
+ C
2
4
x

+ x
3
+ x
4
+ x
5
) + 3
11
hay
4x
5
 6x
0
+ 6x
1
+ 5x
2
+ 3x
3
+ 3  3 (7)
Từ đó:
x
5
 1.
+) Ta chứng minh thêm x
5
không thể bằng 1.
Giả sử x
5
= 1. Lúc đó từ (7) cho x

+) Nếu a là số nguyên thì hiệu s(i, j)−a là số nguyên không âm. Từ S = 6n+4
viết lại

i<j
(s(i, j) − a) = 1, suy ra trong 15 số hạng s(i, j) với i < j, phải có
14 số hạng có cùng giá trị là a và đúng một số hạng có giá trị là a + 1. Gọi
s(p, q) = a + 1. Do đó giá trị của

6
j=1,j=r
s(r, j) chỉ có thể là 5a hoặc 5a + 1 tùy
theo r không thuộc hoặc thuộc {p, q}.
Kết hợp với (*), ta có hoặc 5a chia hết cho 3 hoặc 5a + 1 chia hết cho 3 (**).
12
+) vì thí sinh A giải được 5 bài, nên tồn tại một bài t khác với các bài p, q, r
mà thí sinh A giải được. Gọi h là số thí sinh giải được bài t. Trong số h thí sinh
này, thì thí sinh A giải được bài t và thêm đúng 4 bài nữa, và h −1 thí sinh còn
lại cũng giải được bài t và thêm đúng 3 bài nữa.
Vì vậy:
4 + 3(h − 1) =
6

j=1,j=t
s(t, j) hay
6

j=1,j=t
s(t, j) = 3h + 1.
Do t /∈ {p, q} nên:
6

kiện sau:
1. Trong mỗi hộp, không có hai banh nào được tô cùng một màu.
2. Hai hộp bất kì có chung không quá một màu.
13
Bài toán 1.11. Trong một kỳ thi học sinh giỏi, các thí sinh phải giải 6 bài
toán. Biết rằng với hai bài toán bất kỳ luôn có nhiều hơn
2
5
số thí sinh dự thi
giải được cả hai bài toán này. Ngoài ra không có thí nào giải được cả 6 bài toán.
a. Gọi k là số thí sinh giải được đúng 5 bài toán. Tìm giá trị nhỏ nhất của k.
b. Chứng minh tồn tại ba bài toán mà có nhiều hơn
1
5
số thí sinh dự thi giải
được.
c. Chứng minh tồn tại bốn bài toán mà có nhiều hơn
1
15
số thí sinh dự thi
giải được.
Bài toán 1.12. Cho một n-giác lồi có diện tích S. Chứng minh rằng tồn tại
một cạnh AB của đa giác và một điểm M thuộc miền đa giác này sao cho khoảng
cách từ điểm M đến đường thẳng AB không nhỏ hơn
4S
nAB
.
1.3. Cách xây dựng song ánh giải một số bài toán
tổ hợp
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

là số các xâu không
chứa bốn số liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0, 0. Chứng minh rằng: b
n+1
= 2a
n
.
Lời giải.
Ta gọi một xâu thuộc loại A nếu nó không chứa ba số liên tiếp 0, 1, 0 và gọi một
xâu thuộc loại B nếu nó không chứa 4 số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0, 0.
Với mỗi xâu X = (x
1
, x
2
, . . . , x
n
), ta xây dựng f(X) = (y
1
, y
2
, . . . , y
n+1
) như
sau: y
1
= 0, y
k
≡ x
1
+ x
2

số các số 2. Ví dụ 12121221221112 → 1234142 như sau:
1212122
1221112
1234142
Như thế song ánh giữa hai tập hợp đã được thiết lập và ta có M = N. Cách
xây dựng song ánh như trên khá đẹp song hơi cầu kì. Chúng ta sẽ tìm ra một
lời giải ngắn gọn hơn như sau:
Lời giải 2.
∀k ∈ S = {0, 1, . . . , n}, ta thực hiện 2 lần (độc lập với nhau) việc đánh dấu k
trong n vị trí trên một hàng. Sau đó, ở mỗi vị trí ta ghi: chữ số 3 nếu được đánh
dấu 3 lần, chữ số 4 nếu không được đánh dấu lần nào, chữ số 1 nếu chỉ được
đánh dấu lần đầu và chữ số 2 nếu chỉ được đánh dấu lần sau.
Rõ ràng khi cho k chạy trên S thì số tất cả các số thu được chính là N. Hơn
nữa, ∀k ∈ S thì có thể xem số cách đánh dấu lần đầu là số cách chọn k trong số
n vị trí, còn số cách đánh dấu lần sau là số cách chọn n −k vị trí trong n vị trí.
Do đó tổng số cách đánh dấu khi k chạy trên S đúng bằng số cách chọn n phần
tử từ 2n phần tử (tức là C
n
2n
), và số này chính là M. Vậy ta có điều phải chứng
minh.
Bài toán 1.16. Cho m và n là hai số nguyên dương. Xét phương trình nghiệm
nguyên x
1
+ x
2
+ + x
n
= m Hỏi phương trình trên có bao nhiêu nghiệm nguyên
không âm?

người ta xây dựng một song ánh đi từ một tập vào chính nó, và nguyên tắc ở
đây có thể phát biểu như sau: "Khi đếm số phần tử một tập hợp bằng nhiều
cách thì các kết quả thu được bằng nhau". Chẳng hạn từ bài toán 1.15, nếu ta
tính N theo cách "truyền thống": có C
i
n
C
i
n−1
cách chọn vị trí cho i chữ số 1 và i
chữ số 2, còn lại 2
n−2i
cách chọn vị trí cho các chữ số 3 và 4, với i chạy từ 0 tới

n
2

thì ta đã chứng minh được một đẳng thức khá thú vị:
[n/2]

i=0
C
i
n
C
i
n−i
2
n−2i
= C

Ta đếm số cách chọn n phần tử từ một tập gồm 2n phần tử theo hai cách.
Cách thứ nhất: mỗi lần chọn ra n phần tử, khi đó số cách hiển nhiên là C
n
2n
.
Cách thứ hai: trước hết ta chia tập 2n phần tử thành hai tập con, mỗi tập gồm
n phần tử; sau đó chọn từ tập con thứ nhất k phần tử (có C
k
n
cách chọn) và
chọn từ tập con thứ hai n −k phần tử (có C
n−k
n
= C
k
n
cách chọn), ta sẽ có

C
k
n

2
cách chọn; cuối cùng cho k chạy từ 0 tới n ta được tổng số cách chọn cần tìm là

C
0
n

2

C
1
n+1
+ ··· + C
0
m−k
C
k
n+k
.
17
Lời giải.
Ta đếm số các bộ số nguyên T = (a
1
, a
2
, . . . , a
m+n+1−k
) với 1  a
1
< a
2
< ··· <
a
m+n+1−k
 m + n + 1 bằng hai cách.
Cách thứ nhất: Ta xem đó là số cách chọn m + n + 1 −k số từ m+ n+ 1 số nên
sẽ có C
k
m+n+1

, . . . , a
m+n+1−k
)
thoả mãn m + 2 − i  a
m+2−k
< ··· < a
m+n+1−k
 m + n + 1, từ đó cho i chạy
từ 0 tới k (do m + 1 − k  a
m+1−k
 m + 1) ta được tổng số cách chọn là
C
k
m
C
0
n
+ C
k−1
m−1
C
1
n+1
+ ··· + C
0
m−k
C
k
n+k
. Kết quả đó cho ta điều phải chứng minh.

(m(X) + m(f(X))) = |T |.2003 ⇒ m =

m(X)
|T |
=
2003
2
.
18
Bài toán 1.20. Hãy tính trung bình cộng tất cả các số N gồm 2002 chữ số
thoả mãn N
.
.
.99 và các chữ số của N thuộc {1, 2, 3, 4, 5, 6, 7, 8}.
Lời giải.
Gọi M là tập các số N thoả mãn điều kiện đề bài. Xây dựng ánh xạ f như sau:
Nếu N = a
1
a
2
. . . a
2002
thì f(N) = b
1
b
2
. . . b
2002
, với b
i

ngừng tìm tòi, suy nghĩ để có một tư duy nhạy bén.
Bài tập
Bài tập 1.1. Chứng minh rằng C
k
n
= C
n−k
n
với mọi k, n ∈ N; n ≥ 1; 0 ≤ k ≤ n.
Bài tập 1.2. Người ta xếp n nam sinh và n nữ sinh thành một hàng, sau đó tìm
cách cắt hàng thành hai khúc sao cho mỗi khúc có số nam sinh bằng số nữ sinh.
Gọi A là số trường hợp không thể cắt hàng theo yêu cầu trên, B là số trường
hợp chỉ có thể cắt hàng theo yêu cầu trên một cách duy nhất.
Chứng minh rằng: B = 2A.
Bài tập 1.3. Một câu lạc bộ leo núi có n thành viên tổ chức 4 cuộc leo núi và
E
1
, E
2
, E
3
, E
4
là các đội tham gia vào các cuộc leo núi ấy. Hỏi có bao nhiêu cách
chia các đội sao cho E
1
∩ E
2
= ∅, E
2

m
.C
k−1
n
+ +C
k
m
.C
0
n
= C
k
m+n
với
mọi k, n, m ∈ N; n, m ≥ 1; 0 ≤ k ≤ min {m, n}.
1.4. Phương pháp thiết lập hệ thức truy hồi trong
tổ hợp
Một trong những phương pháp có hiệu quả để giải bài toán tổ hợp là thiết
lập hệ thức truy hồi. Nội dung cơ bản của phương pháp này như sau: Thay vì
ta đếm trực tiếp f(n) theo yêu cầu bài toán, ta sẽ thiết lập hệ thức quan hệ giữa
f(n), f(n − 1), . . . để từ đó tính được f(n).
Bài toán 1.21. [Olympic Bungari, 1995] Cho số nguyên n  2. Hãy tìm số
các hoán vị (a
1
, a
2
, . . . , a
n
) của 1, 2, . . . , n sao cho tồn tại duy nhất một chỉ số
i ∈ {1, 2, . . . , n − 1} thoả mãn a

n−1

i=1
C
i−1
n−1
= S
n−1
+ 2
n−1
− 1.
Chú ý rằng S
2
= 1, từ đó ta có: S
n
= 2
n
− n − 1.
Ở bài này ta thiết lập hệ thức truy hồi xuất phát từ S
n
đi đến S
n−1
. Trong
một số trường hợp, ta lại đi theo hướng ngược lại. Chẳng hạn:
Bài toán 1.22. Giả sử F
k
là tập hợp tất cả các bộ (A
1
, A
2

| (Trường hợp
n = 1998 là bài thi APMO 1998).
20
Lời giải.
Do có 2
n
tập con của {1, 2, . . . , n} nên có 2
nk
bộ (A
1
, A
2
, . . . , A
k
). Với mỗi k-
bộ (A
1
, A
2
, . . . , A
k
) của tập {1, 2, . . . , n − 1} ta có thể thêm hoặc không thêm n
vào tập A
i
để được k-bộ (A
1
, A
2
, . . . , A
k

1
= 2
k
− 1. Từ đấy bằng quy nạp ta chứng minh được: S
n
=
n.2
k(n−1)
(2
k
− 1). Cũng giống bài toán 1, ta có bài toán sau:
Bài toán 1.23. Tìm số tập con của tập {1, 2, . . . , n} sao cho trong mỗi tập con
chứa ít nhất hai phần tử là hai số nguyên liên tiếp.
Lời giải.
Gọi S
n
là tập hợp các tập con không rỗng của tập {1, 2, . . . , n} mà trong mỗi tập
con không có hai phần tử nào là hai số nguyên liên tiếp. Chia các phần tử của
S
n
thành hai nhóm:
Nhóm không chứa {n}: số các tập con như vậy là |S
n−1
|
Nhóm chứa phần tử n: {n} hoặc {a
1
, a
2
, . . . , a
n


n+2
−

1 −
√
5
2

n+2

−1
Mặt khác số tập con không rỗng của tập {1, 2, . . . , n} là 2
n
− 1. Vậy số tập
con mà trong mỗi tập con không có 2 phần tử nào là hai số nguyên liên tiếp là:
2
n
−
1
√
5

1 +
√
5
2

n+2
−

. Hỏi có bao
nhiêu cách bỏ k (1  k  n) quả bóng vào các hộp, biết rằng mỗi hộp chứa nhiều
nhất một quả bóng. (Hai cách bỏ bóng được gọi là khác nhau khi ít nhất một
quả bóng được bỏ vào hai hộp khác nhau trong hai cách đó).
21
Lời giải.
Đặt S
n,k
là số cách bỏ k quả bóng vào các hộp. Giả sử 2  k  n. Nếu một trong
k quả bóng được chọn là b
n
thì (k − 1) quả bóng còn lại có thể bỏ vào các hộp
bằng S
n−1,k−1
cách. Đồng thời, b
n
có 2n − (k − 1) = 2n − k + 1 cách chọn 1 hộp
trong các hộp còn lại để bỏ. Do đó số cách bỏ bóng trong trường hợp này là:
(2n − k + 1).S
n−1,k−1
.
Trường hợp quả b
n
không được chọn. Để ý rằng k  n − 1. Mọi quả bóng
trong các quả bóng b
1
, b
2
, . . . , b
n−1


2
n − k + 1
Bài toán 1.25. Có n (n > 1) thí sinh ngồi trên một bài tròn. Hỏi có bao nhiêu
cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn có đề khác nhau, biết
rằng trong ngân hàng đề có đúng m (m > 1) đề và hiển nhiên mỗi đề có nhiều
bản.
Lời giải.
Nhận xét rằng do thí sinh ngồi theo vòng tròn, nên một cách tự nhiên chúng
ta nghĩ tới việc tìm cách "cắt" và "nắn" vòng tròn thành hàng thẳng.
Cách 1. Kí hiệu P
n
là số cách phát đề hợp lệ cho n học sinh a
1
, a
2
, . . . , a
n
ngồi
theo vòng tròn (một cách phát đề được coi là hợp lệ nếu mỗi thí sinh được nhận
chỉ một đề và hai thí sinh bất kì ngồi gần nhau thì nhận được hai loại đề khác
nhau).
Ta viết a
i
= a
j
(i = j) nếu a
i
và a
j