Sáng kiến kinh nghiệm Phương pháp thiết lập quan hệ truy hồi trong các bài toán đếm

h chọn một 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à: 
 1, 12 1 . n kn k S 
 Trường hợp quả bóng nb không được chọn, lưu ý rằng 1k n . Mọi quả bóng 
trong các quả bóng 1 2 1, ,..., nb b b đều có thể bỏ vào các hộp bằng 1,n kS cách, suy ra 
 , 1, 1, 12 1 3, 2n k n k n kS S n k S n k n 
Nhận thấy , 1, 1 ,1 1,11 ; 1 ; 2n n n n nS n S S n n S 
Từ đó bằng quy nạp ta chứng minh được 
2
,
1 !
1
k
n
n k
n k C
S
n k
. 
21 
Bài 18: Xét đa giác đều n đỉnh với tâm O . Người ta tô màu các miền tam giác 
 1 1i iOA A i n 1 1nA A  bằng 3k k màu sao cho hai miền kề nhau được tô 
bởi hai màu khác nhau. Hỏi có bao nhiêu cách tô màu như vậy? 
Lời giải: 
 Gọi ,S n k là số cách tô màu thoả mãn bài toán. 
 Ta có k cách tô màu miền 1 2OA A , 1k cách tô màu miền 2 3OA A ,, 1k cách 
tô màu miền 1nOA A . Do đó có tất cả 
1
1
n
k k
 cách tô. Tuy nhiên, ta phải trừ đi 
các cách tô sai, chẳng hạn khi các miền 1nOA A và 1 2OA A cùng màu, khi đó ta coi 
2nOA A như một miền tam giác (bỏ qua đỉnh 1A ), số cách tô như vậy là 1,S n k . 
Do đó ta có hệ thức: 
1
, 1 1,
n
S n k k k S n k
1 2
1 [ 1 2, ]
n n
k k k k S n k
1 2 4 3
...
1 1 ... 1 [ 1 3, ]
n n n
k k k k k k S k
 Suy ra , 1 1 1
n n
S n k k k . 
Bài 19. Có n người ngồi thành một hàng ngang vào n chiếc ghế. Hỏi có bao nhiêu 
cách lập hàng mới cho n người đó mà trong mỗi cách lập hàng mới: mỗi người 
hoặc giữ nguyên vị trí của mình, hoặc đổi chỗ cho người liền bên trái, hoặc đổi chỗ 
cho người liền bên phải. 
Lời giải: 
 Đánh số thứ tự vị trí các ghế từ trái qua phải là 1,2,3,,n 
Gọi Sn là số cách lập hàng mới cho n người thỏa mãn đề bài. 
Dễ thấy S1 = 1, S2 = 2. 
22 
Với n 3 : Xét một cách lập hàng mới thỏa mãn điều kiện. Có hai loại hàng được 
lập: 
Loại 1: Người ở vị trí số 1 giữ nguyên vị trí. Rõ ràng số hàng được lập loại này là 
Sn-1 cách. 
Loại 2: Người ở vị trí số 1 đổi chỗ, khi đó người ở vị trí số 1 chỉ có thể xếp vào vị 
trí số 2 và người ở vị trí 2 phải chuyển sang vị trí 1. Số hàng loại này là Sn-2. 
Từ đó ta có n n 1 n 2S S S , n 3 . 
Vậy: 
*
1 2 n 2 n 1 nS 1,S 2,S S S , n N 
Bài 20. Có thể nào chia được 1989 điểm thành 30 nhóm có cỡ của các nhóm đó 
không bằng nhau để cho số các tập hợp gồm 3 điểm mà mỗi điểm được chọn từ 3 
nhóm khác nhau là lớn nhất. 
Lời giải: 
Giả sử các cỡ của 30 nhóm là. 
1 2 3 30...a a a a 
Ta sẽ gọi nhóm có cỡ ka vắn tắt là nhóm k. 
Giả sử 1 3k ka a 
Khi đó xét việc thay ka bởi 1ka và 1ka bởi 1 1ka ta vẫn còn được các nhóm có cỡ 
không bằng nhau. Số tất cả các bộ ba mà không có phần tử nào thuộc nhóm k hoặc 
k+1 thì không bị ảnh hưởng, chỉ có các bộ ba có đúng một phần tử thuộc nhóm k 
hoặc k+1 bị. Nhưng số các bộ ba có đúng một phần tử thuộc nhóm k và một phần 
tử thuộc nhóm k+1 tăng lên, bởi vì 1 11 1k k k ka a a a 
Như thế khoảng trống lớn nhất là 2. 
Giả sử có hai khoảng trống độ dài là 2. Ta giả sử 1 11 1j j k ka a a a 
Bây giờ ta có thể thay ja và 1ka bởi 1ja và 1 1ka . 
23 
Lập luận giống như trước số các bộ ba cũng tăng lên. 
Vậy có nhiều lắm là hai khoảng trống độ dài 2. 
Điều này chỉ đủ cho ta xác định các cỡ. Giả sử các cỡ tạo thành một dãy đơn giản 
có tất cả các khoảng trống bằng 1. Nếu thành phần đầu tiên là n thì thành phần sau 
cùng là n+ 29. và tổng là 
 30 2 29
2
n 
. Nhưng tổng này không thể bằng 1989 vì 
1989 không là bội của 5. 
Do đó ta giả sử các cỡ tạo thành một dãy dơn giản có tất cả các khoảng trống 
bằng 1. ngoại trừ một thành phần bị bỏ qua, để có một khoảng trống bằng 2.Nếu 
thành phần đầu tiên là v và thành phần bị bỏ qua là m thì ta có: 
 30 2 29
1989
2
n
m
Nếu 50n thì 2015 1989 26m ,số này quá nhỏ vì ta phải có m giữa n và n +30 
Nếu 52n thì 2077 1989 88m , số này quá lớn. 
Vậy n=51 và m =57 
Suy ra các cỡ là: 51,52, 56, 58, 59,60,...81. 
Bài 21 : Trong thành phố a có n cô gái và n chàng trai và các cô gái đều quen biết 
các chàng trai. Trong thành phố B có n cô gái 
1 2; ;...; ng g g và 2n-1 chàng trai
1 2 2 1; ;...; nb b b . Các cô gái ig chỉ quen các chành trai 1 2 2 1; ;...; ib b b và không quen biết 
các chàng trai khác. 
Kí hiệu A(r), B(r) lần lượt là số các cách thức khác nhau để r cô gái từ thành phố A 
và thành phố B có thể khiêu vũ với r chàng trai từ chính thành phố của họ tạo 
thành r cặp, mỗi cô gái với một chàng trai mà cô ấy quen biết. 
Chứng minh rằng A(r) =B(r). 
Lời giải: 
Ta kí hiệu A(r) và B(r) bởi A(n, r) và B(n, r) 
Ta có thể chọn r cô gái trong n cô gái của thành phố A bằng rnC cách 
24 
Ta có thể chọn r chàng trai trong n chàng trai của thành phố A bằng rnC cách 
Vì mỗi cô gái trong A đều quen với các chàng trai nên bất kì nhóm nào gồm r cô 
gái được chọn ra đều có thể xếp cặp với r chàng trai nên ta có 
!
, . . ! .
!
r r r
n n n
n
A n r C C r C
n r
Cho n 3 và 2 < r <3 . Xét mọi cách chọn r cặp bạn khiêu vũ trong B sao cho mỗi 
cô gái đều quen biết bạn nhảy của mình. Có hai trường hợp để chọn lựa. 
Nếu một trong các cô gái đang khiêu vũ là 
ng thì r-1 cô gái kia có thể chọn bạn 
nhảy bằng 
B(n-1, r-1) cách. Khi đó 
ng có thể chọn bất kì người nào trong (2n-1)-(r-1) chàng 
trai bởi vì cô gái ý quen biết tất cả 2n-1 chàng trai. Do vậy tổng số cách chọn trong 
trường hợp này là 
 (2n-r).B(n-1, r-1) 
Giả sử không có cô gái 
ng nào cả. Để ý rằng điều này không xảy ra nếu n = r nên 
1r n . Bây giờ mọi cô gái trong các cô 1 2 1; ;...; ng g g đều có thể chọn bạn nhảy mà 
các cô quen biết bằng B(n-1, r) cách. 
Từ đó ta có đẳng thức sau với mọi n 3 : 
 B(n, r) = B(n-1, r)+(2n-r).B(n-1, r-1) với r = 2,...n-1 
 và B(n, n) = n. B(n-1, r-1) 
Ta cũng thấy răng A(n, k) cũng thỏa mãn hệ thưc truy hồi tương tự. 
Vì A(n, 1) =B(n , 1)= 2n với mọi n và A(2,2) = B(2,2) = 2 
nên A(n, r) = B(n, r) với mọi n 1 và r=1,2,...n. 
Do đó: A(r) =B(r). 
25 
Bài 22 ( IMO-1967) Trong một cuộc đấu thể thao tổng số huy chương là m được 
phát trong n ngày thi đấu. Trong ngày thứ nhất người ta phát một huy chương và 
một phần bảy số huy chương còn lại.Trong ngày thứ hai người ta phát hai huy 
chương và một phần bảy số huy chương còn lại. Trong các ngày tiếp theo được 
tiếp tục và phát tương tự nhu thế. Ngày sau cùng còn lại n huy chương. để phát. 
Hỏi có bao nhiêu huy chương được thưởng và đã phát trong bao nhiêu ngày? 
Lời giải: 
Giả sử số huy chương còn lại khi bắt đầu ngày thi đấu thứ r là rm . Khi đó 
1 ; nm m m n 
và với mọi k<n ta có: 
1
6
7
k
k
m k
m 
Biến đổi và rút gọn ta có: 
2 1
7 7 7
1 2. 3. ...
6 6 6
n
m n
hay 
1
1
7 7 7
36 1 1 36 6
6 6 6
n n n
n
m n n n
Do 6 và 7nguyên tố cùng nhau nên 16n phải chia hết n-6 
Nhưng lại có 16 6n n nên n =6 và m=36 
Vậy có 36 huy chương và phát trong 6 ngày. 
Bài 23 (VMO 1990 – bảng A) Các em nhỏ của một lớp đứng thành vòng tròn chơi 
chò chia kẹo. Cô giáo cho mỗi em một số chẵn chiếc kẹo.Một em nào đó đưa nửa 
số kẹo của mình cho bạn ở ngay bên tay phải mình. Tiếp đó em vừa nhận được 
kẹo của bạn xong cũng làm như thế nếu số kẹo của mình là số chẵn , còn nếu là số 
lẻ thì nhận được một chiếc kẹo của cô trước khi đưa cho bạn. Các eo cứ đưa kẹo 
như thế theo vòng tròn.Chứng minh rằng sẽ dẫn đến trường hợp là có một em đưa 
một nủa số kẹo của mình không phải cho bạn mà là cho cô giáo thì khi đó số kẹo 
của mỗi em đều bằng nhau. 
26 
Lời giải: 
Giả sử hai học sinh A và B đứng liền nhau theo thứ tự chuyển kẹo. Xét thời điểm 
thứ n khi A đang chuyển nx chiếc kẹo cho B và giữ lại na chiếc kẹo mà B chưa 
nhận kẹo. 
lúc đó giả sử số kẹo mà A và B đang giữ là ,n na b . Gọi ,n nM T theo thứ tự là số kẹo 
lớn nhất và số kẹo nhỏ nhất của mọi học sinh tại thời điểm thứ n không tính đến nx . 
Tại thời điểm thứ n+1 khi B đang chuyển số kẹo 1nx cho người tiếp theo thì số 
kẹo của B theo giả thiết là: 1 1
,
2
1
2
n n
n n
n n
b x
b x
b x
Lúc đó người đứng tiếp sau B chưa nhận kẹo và số kẹo của mọi người trừ B ra 
không đổi so với thời điểm thứ n (*) 
Nếu 
n n na x b thì 1n n nb a b nên theo (*) thì 1 ,n nM M và 1 ,n nT T 
Nếu 
n n na x b ta xét riêng 1 1à n nM v T 
Xét 
1nM có 1
1 1 1
2 2 2
n n n n
n n
x b M M
b M 
Do n+1à bnM v đều là số nguyên thì 1n nb M . Từ đó và (*) suy ra: 1 ,n nM M 
Vậy dãy nM là dãy tự nhiên không tăng. 
Xét 1nT nếu n nx b thì 1 1 1n n n nb x a T ; nếu n nx b thì 1 1 1n n n nx b a T 
Vậy ta có 
1
1 1
2 2 2
n n n n
n n
x b T T
b T 
Do 
n+1à bnT v đều là số nguyên thì 1 1n nb T . Từ đó và (*) suy ra hoặc 1 ,n nT T nếu ở 
thời điểm thứ n chỉ có duy nhất một số n nb T hoặc 1 ,n nT T nếu có ít nhất một học 
sinh khác B có số kẹo là nT . 
27 
Vậy dãy nT là dãy tự nhiên không giảm, hơn nữa khi n n nb T a thì đến thời điểm 
thứ 
n + 1 có 1 1n nb T nên số nT sẽ mất đi một lần, và cứ tiếp tục chuyển kẹo sau hữu 
hạn lần thì số nT mất hết hết nghĩa là dãy nT tăng thực sự . 
Do dãy nM là dãy tự nhiên không tăng còn dãy nT là dãy tự nhiên không giảm 
và có lúc 
tăng thực sự nên đến một thời điểm nào đó phải có 
k kM T , lúc đó số keojcuar mọi 
học sinh đều như nhau. 
Bài 24 (VMO-2002) Cho tập S gồm tất cả số nguyên trong đoạn: [1; 2002]. Gọi T 
là tập hợp gồm tất cả các tập con không rỗng của S. Với mỗi tập X thuộc T kí hiệu 
m(X) là trung bình cộng của tất cả các số thuộc X. Đặt 
( )m X
m
T

 ở đây tổng lấy 
theo tất cả các tập hợp X thuộc T. Tìm m. 
Lời giải: 
Với mỗi k thuộc {1, 2, ...., 2002} đặt km m X  ở đây tổng lấy theo tất cả các tập 
hợp X thuộc T mà X k 
Xét số a bất kì thuộc tập S. Dễ thấy a có mặt trong 2001
kC tập X thuộc T mà X k 
Suy ra: 1 12001 2001. 1 2 3 ... 2002 1001.2003.
k k
kk m C C
nên 
 200212002 2002 2002
2001
2002
1 1 1
2003. 2 12003
1001.2003. .
2 2
k
k
k
k k k
C
m X m C
k
    
Vì 20022 1T nên 
 2003
2
m X
m
T
 
Bài 25: Cho A = {1, 2, , 2n}. Một tập con của A được gọi là tốt nếu nó có đúng 
hai phần tử x, y và |x – y| {1, n}. Tìm số các tập hợp {A1, A2, , An} thoả mãn 
điều kiện Ai là tập con tốt với mọi i = 1, 2, , n và A1  A2    An = A. 
Lời giải: 
28 
Từ giả thiết, ta sẽ viết lại bài toán như sau (các bạn tự kiểm tra tính tương đương 
của bài toán này so với bài ban đầu): “Cho 1 hình chữ nhật kích thước 2 n được 
chia thành các ô vuông đơn vị. Đánh số các ô từ trái qua phải là 1,2,...,n (hàng 1) 
và n + 1,n + 2,..,2n (hàng 2) Lát chúng bằng các quân domino 1 2 sao cho chúng 
phủ kín hình chữ nhật và không có 2 quân nào đè lên nhau. Ngoài ra, với n lẻ, ta 
được bổ sung thêm 1 quân domino "đặc biệt" có thể phủ kín 2 ô n và n + 1. Đếm số 
cách lát thỏa mãn đề bài” 
Với bài toán này, xét Sn là số cách lát thỏa mãn đề bài với hình chữ nhật kích thước 
2 n . Ta sẽ tìm cách xây dựng công thức truy hồi cho Sn 
Giả sử ta đã lát được hình chữ nhật 2 ( 1)n bằng các quân domino. Xét quân 
domino phủ lên ô vuông n. Có 3 khả năng xảy ra: 
1/ Quân domino đó phủ lên 2 ô: ( ;2 )n n . Rõ ràng phần còn lại là 1 hình chữ nhật 
kích thước 
2 n , và số cách lát trong tình huống này là Sn 
2/ Quân domino đó phủ lên 2 ô (n, n + 1) . Như vậy, buộc phải có 1 quân domino 
phủ lên 2 ô(2n-1,2n) và khi đó, phần còn lại là 1 hình chữ nhật kich thước 
2 ( 1)n . Tức số cách lát trong tình huống này là Sn-1 
3/ Quân domino đó phủ lên 2 ô (n, n+1) (với n lẻ). Khi đó, phần còn lại chỉ có thể 
lát được bằng các quân domino nằm ngang (nếu có 1 quân domino nào nằm dọc thì 
nó sẽ chia hình chữ nhật thành 2 phần, mỗi phần có 1 số lẻ ô chưa được lát (do 
quân domino "đặc biệt" gây ra)) 
Tức trong trường hợp này chỉ có 1 cách lát duy nhất 
Như vậy ta xây dựng được công thức truy hồi như sau: 2k 2k 1 2k 2S S S 1 
(lưu ý rằng khi n chẵn thì không có quân domino "đặc biệt" nên phải bớt đi 1 cách 
của S2k-1) 
 (lập luận tương tự với quân domino “đặc biệt”) 
Và bằng quy nạp ta sẽ thu được , trong đó Fk là số 
Fibonacci thứ k của dãy Fibonacci được xác định bởi công thức 
29 
Cuối cùng ta được công thức tổng quát : 
n n n
n
1 11 1 5 1 5
S
2 2 25
III. BÀI TẬP LUYỆN TẬP 
Bài 1 (Romania 2003) 
Cho số nguyên dương n . Có bao nhiêu số tự nhiên có n chữ số được lập từ các chữ 
số 2,3,7,9 và chia hết cho 3. 
Bài 2: Có bao nhiêu cách lát kín hình “hàm răng 2012 chiếc” (hình vẽ) bằng các 
quân đôminô 1 2 sao cho các quân đôminô không đè lên nhau và cũng 
không đè lên các đường tô đậm? 
Bài 3: Giả sử 1 2, ,..., nP P P theo thứ tự là các điểm trên cùng một đường thẳng. 
Người ta tô các điểm đó bằng 5 màu khác nhau, mỗi điểm tô 1 màu sao cho 2 điểm 
1, ( 1,2,..., 1)i iP P i n luôn hoặc là cùng màu hoặc là 1 trong 2 điểm được tô màu 
xanh. Hỏi có bao nhiêu cách tô như vậy? 
Bài 4: Có bao nhiêu số tự nhiên n thoả mãn đồng thời các điều kiện sau: 
a) n có 1000 chữ số 
b) Tất cả các chữ số của n là lẻ 
c) Hiệu của hai chữ số liên tiếp bất kì của n luôn bằng 2. 
2 2012
4
30 
Bài 5: ( Estonia 2007): Xét lưới ô vuông 10 x 10. Với mỗi nước đi ta tô màu hình 
vuông đơn vị nằm ở giao của 2 hàng và 2 cột. Một nước đi là hợp lệ nếu ít nhất 1 
trong 4 hình vuông này trước đó không được tô. Hỏi số nước đi lớn nhất có thể để 
tô toàn bộ lưới ô vuông là bao nhiêu? 
Bài 6 ( VMO 2015) :Cho số nguyên dương k . Tìm các số tự nhiên n không vượt 
quá 10k thỏa mãn các điều kiện sau: 
i) n chia hết cho 3 
ii) Các chữ số trong biểu diễn thập phân của n thuộc 2;0;1;5 . 
Bài 7: Cho A và E là 2 đỉnh đối tâm của 1 hình bát giác đều. Một con ếch bắt đầu 
nhảy từ A. Tại bất cứ đỉnh nào trừ E, con ếch có thể tới một trong 2 đỉnh kề. Nếu 
ếch nhảy tới E thì nó dừng lại. Tính số cách để ếch nhảy từ A tới E mất đúng n 
bước. (n>4) 
Bài 8: Xếp n học sinh ngồi quanh một bàn tròn. Ngân hàng đề có tất cả m loại đề 
thi. Hỏi có bao nhiêu cách phát đề cho học sinh sao cho không có 2 học sinh nào 
ngồi cạnh nhau có cùng đề thi? 
31 
PHẦN III. KẾT LUẬN 
 Thông qua chuyên đề “Phương pháp thiết lập quan hệ truy hồi trong các bài 
toán đếm” có thể giúp các em học sinh mới học về toán tổ hợp có thể nắm được 
cách tư duy và một số hướng giải quyết các bài toán tổ hợp, chuyên đề cũng giúp 
các em có nguồn tài liệu có nhiều bài toán đếm trong tổ hợp. Do điều kiện thời 
gian và năng lực còn hạn chế nên trong chuyên đề này tôi chưa thể mở rộng và đề 
cập đến những vấn đề khó và hay của tổ vì vậy tôi rất mong nhận được sự đóng 
góp và trao đổi kinh nghiệm của các đồng nghiệp. 
 Nhân đây, tôi cũng mong các bạn đồng nghiệp cùng đóng về cách thức 
giảng dạy chủ đề "Tổ hợp " cho học sinh, nên dạy như thế nào để học sinh cảm 
thấy hấp dẫn và không mệt mỏi về chủ đề này. 
 Bắc Giang, tháng 3 năm 2023 
 Ngƣời viết chuyên đề 
 Trần Anh Đức 
32 
 TÀI LIỆU THAM KHẢO 
[1] Đoàn Quỳnh, Tài liệu chuyên toán Đại số và giải tích 11, Nhà xuất bản 
Giáo dục, Hà Nội 2011. 
[2]Nguyễn Đức Nghĩa – Nguyễn Tô Thành, Toán rời rạc Nhà xuất bản đại học 
Quốc Gia Hà Nội. 
[3] Các chuyên đề của hội các trường chuyên khu vực Duyên hải và đồng bằng 
bắc bộ năm 2013. 
[4] Báo toán học và tuổi trẻ. 
[5] Các diễn đàn về toán và các nguồn tài liệu trên Internet.