Tổ hợp
1. Lý thuyết cơ bản
Các bài toán về tổ hợp cũng rất đa dạng về nội dung, hình thức và phương pháp
giải. Bài toán tổ hợp có thể ẩn chứa đường sau các bản chất đại số, số học, hình
học … và để giải chúng ta cũng cần vận dụng những kiến thức tổng hợp.
Có thể chia các bài toán tổ hợp thành các loại chính sau
+ Bài toán đếm số phần tử của một tập hợp
+ Các bài toán về đồ thị, tô màu
+ Các bài toán trên lưới nguyên, trên bảng vuông
+ Các bài toán bất biến, đơn biến
+ Các bài toán trò chơi
+ Các bài toán hình học tổ hợp
+ Và một số loại toán khác
Để giải bài toán đếm, ta sử dụng các kiến thức cơ bản và nâng cao đã được học, đó
là các quy tắc đếm: quy tắc cộng, quy tắc nhân, quy tắc trừ, nguyên lý bù trừ, các
số tổ hợp, chỉnh hợp, hoán vị. Ngoài ra, sử dụng các phương pháp đếm nâng cao
như Phương pháp song ánh, Phương pháp quan hệ đệ quy, Phương pháp đồ thị,
Phương pháp hàm sinh.
Định lý. (Đường đi trên lưới nguyên) Số đường đi ngắn nhất trên lưới nguyên từ
m
điểm A(0, 0) đến điểm B(m, n) bằng C m+ n .
Định lý. (Bài toán chia kẹo Euler) Số nghiệm nguyên không âm của phương trình
x1 + x2 + … + xn = k
n −1
là C k + n −1 .
Định lý. (Nguyên lý bao hàm và loại trừ) Với A 1, A2, …, An là các tập hợp bất kỳ,
ta có
n

n


∑ d ( x) = 2 | E |

x∈X

Định lý. (Ore) Cho G là đồ thị đơn vô hướng bậc n. Nếu với hai đỉnh không kề
nhau u, v bất kỳ ta có d(u) + d(v) ≥ n thì G là đồ thị Hamilton.
Định lý. (Euler) Với một đa diện lồi bất kỳ ta luôn có
M–C+Đ=2
Trong đó M là số mặt, C là số cạnh và Đ là số đỉnh.
Định lý (Redei) Một tournament bất kỳ đều có một đường đi Hamilton.
Nhiều bài toán trò chơi hay biến đổi trạng thái được giải quyết một cách khá hiệu
quả nhờ khái niệm bất biến, đơn biến.
Định nghĩa. Cho tập hợp Ω (tập hợp các trạng thái) và tập hợp T (tập hợp các phép
biến đổi) các ánh xạ từ Ω  Ω. Hàm số f: Ω  R được gọi là bất biến đối với cặp
(Ω, T) nếu ta có f(t(ω)) = f(ω) với mọi ω thuộc Ω và với mọi t thuộc T.
Nguyên lý bất biến. Nếu f là một bất biến của (Ω, T) và f(ω’) ≠ f(ω) thì ω’ không
thể thu được từ ω thông quan các phép biến đổi T.
Nguyên lý Dirichlet, nguyên lý cực hạn, phép quy nạp toán học cũng là những
công cụ thường được sử dụng trong phép giải các bài toán tổ hợp.
Mệnh đề. (cơ sở của nguyên lý cực hạn)
a) Nếu A là một tập con hữu hạn bất kỳ của R thì A có phần tử lớn nhất và
phần tử nhỏ nhất.
b) Nếu A là một tập con bất kỳ của N thì A có phần tử nhỏ nhất.
Định lý. (Định lý Pick về diện tích đa giác trên lưới nguyên) Cho P là một đa giác
có đỉnh là các điểm nguyên trên mặt phẳng, khi đó diện tích của P có thể tính bởi
công thức
S(P) = I + B/2 – 1
Trong đó B là số điểm nguyên nằm trên chu vi của đa giác, I là số điểm nguyên
nằm bên trong đa giác.
2. Một số bài tập có lời giải

B là các tập con của X sao cho A không phải là tập con của B và B cũng không
phải là tập con của A.
Lời giải. Có 2n tập con của E. Từ đó số các tập sắp thứ tự (A, B) các tập con của E
là 2n x 2n = 4n. Ta đếm số các bộ (A, B) mà A ⊆ B hoặc B ⊆ A. Ta có
|{(A, B)| A ⊆ B hoặc B ⊆ A }|
= |{(A, B)| A ⊆ B}| + | (A, B)| B ⊆ A } - |{(A, B)| A ⊆ B và B ⊆ A}|.
Rõ ràng
|{(A, B)| A ⊆ B và B ⊆ A}| = |{(A, B)| A = B}| = 2n.
k
Để tính |{(A, B)| A ⊆ B}| ta lý luận như sau: Nếu |B| = k (k=0, 1, …, n) thì có C n
cách chọn B. Sau khi B được chọn, sẽ có 2k cách chọn A. Từ đó
n

| {( A, B ) | A ⊆ B} |= ∑ C nk 2 k = 3 n.
k =0

Từ đó đáp số của bài toán là 4n – 2.3n + 2n.
Bài toán 3. (IMOSL 2007) Với số nguyên dương n > 1 xét S = {1, 2, 3, …, n}. Tô
các số của S bằng 2 màu, u số màu đỏ và v số màu xanh. Hãy tìm số các bộ (x, y,
z) thuộc S3 sao cho


a) x, y, z được tô cùng màu;
b) x + y + z chia hết cho n.
Lời giải.
Cách 1. Gọi R là tập các số được tô màu đỏ và B là tập các số được tô màu xanh.
Nếu x, y, đã được chọn thì có duy nhất một cách chọn z = z x,y sao cho x + y + z
chia hết cho n. Suy ra có n 2 bộ (x, y, z) với x + y + z chia hết cho n. Ta đi đếm các
bộ (x, y, z) với x + y + z chia hết cho n nhưng trong 3 số x, y, z xuất hiện cả hai
màu. Nếu (x, y, z) là một bộ hai màu thì sẽ có hoặc hai số màu đỏ, một số màu

a +b+c

,

3

Nên số các bộ (x, y, z) thuộc S 3 sao cho x, y, z cùng màu và x + y + z chia hết cho
n chính là tổng các hệ số của xn, x2n, x3n trong H(x).
Mặt khác, H(x) = P3(x) + Q3(x) = (P2(x) – P(x)Q(x) + Q2(x))(P(x) + Q(x))
= (P2(x) – P(x)Q(x) + Q2(x))(x + x2 + …+ xn)
Giả sử
G(x) = P2(x) – P(x)Q(x) + Q2(x) = a0 + a1x + … + amxm
Chú ý rằng với mọi số tự nhiên k, tồn tại suy nhất i thuộc (1, 2, …, n) sao cho k+i
chia hết cho n. Do đó tổng các hệ số của x n, x2n, x3n trong H(x) đúng bằng tổng các
hệ số của G(x) và như vậy bằng G(1) = u2 – uv + v2.
Vậy đáp số của bài toán là u2 – uv + v2.
Bài toán 4. Tại một hội nghị có 100 đại biểu. Trong số đó có 15 người Pháp, mỗi
người quen với ít nhất 70 đại biểu và 85 người Đức, mỗi người quen với không
quá 10 đại biểu. Họ được phân vào 21 phòng. Chứng minh rằng có một phòng nào
đó không chứa một cặp nào quen nhau.


Lời giải. Mỗi một người Pháp phải quen với ít nhất 70 – 14 = 56 người Đức. Suy
ra số cặp (Pháp, Đức) quen nhau ít nhất là 15 x 56 = 840.
Gọi n là số người Đức quen ≤ 9 đại biểu người Pháp (gọi là Đ1) thì ta có:
840 ≤ (85-n).10 + n.9. Suy ra n ≤ 10. Những người Đức còn lại (Đ 2) đều quen 10
đại biểu người Pháp, do đó không thể quen với người Đức nữa.
Vì có 21 phòng và chỉ có 15 người Pháp nên có ít nhất 6 phòng chỉ có toàn
người Đức. Vì chỉ có nhiều nhất 10 người Đức có thể quen nhau nên theo nguyên
lý Dirichlet, trong 6 phòng này sẽ có ít nhất một phòng chỉ có nhiều nhất 1 người

cạnh còn lại của đồ thị có số lượng là 17.4/2 – 16 = 18 chỉ có thể nối các đỉnh
ngoài.
Mỗi một trong 18 cạnh này cho chúng ta một chu trình độ dài 5 đi qua X. Vì X là
một đỉnh bất kỳ, qua mỗi một trong 16 đỉnh còn lại cũng có đúng 18 chu trình như
vậy. Mỗi một chu trình đi qua đúng 5 đỉnh, suy ra số chu trình bằng 18.17/5, mâu
thuẫn. Như vậy khẳng định bài toán được chứng minh.
Bài toán 7. (Thanh Hoá 2009) Cho A là một tập hợp gồm 8 phần tử. Tìm số lớn
nhất các tập con gồm 3 phần tử của A sao cho giao của 2 tập bất kì trong các tập
con này không phải là một tập hợp gồm 2 phần tử.
Lời giải. Giả sử ta tìm được n tập hợp con thoả mãn yêu cầu đề bài. Ta chứng
minh rằng một phần tử a bất kỳ thuộc A thuộc không quá 3 tập hợp trong số n tập
hợp con nói trên. Thật vậy, giả sử có 4 tập hợp chứa a là {a, a 1, a2}, {a, a3, a4}, {a,
a5, a6}, {a, a7, a8} thì do ai đều khác a nên phải tồn tại i ≠ j sao cho ai = aj. Không
mất tính tổng quát có thể giả sử i = 1. Nếu j = 2 thì {a, a 1, a2} chỉ có 2 phần tử.
Mâu thuẫn. Nếu j > 2, chẳng hạn j = 3 thì {a, a 1, a2} ∩ {a, a3, a4} = {a, a1}, mâu
thuẫn!
Như vậy mỗi một phần tử thuộc không quá 3 tập hợp. Suy ra số lần xuất hiện của
tất cả các phần tử của A trong các tập con được chọn không quá 3 x 8 = 24 lần. Vì
mỗi một tập con có 3 phần tử nên số tập con không quá 24/3 = 8. Suy ra n ≤ 8.
Ta chứng minh 8 là số lớn nhất bằng cách chỉ ra 8 tập con như vậy. Điều này có
thể làm được khá dễ dàng thông qua bảng sau

1
2
3
4
5
6
7
8

X
X

X
X
X

8

X
X

X
X

X
X

X
X

Bài toán 8. (Nghệ An 2009) Gọi S là tập hợp các số nguyên dương đồng thời thoả
mãn 2 điều kiện sau:
1.Tồn tại 2 phần tử x, y ∈ S sao cho (x, y) = 1
2.Với bất kỳ a, b ∈ S thì a + b ∈ S


Gọi T là tập hợp tất cả các số nguyên dương không thuộc S. Chứng minh rằng số
phần tử của T là hữu hạn và không nhỏ hơn s (T ) , trong đó s(T) là tổng các phần
tử của tập T (nếu T = ∅ thì s(T) = 0).

B, trong đó
B = {(v1, v2, …, vk) ∈ Ekn-k+1| v1 < v2 < …< vk} xác định như sau
f(u1, u2, …, uk) = (v1, v2, …, vk)
với vi = ui – (i-1). Ta kiểm tra (v1, v2, …, vk) ∈ B :


1) Rõ ràng vi+1 – vi = (ui+1 – i) – (ui – (i-1)) = ui+1 – ui – 1 ≥ 1
2) v1 = u1 ≥ 1, vk = uk – (k -1) ≤ n – k + 1.
Ta kiểm tra f là một song ánh. Nếu (u 1, u2, …, uk) ≠ (u1’, u2’, …, uk’) thì rõ ràng
ảnh của chúng khác nhau. Suy ra f là một đơn ánh. Ngược lại, với (v 1, v2, …, vk)
thuộc B, ta chọn ui = vi + i-1 thì (u 1, u2, …, uk) thuộc A và f(u 1, …, uk) = (v1, v2,
…, vk). Suy ra f là toàn ánh.
Vậy |A| = |B|. Mà |B| thì rõ ràng là bằng số các tập con k phần tử của E n-k+1, do đó
bằng C nk− k +1 .
Cách 2. (Sử dụng bài toán chia kẹo của Euler). Giả sử ta chọn được k người. Gọi
x1 là số người tính từng người đầu tiên đến trước người thứ nhất được chọn, x 2 là
số người nằm giữa người thứ nhất và người thứ hai, …, x k là số người nằm giữa
người thứ k-1 và người thứ k và xk+1 là số người nằm sau người thứ k đến cuối.
Khi đó ta có
x1 + x2 + … + xk+1 = n – k
(1)
và x1, xk+1 là các số nguyên không âm, còn x2, …, xk là các số nguyên ≥ 1.
Ngược lại, nếu (x1, …, xk+1) là một nghiệm của (1) với x1, xk+1 ≥ 0, x2, …, xk ≥ 1 thì
ta cho tương ứng với cách chọn người thứ 1+x 1, 2+x1+x2, …, k+x1+…+xk thì rõ
ràng do (i + x1 + …+ xi) – (i-1 + x1 + …+xi-1) = 1 + xi ≥ 2 nên không có 2 người
liên tiếp được chọn.
Để hoàn tất lời giải bài toán, ta đặt y 1 = x1, yk+1 = xk+1 và yi = xi – 1 với i=2, …, k
thì được
y1 + y2 + … + yk+1 = n – 2k + 1
(2)

(k + n − k ) = C nk−−k1−1
(k − 1)!(n − 2k )! k!(n − 2k )! k!(n − 2k )!
k

3. Bài tập tự giải
Bài 1. Hình vuông được chia thành 16 hình vuông con bằng nhau, thu được tập
hợp gồm 25 đỉnh. Hỏi cần phải bỏ đi ít nhất bao nhiêu đỉnh của tập hợp này để
không có 4 đỉnh nào của tập hợp còn lại là đỉnh của một hình vuông với các cạnh
song song với cạnh của hình vuông ban đầu?
Bài 2. (Nghệ An 2009) Cho n là số nguyên dương lớn hơn hay bằng 2. Kí hiệu A
= {1, 2, …, n}. Tập con B của tập A được gọi là 1 tập "tốt" nếu B khác rỗng và
trung bình cộng của các phần tử của B là 1 số nguyên. Gọi T n là số các tập tốt của
tập A. Chứng minh rằng Tn – n là 1 số chẵn.
Bài 3. (Vũng Tàu 2009) Trên bàn cờ vua kích thước 8x8 được chia thành 64 ô
vuông đơn vị, người ta bỏ đi một ô vuông đơn vị nào đó ở vị trí hàng thứ m và cột
thứ n. Gọi S(m;n) là số hình chữ nhật được tạo bởi một hay nhiều ô vuông đơn vị
của bàn cờ sao cho không có ô nào trùng với vị trí của ô bị xóa bỏ ban đầu. Tìm
giá trị nhỏ nhất và giá trị lớn nhất của S(m;n).
Bài 4. Ba nhóm đường thẳng song song chia mặt phẳng thành N miền. Hỏi số
đường thẳng của cả 3 nhóm ít nhất là bao nhiêu để N > 1981.
Bài 5. (Nghệ An 2009) Cho 9 điểm nguyên trên mặt phẳng tọa độ, không có 3
điểm thẳng hàng. Chứng minh ta luôn chọn được 3 điểm thỏa mãn diện tích của
tam giác tạo bởi chúng là số chẵn.
Bài 6. (Nga 2007, Bắc Ninh 2009) Trong bảng hình vuông gồm 10 x 10 ô vuông
(10 hàng, 10 cột), người ta viết vào các ô vuông các số tự nhiên từ 1 đến 100 theo
cách như sau: ở hàng thứ nhất, từ trái sang phải, viết các số từ 1 đến 10; ở hàng
thứ hai, từ trái sang phải, viết các số từ 11 đến 20; cứ như vậy cho đến hết hàng
thứ 10. Sau đó cắt bảng hình vuông thành những hình chữ nhật cỡ 1 x 2 hoặc 2 x
1. Tính tích số của hai số trong mỗi hình chữ nhật rồi cộng 50 tích lại. Cần phải
cắt hình vuông như thế nào để tổng tìm được nhỏ nhất ?

a + b + c + d + e + f = 27
(a, b, c, d, e, f) ∈ N6
trừ đi số phần tử của N = Na ∪ Nb ∪ Nc ∪ Nd ∪ Ne ∪ Nf, trong đó
Na = { (a, b, c, d, e, f) ∈ N6, a + b + c + d + e + f = 27, a ≥ 10}
(Nb, Nc, Nd, Ne, Nf định nghĩa tương tự).
4. Đáp số, hướng dẫn, lời giải