SỬ DỤNG ÁNH XẠ TRONG CÁC BÀI TOÁN TỔ HỢP
MÃ: TO10

1. Lý thuyết.
1.1. Định nghĩa.
+ Cho hai tập hợp X và Y (khác rỗng). Một ánh xạ f từ X lên Y là một quy tắc cho
tương ứng mỗi phần tử x∈X với một và chỉ một phần tử y = f(x)∈Y.
+ Tập X gọi là tập nguồn, tập Y gọi là tập đích.
+ Ánh xạ f được gọi là đơn ánh nếu với mọi x1, x2∈X, f(x1) = f(x2) ⇒ x1 = x2.
(Hay nếu với mọi x1, x2∈X, x1 π x 2 fi f (x 1 ) π f (x 2 ))
+ Ánh xạ f được gọi là toàn ánh nếu với mọi y∈Y, ∃x∈X sao cho f(x) = y.
+ Ánh xạ f được gọi là song ánh nếu f vừa là đơn ánh vừa là toàn ánh.
1.2. Định lí 1.
Với A, B là các tập hợp hữu hạn. Xét f là một ánh xạ đi từ A vào B
• Nếu f là đơn ánh thì |A| ≤ |B|
• Nếu f là toàn ánh thì |A| ≥ |B|
• Nếu f là song ánh thì |A| =|B|
1.3. Định lí 2.
Cho 2 tập hợp A và B có n phần tử, số lượng song ánh f: A Æ B là n!.
2. BÀI TẬP ÁP DỤNG
Bài 1. Cho k, n là các số nguyên dương. Tìm số nghiệm nguyên không âm của
phương trình : x 1 + x 2 + ... + x k = n

(*)
( Bài toán chia kẹo của EULER )

Lời giải

1




Dễ dàng chứng minh được f là một song ánh.
Vậy số nghiệm của phương trình (*) sẽ tương ứng với số dãy nhị phân nhị phân có
độ dài n + k -­‐ 1 gồm k -­‐ 1 bit 0 và n bit 1. Mặt khác mỗi dãy nhị phân tương ứng
với một cách chọn k -­‐ 1 vị trí cho bit 0 nên số dãy nhị phân thoả mãn là C nk +-­‐ 1k -­‐ 1 .
Bài 2. Có bao nhiêu số nguyên dương có dạng abcde

thỏa mãn:

a £ b
(-­‐ 1)n
Vậy số cách phân phối thoả mãn đầu bài là: n ![1 -­‐
+ -­‐ ... +
].
2! 3!
n!
Bài 5. Cho A = {a1 , a2 ,..., an } , (2 £ n Œ• ). Gọi H là tập hợp gồm các hoán vị của
A mà trong mỗi hoán vị đó phần tử ai không nằm ở vị trí thứ i. Tính H .
Lời giải
Ta phát biểu lại bài toán:
Tìm tất cả các song ánh f : A Æ A sao cho không tồn tại i để

f (ai ) = ai , " i Œ{1;2;...; n }.
Ta có số song ánh f : A Æ A là n !
Gọi Ai là tập hợp các song ánh f : A Æ A mà f (ai ) = ai .

3


Dễ thấy: Ai = (n -­‐ 1) !; Ai « Aj = (n -­‐ 2) !;...; A1 « A2 « ... « An = 1
Theo nguyên lí bù trừ, ta có:
n

H = n !-­‐ C n1 (n -­‐ 1) !+ C n2 (n -­‐ 2)!-­‐ ... + (-­‐ 1) C nn (n -­‐ n )!
Bài 6. (VMO - 2012 ) Cho một nhóm gồm 5 cô gái, kí hiệu là G1,G2 ,G3 ,G4 ,G5 , và
12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm
người đã cho ngồi vào các chiếc ghế đó sao cho các điều kiện sau được đồng thời
thỏa mãn:
a/ Mỗi ghế có đúng một người ngồi;
b/ Thứ tự ngồi của các cô gái, xét từ trái qua phải, là G1,G2 ,G3 ,G4 ,G5 ;

B = (g1, g2, g3, g 4 , g5 ) | 1 £ g1 < g2 < g3 < g 4 < g5 £ 17, 3 < g2 -­‐ g1 ;1 < g5 -­‐ g 4
1

2

3

4

5

Để tính |B|, ta đặt D =

1

2

3

4

5

{(h , h , h , h , h ) | 1 £ h
1

2

3



 m (X )
T

ở đây tổng lấy theo tất

cả các tập hợp X thuộc T. Hãy tính giá trị của m.
Lời giải
Cách

1:

{

Xây

dựng

song

ánh

f:

}

T ÆT

(



)

2003 22002 -­‐ 1
Ê2003 ˆ˜ 2002 k
˜˜ . C 2002 =
=Á
Á
Á
2
Ë 2 ¯ˉ˜ k =1

Ê m (X )ˆ˜
ÁÂ
˜˜ = 2003
-­‐ 1 . Vì vậy: m = Á
Á
˜
Á
2
Á
Ë T
¯ˉ˜˜

Bài 8. Hãy trung bình cộng tất cả các số N = a1a2 ...an chia hết cho 99 và các chữ số
của N thuộc tập {1, 2, 3, 4, 5, 6, 7, 8}.
Lời giải
Gọi T là tập tất cả các số dạng. Khi đó xét tương ứng f: T → T

a1a2 ...an → b1b2 ...bn

6


Đặt A = {tập các chỉnh hợp chập k của (1,2,...,n)};
A* = {tập các chỉnh hợp thoả mãn giả thiết};
B = { (a1 , a2 ,..., ak )∈A ⎢a1 < a2

 a ≥ 233 € Â

a ŒB

a ŒA \B

(2)

Hiển nhiên f là song ánh, suy ra: S = D
Từ (1), (2) fi S =

N
2

=

230
= 229 .
2

7

a ≥ 233 € A \ B ŒD


3. MỘT SỐ BÀI TẬP TƯƠNG TỰ
Bài 1. Cho n người xếp thành một hàng dọc. Hỏi có bao nhiêu cách chọn ra k người
sao cho 2 người liên tiếp không được chọn (với n > 2k).
Bài 2. Cho X = {1, 2, ..., 2008}. Hỏi có bao nhiêu tập con A của X có tính chất: A

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,
NXB Đại học Quốc Gia Hà Nội.

3.

Nguyễn Văn Thông (Chủ biên), Nguyễn Văn Hiếu, Nguyễn Văn Minh (2013),
Bồi dưỡng học sinh giỏi luyện giải đề trước kỳ thi vào lớp 10 ba miền Bắc Trung - Nam môn Toán, NXB Đại học Quốc Gia Hà Nội.

4.

Tủ sách toán học & tuổi trẻ (2007), Các bài thi Olympic Toán Trung học phổ
thông Việt Nam 1990 - 2006, NXB Giáo dục.

5.

Tuyển tập 30 năm Toán học tuổi trẻ, NXB Giáo dục, 2004.

9