PHƯƠNG PHÁP ÁNH XẠ TRONG CÁC BÀI TOÁN TỔ HỢP
MÃ: TO06

1. Ánh xạ, đơn ánh, toàn ánh và song ánh
+ Một ánh xạ f từ tập X đến tập Y là một quy tắc đặt tương ứng mỗi phần tử x
thuộc X một (và chỉ một) phần tử y của Y. Phần tử y này gọi là ảnh của x qua ánh xạ f và
được kí hiệu là y  f ( x) . Khi đó người ta thường viết f : X  Y .
+ Ánh xạ f : X  Y được gọi là đơn ánh nếu với mọi a, b thuộc X mà a  b thì

f (a)  f (b) , tức là hai phần tử phân biệt có ảnh phân biệt.
Từ đó suy ra ánh xạ f là đơn ánh khi và chỉ khi với mọi a, b thuộc X mà

f (a)  f (b) thì a  b .
+ Ánh xạ f : X  Y được gọi là toàn ánh nếu với mọi y thuộc Y đều tồn tại x
thuộc X sao cho f ( x)  y.
+ Ánh xạ f : X  Y được gọi là song ánh nếu nó vừa là đơn ánh, vừa là toàn ánh.
Như vậy ánh xạ f : X  Y là song ánh khi và chỉ khi với mọi y thuộc Y đều tồn tại
duy nhất x thuộc X sao cho f ( x)  y.

2. Một số kết quả thường dùng
Cho X và Y là hai tập hợp hữu hạn, khác rỗng và f : X  Y là một ánh xạ. Khi đó ta có
+ Nếu f là đơn ánh thì X  Y .
+ Nếu f là toàn ánh thì X  Y .
+ Nếu f là song ánh thì X  Y .

3. Phương pháp ánh xạ trong bài toán đếm
Phương pháp ánh xạ trong bài toán đếm dựa vào ý tưởng như sau:
1


Nếu tồn tại một song ánh từ X vào Y thì X  Y (với X, Y là các tập hữu hạn). Như

B2  C2 , hay B  C .
+ Ta chứng minh f là toàn ánh:
2


Giả sử M  D là một tập con của A có n phần tử. Kí hiệu M 1 , M 2 tương ứng là tập các số
chẵn và tập các số lẻ của M. Đặt B1  M1 , B2  Y \ M 2 và B  B1  B2 . Ta có

B1  M1 ; B2  Y  M 2  n  M 2  M  M 2  M 1 .
Suy ra B1  B2 , tức B là tập cân. Rõ ràng f ( B)  B1  Y \ B2   M 1  M 2  M .
Như vậy ta đã chứng minh được f là song ánh. Do đó số các tập cân của A bằng số các
tập con có n phần tử của A. Vậy A có tất cả là C2nn tập cân.
Ví dụ 2 (Bài toán chia kẹo của Euler). Cho k, n là các số nguyên dương. Khi đó số
nghiệm nguyên không âm của phương trình
x1  x2 

 xk  n

(1)

là Cnkk11 .
Lời giải
Gọi A là tập hợp tất cả các nghiệm  x1 , x2 ,..., xk  của phương trình (1). Gọi B là tập hợp
tất cả các xâu nhị phân độ dài n  k  1 với n số 1 và k  1 số 0.
Xét ánh xạ f : A  B theo quy tắc  x1 , x2 ,..., xk 

1..101..101......01..1 như sau:

Trong đó có x1 số 1 liên tiếp rồi đến một số 0, sau đó đến x2 số 1 liên tiếp rồi lại đến một
số 0,…, cuối cùng là xk số 1 liên tiếp.

S  1;2; ; n

hoán vị

f của

S

thỏa mãn
thỏa

mãn

f (i)  i  1, i  1, 2,..., n. Chứng minh En  Cn .

Hướng dẫn

g với g (i)  n  1  f (n  i  1) .

Thiết lập song ánh f

Ví dụ 5. Cho n là một số nguyên dương. Giả sử M là tập tất cả các số nguyên dương viết
trong hệ thập phân có n chữ số 1, n chữ số 2 và không có chữ số nào khác; N là tập tất cả
các số nguyên dương viết trong hệ thập phân gồm n chữ số, chỉ chứa các chữ số 1, 2, 3, 4
và số các số 1 bằng số các số 2. Chứng minh rằng M = N.
Hướng dẫn
Thiết lập ánh xạ f : M  N như sau, với mỗi x  a1a2 ...anb1b2 ...bn  M cho ứng với

y  c1c2 ...cn , với ci  ai * bi được xác định theo quy tắc
1*1  1,

một người thuộc A. Vậy tồn tại một song ánh đi từ A đến B, tức a và b có số người quen
bằng nhau.
Nếu a không quen b thì tồn tại c quen cả a và b. Khi đó theo lập luận bên trên thì số người
quen của a và b bằng nhau vì cùng bằng số người quen của c. (đpcm)
Ví dụ 7 (VMO – 2002). Cho tập S gồm tất cả các số nguyên trong đoạn 1;2014 . Gọi T là
tập hợp tất cả các tập con không rỗng của S. Với mỗi X thuộc T, kí hiệu m(X) là trung
bình cộng các phần tử của X. Tính

m

 m( X )

T
trong đó tổng lấy theo tất cả các tập X thuộc T.
Lời giải
Xây dựng ánh xạ f : T  T như sau: f ( X )  2015  x | x  X  , X  T .
Dễ dàng chứng minh ánh xạ trên là song ánh.Rõ ràng có
5


m( X )  m( f ( X ))  2015 .
Do đó

2 m( X )    m( X )  m  f ( X )    T .2015  m 

 m( X )  2015 .
T

2


Ví dụ 10 ( IMO 1989). Cho n là một số nguyên dương. Một hoán vị  x1 , x2 ,

1;2;

tập

;2n được gọi là có tính chất P nếu

, x2 n  của

xi  xi 1  n với ít nhất một

i  1;2; ;2n  1 . Chứng minh rằng với mỗi số nguyên dương n, số các hoán vị có tính
chất P nhiều hơn số hoán vị không có tính chất đó.
Hướng dẫn
Đặt A là tập tất cả các hoán vị của 1;2; ;2n , B là tập tất cả các hoán vị của

1;2;

;2n có tính chất P và C là tập tất cả các hoán vị của 1;2; ;2n không có tính

chất P.
Ta chia các số 1, 2, …, 2n thành n cặp (1 ; n), (2 ; n+1),…, (n ; 2n).
Giả sử x   x1 , x2 ,..., xk 1, xk , xk 1,...x2 n   C , và giả sử xk cùng cặp với x2n , suy ra

k  2n  2 . Xét ánh xạ f : C  B như sau:
x   x1 , x2 ,..., xk 1, xk , xk 1,...x2n   C

x '   x1, x2 ,..., xk 1, xk , x2 n , x2 n1,..., xk 1   B .




X 1  x1 , x2 ,..., xn2 , X 2  xn2 1 ,..., x2 n2 , X 3  x2 n2 1 ,..., x3n2 .
Xét ánh xạ f : X 1  X 2  X 3  E  E , (a, b, c)

 b  a, c  b  .

Ta có X1  X 2  X 3  n6 . Do a  X 1 , b  X 2 , c  X 3 nên a < b < c, suy ra

b  a  1, c  b  1 và (b  a)  (c  b)  c  a  n3 .
Vì vậy tập ảnh f là tập con của tập A với A   m; n  | m, n  X , m  n  n3 . Mà ta có
n3 1

A  k 
k 1

n3 (n3  1) n 6

2
. 2

Do đó theo nguyên lí Dirichlet, tồn tại ba bộ số  ai , bi , ci  , i  1,2,3 cho cùng một ảnh

 x0 ; y0  , nghĩa là ta có
bi  ai  x0 , ci  bi  y0 ;

i  1, 2,3.

Chọn z0   x0  y0 thì z0  ai  ci , i  1, 2,3.
Do vậy với mỗi i  1, 2,3 ta có

minh rằng Tn  n là một số chẵn.
Bài 5 (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:
1/ Mỗi ghế có đúng một người ngồi;
2/ 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;
3/ Giữa G1 và G2 có ít nhất 3 chàng trai;
4/ Giữa G4 và G5 có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.

9


Hỏi có tất cả bao nhiêu cách xếp như vậy?
(Hai cách xếp được coi là khác nhau nếu tồn tại một chiếc ghế mà người ngồi ở chiếc ghế
đó trong hai cách xếp là khác nhau).
Bài 6. Người ta xếp n nam sinh và n nữ sinh thành một hàng, sau đó tách 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ể
tách hàng theo yêu cầu trên, B là số trường hợp chỉ có thể tách hàng theo yêu cầu trên một
cách duy nhất.
Chứng minh rằng B  2 A .
Bài 7. Hãy tính trung bình cộng tất cả các số n gồm 2016 chữ số thỏa mãn n 99 và các
chữ số của n thuộc 1;2;3;4;5;6;7;8 .
Bài 8 (IMO – 1987). Gọi pn ( k ) là số hoán vị của tập 1, 2,..., n có đúng k điểm cố định.
Chứng minh rằng
n

 k . p (k )  n !
k 0