SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI
Đơn vị:Trường THPT Chuyên Lương Thế Vinh
Mã số:
(Do HĐKH Sở GD&ĐT ghi)
SÁNG KIẾN KINH NGHIỆM
MỘT SỐ PHƯƠNG PHÁP GIẢI
ĐẾM NÂNG CAO
Người thực hiện: NGUYỄN TẤT THU
Lĩnh vực nghiên cứu:
- Quản lý giáo dục 
- Phương pháp dạy học bộ môn: Toán học 

- Lĩnh vực khác: 

Có đính kèm: Các sản phẩm không thề hiện trong bản in SKKN
 Mô hình  Phần mềm  Phim ảnh  Hiện vật khác
Năm học: 2013 – 2014
SƠ LƯỢC LÝ LỊCH KHOA HỌC
I. THÔNG TIN CHUNG VỀ CÁ NHÂN
1. Họ và tên: Nguyễn Tất Thu
2. Ngày tháng năm sinh: 13-09-1980
3. Nam, nữ: Nam
4. Địa chỉ: Tổ 10 – KP5 - Trảng Dài – Biên Hoà - Đồng Nai
5. Điện thoại: (CQ)/ (NR); ĐTDĐ:0942444556
6. Fax: E-mail:
7. Chức vụ: Giáo viên
8. Đơn vị công tác: Trường THPT Chuyên Lương Thế Vinh
II. TRÌNH ĐỘ ĐÀO TẠO
- Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Thạc sĩ
- Năm nhận bằng: 2013
- Chuyên ngành đào tạo: Lí luận và phương pháp dạy học bộ môn Toán

A B≤

•
Nếu
f
là toàn ánh thì
A B≥
•
Nếu
f
là song ánh thì
A B=
Do đó thay vì đếm số phần tử của
A
, ta đi đếm số phần tử của
B
.
Ví dụ 1. Cho
{ }
1 2 n
X a ,a , ,a=
với
n
là số tự nhiên dương, k là số tự nhiên thỏa
k n≤
.
Đặt
{ }
1 2 k 1 2 k
i i i i i i 1 2 k

có thể bằng nhau.
Do đó, ta tìm các phá bỏ các dấu “=” ở trong bất đẳng thức
1 2 k
1 i i i n≤ ≤ ≤ ≤ ≤
.
Tức là, ta đưa về đếm các bộ
( )
1 2 k
j ,j , ,j
với
1 2 k
1 j j j n≤ < < < ≤
. Để thực hiện
được điều đó, ta tịnh tiến các chỉ số
1 2 k
i ,i , ,i
mỗi chỉ số tăng thêm một đơn vị
so với chỉ số trước nó. Dẫn tới, ta đi xét tương ứng sau
Xét tương ứng
( ) ( )
1 2 k 1 1 2 k
i ,i , ,i S i ,i 1, ,i k 1∈ → + + −
. Rõ ràng, đây là một
song ánh từ
1
S
và tập
2
S
là tập gồm các bộ

k 1
n 1
C
−
−
.
Ví dụ 2. Trong một giải bóng đá có 10 trận đấu và được diễn ra trong vòng 30
ngày. Hỏi ban tổ chức có bao nhiêu cách sắp xếp các trận đá bóng sao cho hai
trân đấu kế nhau phải cách nhau ít nhất một ngày.
Lời giải.
Cách 1:
Giả sử trận đấu thứ
i
được xếp vào ngày
i
x
. Khi đó, mỗi cách xếp các trận đấu
tương ứng với một bộ 10 số
( )
1 2 10
x ,x , ,x
thỏa các điều kiện sau
•
1 2 3 10
1 x x x x 30≤ < < < < ≤
•
i 1 i
x x 2
+
− ≥

x
có thể là hai số tự
nhiên liên tiếp.
Dẫn đến, ta sẽ chuyển bộ
( )
1 2 10
x ,x , ,x
về bộ
( )
1 2 3 10
x ,x 1,x 2 ,x 9− − −
.
Gọi
A
là tập các bộ
( )
1 2 10
x ,x , ,x
thỏa mãn các điều kiện trên

( )
{ }
1 10 1 2 10
B y , ,y 1 y y y 21= ≤ < < < ≤
Xét ánh xạ
f : A B→
được xác định như sau
( ) ( )
1 10 1 2 3 10
f x , ,x x ,x 1,x 2, ,x 9= − − −

1 2 11
x x x 30 10 20+ + + = − =
Đặt
1 1 11 11 i i
y x ,y x ,y x 1, i 2,10= = = − ∀ =
Khi đó, mỗi bộ
( )
1 2 11
x ,x , ,x
tương ứng với một bộ
( )
1 2 11
y ,y , ,y
thỏa
1 2 11
y ,y , ,y 0≥
và
1 2 11
y y y 11+ + + =
(*).
Số các bộ
( )
1 2 11
y ,y , ,y
chính là số nghiệm không âm của phương trình (*) và
bằng
11 11
11 11 1 21
C C
+ −

1 i i i 2013≤ < < < ≤
•
k 1 k
i i 4
+
− ≥
với
k 1,2012∀ =
và
1 2013
2013 i i 4+ − ≥
.
Ta thấy
k 1 k k 1 k k 1 k
i i 4 i i 3 i 3 i
+ + +
− ≥ ⇔ − > ⇔ − >
, do đó ta sẽ thay thế các
k
i

bởi
k
i 3(k 1)− −
.
Gọi
S
là tập các bộ
( )
1 2 100

{ }
1
a 1,2,3∈
, đặt
i i 1
b a a= −
. Khi đó, ánh xạ
g
đi từ
1
S
và tập
2
S
là tập các
bộ
( )
1 2 100
b ,b , ,b
thỏa
2 3 100
1 b b b 1712≤ < < < ≤
là một song ánh. Ta có
99
2 1712
S 3.C=
.
•
1
a 4≥

k (a ,a , ,a )
của
n
số tự nhiên đầu
tiên thỏa ít nhất một trong hai điều kiện sau
i) Tồn tại
{ }
i,j 1,2, ,k∈
thỏa
i j
a a>
và
i j<
ii) Tồn tại
{ }
i 1,2, ,k∈
sao cho
i
a i−
là số lẻ.
Lời giải.
Gọi
S
là tập các chỉnh hợp chập
k
của
n
số tự nhiên đầu tiên. Ta có
k
n

A S B= −
.
Ta đi tính
B ?=
Với mỗi bộ
{ }
1 2 k
(a ,a , ,a ) 1,2,3, ,n⊂
thì tồn tại duy nhất một chỉnh hợp chập
1 2 k
k (a ,a , ,a )
thỏa điều kiện (a). Do đó, ta chỉ cần đi phân tích điều kiện (b)
Vì
i
a i−
là số chẵn khi và chỉ khi
i
a i+
là số chẵn. Hơn nữa giá trị của
i
a i−
ta
khó kiểm soát còn các giá trị của
i
a i+
chỉ thuộc vào tập
{ }
1,2,3, ,k n+
nên ta
xét ánh xạ

Ta chứng minh được
f
là song ánh.
Vì vậy
k
n k
2
B C C
 + 
 
 
= =
.
Vậy
k k
n
n k
2
A C C
 + 
 
 
= −
.
Ví dụ 5. Cho một tam giác đều cạnh bằng
n
. Chia tam giác này thành
2
n
tam

S S S= =
và
BC
S 3 S=
.
Ta đi tính
BC
S ?=
.
Trên các tia
AB,AC
kéo dài ta lấy các điểm
B',C'
sao cho
BB' CC' 1= =
.
Ta chia đoạn
B'C'
thành
n 1
+
đoạn bằng nhau
1 1 2 n
B'A ,A A , ,A C'
Với mỗi hình bình hành thuộc
BC
S
, ta kéo dài các cạnh của hình bình hành, cắt
B'C'
tại 4 điểm phân biệt thuộc vào tập các điểm

=
.
Vậy
4
n 2
S 3C
+
=
.
Ví dụ 6. Cho A là tập hữu hạn các số thực dương. Ta định nghĩa B và C là các
tập sau
{ }
x
B x,y A , C xy x,y A
y
 
= ∈ = ∈
 
 
.
Chứng minh rằng
2
A . B C≤
.
Lời giải.
Giả sử
k
1 2
1 2 k
x

Xét
j
i
i j
x
x
a z; , b z';
y y
 
 
 ÷
= =
 ÷
 ÷
 
 
mà
f(a) f(b)=
, ta có:
i j i j
j
i
i j i ji j
x z x z' x x
x
x
z z' a b
y z y z' y y
y y
 = =

1 2 k
X ,X , ,X
.
Ví dụ 1. Cho tập hợp
A
có
n (n 1)≥
phần tử. Hãy tính số tập con của tập
A
.
Lời giải.
Gọi
n
S
là tập hợp gồm tập con của tập
{ }
A 1,2,3, ,n=
và
n n
a S=
. Ta phân
hoạch tập
n
S
thanh hai tập
X
gồm các tập con chứa
n
và
Y

n 1 n 1
X S a
− −
= =
.
•
Tính
Y
Vì mỗi tập con
H
thuộc
Y
, ta có
H
không chứa
n
nên
H
là một tập con của tập
{ }
1,2, ,n 1−
và ngược lại. Do đó,
n 1 n 1
Y S a
− −
= =
.
Suy ra
n 1 n
n n 1 n 1 n 1 1

0
trong xâu
kí tự là số chẵn.
Lời giải. Đặt
n
A
là số xâu kí tự có độ dài
n
mà số lần xuất hiện của số 0 là số
chẵn và
n n
a A=

Ta thấy
1
a 9=

Vì có
n
10
xâu kí tự có độ dài
n
nên số xâu kí tự độ dài
n
mà trong đó số xuất
hiện của chữ số 0 là số lẻ bằng
n
n
10 a−
.

−
−
= −
.
Ta tính
Y

Với
1 2 n
x a a a Y= ∈
thì xâu
2 3 n
a a a
có độ dài
n 1
−
và số lần xuất hiện của số 0
là số chẵn. Do đó, có
n 1
a
−
xâu
2 3 n
a a a
như vậy. Với mỗi xâu
2 3 n n 1
a a a A
−
∈


của tập
{ }
1,2,3, ,n
sao cho tồn tại
duy nhất một chỉ số
i
sao cho
i i 1
a a
+
>
.
Lời giải. Gọi
n
S
là tập các hoán vị
1 2 n
(a ,a , ,a )
của tập
{ }
1,2,3, ,n
sao cho tồn
tại duy nhất một chỉ số
i
sao cho
i i 1
a a
+
>
và đặt

này là
Y

+)
i
a n=
và
j j 1
a a , j i
+
< ∀ ≠
, gọi tập các hoán vị thuộc dạng này là
Z
.
Khi đó tập
n
S
được phân hạch thành ba tập
X,Y,Z
nên
n
S X Y Z= + +
.
Dễ thấy
n 1
X x
−
=

Với mỗi hoán thuộc tập

n 1
Y x
−
=

Với mỗi hoán vị thuộc tập
Z
ta rút
i
a
ra thì ta thu được hoán vị
( )
1,2,3, ,n 1−

và với mỗi hoán vị này, ta có
n 1−
cách chèn
n
vào. Do đó
Z n 1= −
.
Do đó
n n 1 n 1 n 1
x x x n 1 2x n 1
− − −
= + + − = + −
và
2
x 1=
.

và
n n
a A=

Ta có
1 2
a 0,a 1= =
.
Vì
( ) ( )
n A A 1 , n 1 A A 1∈ ∪ + + ∉ ∪ +
nên
n A∉
và
n 1 A− ∈
. Do đó, ta chia tập
n
X
thành hai tập rời nhau
{ }
n n
Y A X n 2 A= ∈ − ∈
và
{ }
n n
Z A X n 2 A= ∈ − ∉
.
+) Tính
n
Y

n n 2
Z a
−
=
.
Do đó, ta có
n n 1 n 2
a a a
− −
= +
. Từ đây ta tìm được
n 1 n 1
n
1 1 5 1 5
a
2 2
5
− −
 
   
+ −
 
= −
 ÷  ÷
 ÷  ÷
 
   
 
 
.

là tập gồm các
thẻ được chọn trong đó có thẻ ghi số
n
. Khi đó
n
a A B= +
.
•
Tính
A
Xét ánh xạ
n 1
f : A S , f(x) x
−
→ =
là một song ánh. Do đó
n 1
A S
−
=
•
Tính
B
Ta phân hoạch
B
thành hai tập rời nhau
1
B
và
2

hơn số thẻ được chọn. Số cách chọn trong trường hợp này là
n 1
a
−
.
• Thẻ ghi số
n
được chọn
+) Nếu chỉ chọn 1 thẻ ghi số
n
thì có 1 cách chọn
+) Nếu chọn ít nhất hai thẻ thì thẻ ghi số
1
sẽ không được chọn và các thẻ được
chọn còn lại (khác thẻ ghi số
n
) gồm các thẻ ghi số từ
2
đến
n 1
−
, ta trừ đi mỗi
số ghi trên các thẻ này 1 đơn vị thì ta được các thẻ ghi từ số 1 đến
n 2
−
. Do đó,
trường hợp này có
n 2
a 1
−

a
thuộc
A
với mọi
i 1,2, ,n=
2)
i i 1
a a
+
−
thuộc
A
với mọi
i 1,2, ,n 1= −
.
Lời giải.
Gọi
n
S
là tập các bộ
1 1 n
(a ,a , ,a )
. Ta phân hoạch tập
n
S
thành ba tập rời nhau
{ }
1n 1 n n n
(a ,a , A ,a ) S a 1∈= =


. Ngược lại với mỗi bộ thuộc
n 1
A
−
hoặc
n 1
B
−
ta có thể thêm vào cuối số 1 hoặc số 0 để thu được một dãy
thuộc
n
A
. Do đó, ta có
n n 1 n 1
x x y
− −
= +

Tương tự, ta có
n n 1 n 1 n 1 n 1
y x y z u
− − − −
= + + =
và
n n 1 n 1
z z y
− −
= +

Do đó

n
chữ số được lập từ các chữ số
3,4,5,6
. Ta có
n
A 4=
.
Vì một số tự nhiên khi chi cho 3 chỉ có 3 số dư là 0,1,2 nên ta chia tập A thành 3
tập rời nhau
n n n
A ,B ,C
theo thứ tự là gồm các
x A
∈
mà số dư của
x
khi chia
cho 3 là 0, 1, 2.
Ta cần tìm
n n
x A=
, đặt
n n n n
y B , z C= =
, ta có
n
n n n
x y z 4+ + =
.
Xét một số

n 1
x
−
số.
+) Nếu
n
a 5=
, khi ta bỏ
n
a
, ta thu được một số có
n 1
−
chữ số thuộc tập
n 1
B
−

và mỗi số thuộc
n 1
B
−
, ta thêm vào cuối chữ số 5 ta thu được một số thuộc
n
A
.
Trường hợp này có
n 1
y
−

n
. Kí hiệu
T
là tập hợp
2n
số
nguyên dương đầu tiên. Hỏi có tất cả bao nhiêu tập con
S
của
T
có tính chất:
Trong
S
không tồn tại các số
a,b
mà
{ }
a b 1;n− ∈
. ( Tập rỗng được coi là một
tập có tính chất trên).
Lời giải.
1
2

n 1−
n
n 1+
n 2+

2n 1−

.
•
Tính
n
a

Gọi
n
x
là số cách chọn một số ô thỏa (*) từ bảng chữ nhật khuyết đơn
2 n
×
(ở
hình 2)

x(Hình 2)
Ta có các cách chọn thỏa (*) gồm:
+)
n 1
a
−
cách chọn mà ô ở cột thứ nhất không được chọn.
+)
n 1
2x
−
cách chọn mà trong mỗi cách chọn thì ô thuộc cột thứ nhất được chọn.

n n 1 n 2
a 2a a n 3
− −
= + ∀ ≥
và ta có
1 2
a 3,a 7= =
nên
( ) ( )
n 1 n 1
n
1
a 1 2 1 2
2
+ +
 
= + + −
 
 
.
•
Tính
n
b

Ta có
1 2 3
b 0,b b 1= = =

A

B
đều không được chọn.
+)
n 2
2x
−
cách chọn mà mỗi cách chọn thì một trong hai ô A, B được chọn.
+)
n 2
y
−
cách chọn mà mỗi cách chọn thì ccar hai ô A và B đều được chọn.
Do đó
n n 2 n 2 n 2 n 1 n 2 n n n 2 n 2
y a 2x y a y 2y a 2y a
− − − − − − −
= + + = + ⇒ − = −

Suy ra
( )
n
n n
2y a 1− = −
Do đó
( )
n 2
n 2
n n 2
a 1
b y

 
.
2.3. Đếm bằng công thức bao hàm và loại trừ
Với
n
tập hữu hạn
1 2 n
A ,A , ,A
ta có:
n
n 1
1 2 n k i j 1 2 n
k 1 1 i j n
A A A A A A ( 1) A A A
−
= ≤ < ≤
∪ ∪ ∪ = − ∩ + + − ∩ ∩ ∩
∑ ∑
Ví dụ 1. Ta gọi A là tập hợp “đầy đặn” nếu A chứa đúng 5 số thực và bất kì
phần tử
x
nào của A thì
x 1
−
hoặc
x 1
+
cũng thuộc A. Tìm số tập hợp đầy đặn
là tập con của
{ }

1 2 1 2
S S S S S= + − ∩
.
*Tính số phần tử của tập hợp
1
S .
Xét một tập hợp đầy đặn
{ }
A a,b,c,d,e=
thuộc
1
S
, dễ thấy
a,b,c
là các số liên
tiếp nên ta sẽ đếm số giá trị
a
thỏa mãn. Do điều kiện (*) nên
1 a 2008≤ ≤
. Hơn
nữa, ứng với mỗi cách chọn của
a,
số
d
nhận giá trị tùy ý từ
a 3+
đến 2011 nên
có
2009 a−
cách chọn

A a,b,c,d,e S= ∈
thì
tập hợp tương ứng với nó sẽ là
{ }
2 2
A 2013 a,2013 b,2013 c,2013 d,2013 e S= − − − − − ∈
.
Suy ra
2 1
S S=
.
*Tính số phần tử của tập hợp
1 2
S S∩
.
Dễ thấy đây là các tập hợp chứa 5 phần tử liên tiếp và như thế, với mỗi cách
chọn
a
sẽ tạo thành một tập hợp đầy đặn thuộc
1 2
S S .∩
Số cách chọn đó chính
là 2008 do
1 a 2008.≤ ≤
Vậy
( )
2
2008 2009
S 2 2009 2008 2008 2008 2 2009 2009 1 2008 .
2

     
     

2014
A B 335, B C 95, C A 143, A B C 47
2.3
 
∩ = = ∩ = ∩ = ∩ ∩ =
 
 

Do đó
A B C 1007 671 287 335 95 143 47 1439∪ ∪ = + + − − − + =
.
Ví dụ 3. Trong một thư viện người ta quan sát trong một tháng thấy được
i) Mỗi ngày có 5 người đến đọc sách
ii) Hai ngày bất kì thì số người đến đọc sách là 9
Hãy tính xem trong 1 tháng có bao nhiêu người đến đọc sách. Biết tháng đó có
30 ngày.
Lời giải. Bài toán tương đương với bài toán sau:
Cho các tập
i
A , i 1,30=
thỏa:
i i j
A 5, A A 9, i j= ∪ = ∀ ≠
. Tính
30
i
i 1

Nếu
k 29≤
, suy ra tồn tại
m
A
sao cho
m
a A∈
với
m k 1≥ +
.
Khi đó, tồn tại
j m i
b A A , i 1,2, ,k∈ ∩ =
và
j i
b b≠
với mọi
i j≠
Suy ra
m
A k 5≥ >
trái với giả thiết. Do đó
30 30
i i
i 1 i 1
{a} A A 1
= =
= ⇒ =
I I

i
i 1
A 121
=
=
U
.
Ví dụ 4. Từ các số
1,2,3
lập được bao nhiều số tự nhiên gồm
6
chữ số thỏa mãn
đồng thời hai điều kiện sau:
1) Trong mỗi số, mỗi chữ số có mặt đúng hai lần
2) Trong mỗi số, hai chữ số giống nhau không đứng cạnh nhau.
Lời giải. Gọi
X
là tập các số có 6 chữ số được lập từ các số chữ 1,2,3 và mỗi chữ
số xuất hiện đúng 2 lần

A
là tập các số thoả yêu cầu bài toán

k
A
là tập các số thuộc X là trong đó hai chữ số
k
đứng cạnh nhau
(1 k 3)≤ ≤
.

1 2 3
A A A 3!∩ ∩ =
Suy ra :
1 2 3
A A A 3.30 3.12 6 60∪ ∪ = − + =
.
Vậy
A 90 60 30= − =
.
Ví dụ 5. Có bao nhiêu hoán vị
( )
1 2 n
a ,a , ,a
của tập
{ }
1,2,3, ,n
sao cho
i
a i, i 1,2, ,n≠ ∀ =
.
Lời giải.
Gọi S là tập hợp các hoán vị của {1;2;…;n} và
i
A

là tập hợp các hoán vị
{ }
1 2 n
a ;a ; ;a


 ÷
 ÷
 
.
Chú ý: Trong một số bài toán, ta dùng công thức bao hàm loại trừ để đánh giá
các bất đẳng thức.
Ví dụ 6. Khi điều tra một lớp học, người ta thấy:
Hơn
2
3
số học sinh có điểm giỏi hai môn Toán và Lý;
Hơn
2
3
số học sinh có điểm giỏi hai môn Lý và Văn;
Hơn
2
3
số học sinh có điểm giỏi hai môn Văn và Sử;
Hơn
2
3
số học sinh có điểm giỏi hai môn Sử và Toán.
Chứng minh rằng có ít nhất 1 học sinh đạt điểm giỏi cả 4 môn Toán, Lý, Văn và
Sử.
Lời giải.
Kí hiệu
T,L,V,S
lần lượt là tập các học sinh có điểm giỏi ở môn Toán, Lý, Văn,
Sử.

Ta chọn 100 người như sau
1
x khoâng choïn choïn x khoâng choïn
1 1 1 2
2
1 2 1 2

n n n n n n
α α + α + α
1 4 2 4 3 12 3 1 44 2 4 43
Mỗi cách chọn thỏa yêu cầu bài toán tương ứng với một bộ
( )
1 2 101
x ,x , ,x
thỏa
1 2 101
x x x 1912+ + + =
với
1 101 i
x ,x 0, x 1, i 2, ,100≥ ≥ =
.
Đặt
1 1 100 100 i i
x y ,y x ,x 1 y , i 2,3, ,99= = − = =
Ta có phương trình:
1 2 101 i
y y y 1813, y 0+ + + = ≥
Vậy số cách chọn thỏa yêu cầu bài toán là:
100
1913

+ − ≥


Đặt
i i
b a 3(i 1)= − −
ta có:
i 1 i
k 1
k k
b b 1
b b n 3k 1
b a 3(k 1) n 3k 3
+

− ≥

− ≤ − −


= − − ≤ − +

Dễ thấy có một song ánh giữa tập
A
và tập con
{ }
1 2 k
B 1 b b b= ≤ < < <
của
tập

3C
−
− −
.
•
1
b 4≥
, ta đặt
i i
c b 3= −
, ta có
1 2 k
1 c c c n 3k≤ < < < ≤ −
và
i i
b ,c
là tương ứng
1-1
Do đó số tập con B là
k
n 3k
C
−
.
Vậy đáp số của bài toán là:
k 1 k
n 3k 1 n 3k
3C C
−
− − −

thứ tự là tập các
số chẵn và số lẻ của B. Theo định nghĩa tập cân ta có
1 2
B B=
. Xét một ánh xạ f
từ M vào N như sau :
( ) ( )
1 2
f B B Y\B= ∪
Do B
1
và
2
Y\Blà hai tập rời nhau nên ta có
( )
1 2 1 2
f B B Y / B B Y B Y n
= + = + − = =
Vậy
( )
f B N∈
Công việc còn lại của ta chỉ là chứng minh f là song ánh.
+)
f
là đơn ánh : Giả sử tồn tại
B,C M∈
mà



Suy ra
B C=
.
Vậy f là đơn ánh
+)
f
là toàn ánh : Với
D N∈
là một tập con của A có
n
phần tử, ta kí hiệu
1 2
M ,M
là tập các số chẵn và các số lẻ của
M
. Khi đó đặt
1 1 2 2 1 2
B M ,B Y\M ,B B B= = = ∪
.
Ta có
1 1
B M=
và
2 2 2 2 1
B Y M n M M M M= − = − = − =
suy ra
1 2
B B=

tập con của X thỏa: với mọi
x,y X∈
mà
x y≠
thì tồn tại tập
k
A (1 k m)≤ ≤
sao cho
k
k
x A
y A
 ∈


∉


hoặc
k
k
x A
y A
 ∉


∈


.

x A∉
thì
k
a 0=
.
Xét
x,x' X∈
và
( )
(
)
'
1 2 m 1 2 m
f(x) a ,a , ,a ; f(x') a ,a' , ,a'= =
Nếu
f(x) f(x')=
thì
i i
a a'=
, suy ra
k k
x A x' A∈ ⇔ ∈
và
k k
x A x' A∉ ⇔ ∉
. Điều
này xảy ra khi
x x'
=
nên f là đơn ánh. Do đó:

Với mỗi
( )
1 2 k 2n
b b ,b , ,b , ,b B= ∈
mà
2n k
b b n− =
cho ta phần tử
( )
1 2 k 2n
a a ,a , ,a , ,a A= ∈
mà
i i
j 2n j k 1
a b , i 1,k
a b , j k 1,2n
− + +

= ∀ =


= ∀ = +


Ta chứng minh
f
là đơn ánh.
Với
( ) ( )
1 2 2n 1 1 2n

= =

⇔

= = +


hay
b b'=
.
Ta chứng minh
f
không toàn ánh.
Xét
{ }
a 1;n 1,2,n 2,3, ,n,n 3;n 4, ,2n A= + + + + ∈
, khi đó, rõ ràng
a
không có
tạo ảnh
Do đó
f
không là toàn ánh.
Vậy ta có
B A<
.
Bài 6. Một dãy
1 2 n
a a a
với

Tương tự, số xâu các dạng ABABAB, BABA, BABAB lần lượt là
5 3 4
n 1 n 1 n 1
C , C , C
− − −
Do đó, có tất cả
3 4 5 5
n 1 n 1 n 1 n 1
C 2C C C
− − − +
+ + =
.
Bài 7. Cho một nhóm gồm 5 cô gái, kí hiệu là G
1
, G
2
, G
3
, G
4
, G
5
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à G
1
, G

1
và G
2
,
x
3
là số chàng trai ở giữa G
2
và G
3
, x
4
là số chàng trai ở giữa G
3
và G
4
, x
5
là số
chàng trai ở giữa G
4
và G
5
, x
6
là số chàng trai được xếp ở bên phải G
5
. Khi đó bộ
số (x
1

ta được số cách phân ghế cho các cô gái là
4 4 4 4
12 11 10 9
C C C C 1161.+ + + =
Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số
cách xếp thỏa mãn yêu cầu bài toán là 12! 1161.
Bài 8. Cho hai tập hợp M gồm các số tự nhiên gồm 2n chữ số mà trong biểu diễn
thập phân có n chữ số 1 và n chữ số 2 và tập N gồm n chữ số mà trong biểu diễn
thập phân chỉ có các chữ số 1,2,3.4 và số chữ sô 1 bằng số chữ số 2. Chứng minh
rằng
M N=
.
Lời giải.
Với một phần tử thuộc M ta cắt n chữ số đầu và n chữ số cuối rồi cộng theo cột
với quy tắc:
1+1=1, 2+2=2, 1+2=3, 2+1=4, khi đó ta thu được một số có n chữ số mà số chữ số 1
bằng số chữ số 2 nên số này thuộc N, tức là mỗi phần tử thuộc M cho tương ứng
một phần tử thuộc N (*)
Ngược lại một phần tử thuộc N ta nhân đôi nó lên và viết liền sau số vừa lấy ta
được một số gồm 2n chữ số, sau đó ta thực hiện quy luật như sau: Ơr n chữ số
đầu ta đổi 3 thành 2, 4 thành 1; ở n số sau ta đổi 3 thành 1, 4 thành 2, khi đó ta
thu được một số có 2n chữ số có n chữ số 1 và n chữ số 2, tức là mỗi phần tử
thuộc N cho tương ứng một phần tử thuộc M (**)
Từ (*) và (**) suy ra tồn tại một song ánh từ tập M vào tập N, nên
M N=
.
Bài 9. Trong mặt phẳng cho
n
đường thẳng phân biệt, hai đường thẳng bất kì
luôn cắt nhau và không có 3 đường thẳng nào đồng quy. Hỏi

đường thẳng
1 2 n
a ,a , ,a
tại
n
điểm
1 2 n
A ,A , ,A

và
n
điểm này chia đường thẳng
n 1
a
+
thành
n 1
+
phần gồm 2 tia và
n 1
−
đoạn
thẳng.
Mỗi phần bị chia đó sẽ nằm trong một miền của mặt phẳng bị chia bởi
n
đường
thẳng và phần này chia miền đó thành hai miền. Do đó, số phần mặt phẳng
được chia bởi
n 1+
đường thẳng nhiều hơn số phần mặt phẳng được chia bởi

2
n n 1 n 1 1
n(n 1) n n 4
u u n u n 1 n u 1 2 n 2
2 2
− −
+ + +
= + = + − + = = + + + + = + =
.
Bài 10. Có bao nhiêu xâu nhị phân độ dài
n
trong đó không có hai bit 1 đứng
cạnh nhau?
Lời giải.
Giả sử có
n
S
là tập hợp các xâu nhị phân có độ dài
n
và trong đó không có hai
bit 1 đứng cạnh nhau và
n n
a S=
. Ta phân hoạch tập
n
S
thành hai tập rời nhau
A
và
B

3 4 n n 2
y a a a S
−
= ∈
là một
song ánh
Nên
n 2 n 2
A S a
− −
= =
.
•
Xét ánh xạ
n 1
g : B S
−
→
được xác định bởi
2 3 n
g(x) a a a=
với
2 3 n
x 0a a a=
là
một song ánh.
Do đó
n 1 n 1
B S a
− −

cân có trọng lượng
0 1 n 1
2 ,2 , ,2
−
. Ta muốn đặt lên cái cân mỗi một trong
n
quả cân, lần lượt từng
quả một, theo cách để đảm bảo đĩa cân bên phải không bao giờ nặng hơn đĩa
cân bên trái . Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi
đặt nó lên đĩa bên phải, hoặc đĩa bên trái, cho đến khi tất cả các quả cân đều
được đặt lên đĩa. Hỏi có bao nhiêu cách để thực hiện việc đặt cân theo đúng
mục đích đề ra?
Lời giải
Gọi
n
s
là số cách thực hiện việc đặt
n
quả cân lên đĩa thỏa mãn yêu cầu đề ra.
Xét cách đặt
n 1
+
quả cân có trọng lượng
0 1 n
2 ,2 , ,2
.
Do
0 1 n 1 n n
2 2 2 2 1 2
−

, và
trong trường hợp này quả cân có trọng lượng
n 1
2
−
có 2 cách đặt ( đặt lên đĩa
bên phải hay đĩa bên trái đều thỏa mãn) , do đó số cách đặt
n 1+
quả cân trong
trường hợp này là
n
2ns
.
Vậy ta có hệ thức truy hồi
( )
n 1 n n n
s 2ns s 2n 1 s
+
= + = +
.
Ta có
1
s 1=
nên
( ) ( )
n
s 2n 1 2n 3 3.1= − −
.
Bài 12. Cho số nguyên dương
n

+
.
Xét một phần tử thuộc
n
B
thì có 1 cách thêm vào chữ số cuối để được một phần
tử của
n 1
A
+
và có đúng 3 cách thêm vào chữ số tận cùng để được một phần tử
của
n 1
B
+
.
Vậy
( )
( )
n 1 n n
n 1 n n
A 2 A B 1
B 2 A 3 B 2
+
+

= +


= +

⇔ − = −
Từ
( )
*
suy ra
( )
n n 1
n 2 n 1 2 1
a a 4 a a 4
+
+ +
− = − =
( do
1 2
a 2,a 6= =
).
n 1
n 2 n 1
a a 4
+
+ +
⇒ = +
n n 1 n 1
n 1
a 4 4 a 4 4
+ +
= + + = = + + +
(
)
n 1

n
chữ số mà trong mỗi số đó đều chứa một số lẻ chữ số 1 và một số
chẵn chữ số 2 (
n
là số nguyên dương cho trước).
Lời giải
Kí hiệu
n
X
là tập tất cả các số tự nhiên có
n
chữ số được lập từ các số của tập
E

và
n n n n
A ,B ,C ,D
lần lượt là tập tất cả các số tự nhiên có
n
chữ số được lập từ
các số của tập
E
mà trong mỗi số đó lần lượt chứa ( lẻ các chữ số 1, chẵn các chữ
số 2);( lẻ các chữ số 1, lẻ các chữ số 2); ( chẵn các chữ số 1, lẻ các chữ số 2);( chẵn
các chữ số 1, chẵn các chữ số 2).
Dễ thấy
n n n n
A ,B ,C ,D
đôi một rời nhau và
n n n n n