http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

CHƯƠNG II
BÀI TOÁN ð*M
Lý thuyt t hp là mt phn quan trng ca toán hc ri rc chuyên nghiên cu
s! phân b$ các phn t% vào các t'p hp. Thông thưng các phn t% này là h,u hn và
vi-c phân b$ chúng ph/i tho/ mãn nh,ng ñi2u ki-n nh4t ñ5nh nào ñó, tùy theo yêu cu
ca bài toán cn nghiên cu. M;i cách phân b$ như v'y gi là mt c4u hình t hp. Ch
ñ2 này ñã ñưc nghiên cu t> th k? 17, khi nh,ng câu hBi v2 t hp ñưc nêu ra trong
nh,ng công trình nghiên cu các trò chơi may ri. Li-t kê, ñm các ñ$i tưng có nh,ng
tính ch4t nào ñó là mt phn quan trng ca lý thuyt t hp. Chúng ta cn ph/i ñm các
ñ$i tưng ñF gi/i nhi2u bài toán khác nhau. Hơn n,a các k? thu't ñm ñưc dùng r4t
nhi2u khi tính xác su4t ca các bin c$.
2.1. CƠ S/ C0A PHÉP ð*M.
2.1.1. Nh4ng nguyên lý ñ:m cơ bn:
1) Quy t>c c?ng: Gi/ s% có k công vi-c T
1
, T
2
, ..., T
k
. Các vi-c này có thF làm tương
ng bLng n
1
, n
2
, ..., n
k
cách và gi/ s% không có hai vi-c nào có thF làm ñMng thi. Khi ñó
s$ cách làm mt trong k vi-c ñó là n
1
+n
2
+ ... + n
k
.
Thí dA 1: 1) Mt sinh viên có thF chn bài th!c hành máy tính t> mt trong ba danh
sách tương ng có 23, 15 và 19 bài. Vì v'y, theo quy tTc cng có 23 + 15 + 19 = 57
cách chn bài th!c hành.
2) Giá tr5 ca bin m bLng bao nhiêu sau khi ñon chương trình sau ñưc th!c hi-n?
m := 0
for i
1
:= 1 to n
1
m := m+1
for i
2
:=1 to n
2
m := m+1
.......................
for i
k
:= 1 to n
k
m := m+1
Giá tr5 khYi to ca m bLng 0. Kh$i l-nh này gMm k vòng lZp khác nhau. Sau m;i
bư\c lZp ca t>ng vòng lZp giá tr5 ca k ñưc tăng lên mt ñơn v5. Gi T
i
là vi-c thi
hành vòng lZp th i. Có thF làm T
i
bLng n
i
cách vì vòng lZp th i có n
i
bư\c lZp. Do các
vòng lZp không thF th!c hi-n ñMng thi nên theo quy tTc cng, giá tr5 cu$i cùng ca m
bLng s$ cách th!c hi-n mt trong s$ các nhi-m v_ T
i
, tc là m = n
1
+n
2
+ ... + n
k
.
Quy tTc cng có thF phát biFu dư\i dng ca ngôn ng, t'p hp như sau: Nu A
1
,
A
2
, ..., A
k
là các t'p hp ñôi mt ri nhau, khi ñó s$ phn t% ca hp các t'p hp này
bLng tng s$ các phn t% ca các t'p thành phn. Gi/ s% T
i
là vi-c chn mt phn t% t>
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

t'p A
i
v\i i=1,2, ..., k. Có |A
i
| cách làm T
i
và không có hai vi-c nào có thF ñưc làm
cùng mt lúc. S$ cách chn mt phn t% ca hp các t'p hp này, mt mZt bLng s$ phn
t% ca nó, mZt khác theo quy tTc cng nó bLng |A
1
|+|A
2
|+ ... +|A
k
|. Do ñó ta có:
|A
1
∪ A
2
∪...∪ A
k
| = |A
1
| + |A
2
|
+ ... + |A
k
|.
2) Quy t>c nhân: Gi/ s% mt nhi-m v_ nào ñó ñưc tách ra thành k vi-c T
1
, T
2
, ..., T
k
.
Nu vi-c T
i
có thF làm bLng n
i
cách sau khi các vi-c T
1
, T
2
, ... T
id1
ñã ñưc làm, khi ñó
có n
1
.n
2
....n
k
cách thi hành nhi-m v_ ñã cho.
Thí dA 2: Ngưi ta có thF ghi nhãn cho nh,ng chic gh trong mt gi/ng ñưng bLng
mt ch, cái và mt s$ nguyên dương không vưt quá 100. BLng cách như v'y, nhi2u
nh4t có bao nhiêu chic gh có thF ñưc ghi nhãn khác nhau?
Th t_c ghi nhãn cho mt chic gh gMm hai vi-c, gán mt trong 26 ch, cái và
sau ñó gán mt trong 100 s$ nguyên dương. Quy tTc nhân chg ra rLng có 26.100=2600
cách khác nhau ñF gán nhãn cho mt chic gh. Như v'y nhi2u nh4t ta có thF gán nhãn
cho 2600 chic gh.
2) Có bao nhiêu xâu nh5 phân có ñ dài n.
M;i mt trong n bit ca xâu nh5 phân có thF chn bLng hai cách vì m;i bit hoZc
bLng 0 hoZc bLng 1. BYi v'y theo quy tTc nhân có tng cng 2
n
xâu nh5 phân khác nhau
có ñ dài bLng n.
3)Có thF to ñưc bao nhiêu ánh x t> t'p A có m phn t% vào t'p B có n phn t%?
Theo ñ5nh nghĩa, mt ánh x xác ñ5nh trên A có giá tr5 trên B là mt phép tương
ng m;i phn t% ca A v\i mt phn t% nào ñó ca B. Rõ ràng sau khi ñã chn ñưc /nh
ca i d 1 phn t% ñu, ñF chn /nh ca phn t% th i ca A ta có n cách. Vì v'y theo quy
tTc nhân, ta có n.n...n=n
m
ánh x xác ñ5nh trên A nh'n giá tr5 trên B.
4) Có bao nhiêu ñơn ánh xác ñ5nh trên t'p A có m phn t% và nh'n giá tr5 trên t'p B có n
phn t%?
Nu m > n thì v\i mi ánh x, ít nh4t có hai phn t% ca A có cùng mt /nh, ñi2u
ñó có nghĩa là không có ñơn ánh t> A ñn B. Bây gi gi/ s% m ≤ n và gi các phn t%
ca A là a
1
,a
2
,...,a
m
. Rõ ràng có n cách chn /nh cho phn t% a
1
. Vì ánh x là ñơn ánh
nên /nh ca phn t% a
2
ph/i khác /nh ca a
1
nên chg có n d 1 cách chn /nh cho phn t%
a
2
. Nói chung, ñF chn /nh ca a
k
ta có n d k + 1 cách. Theo quy tTc nhân, ta có
n(n − 1)(n − 2)...(n − m + 1) =
!
( )!−
ñơn ánh t> t'p A ñn t'p B.
5) Giá tr5 ca bin k bLng bao nhiêu sau khi chương trình sau ñưc th!c hi-n?
m := 0
for i
1
:= 1 to n
1
for i
2
:= 1 to n
2
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

.......................
for i
k
:= 1 to n
k
k := k+1
Giá tr5 khYi to ca k bLng 0. Ta có k vòng lZp ñưc lMng nhau. Gi T
i
là vi-c thi
hành vòng lZp th i. Khi ñó s$ ln ñi qua vòng lZp bLng s$ cách làm các vi-c T
1
, T
2
, ...,
T
k
. S$ cách th!c hi-n vi-c T
j
là n
j
(j=1, 2,..., k), vì vòng lZp th j ñưc duy-t v\i m;i giá
tr5 nguyên i
j
nLm gi,a 1 và n
j
. Theo quy tTc nhân vòng lZp lMng nhau này ñưc duy-t
qua n
1
.n
2
....n
k
ln. Vì v'y giá tr5 cu$i cùng ca k là n
1
.n
2
....n
k
.
Nguyên lý nhân thưng ñưc phát biFu bLng ngôn ng, t'p hp như sau. Nu A
1
,
A
2
,..., A
k
là các t'p h,u hn, khi ñó s$ phn t% ca tích Descartes ca các t'p này bLng
tích ca s$ các phn t% ca mi t'p thành phn. Ta bit rLng vi-c chn mt phn t% ca
tích Descartes A
1
x A
2
x...x A
k
ñưc tin hành bLng cách chn ln lưt mt phn t% ca
A
1
, mt phn t% ca A
2
, ..., mt phn t% ca A
k
. Theo quy tTc nhân ta có:
|A
1
x A
2
x ... x A
k
| = |A
1
|.|A
2
|...|A
k
|.
2.1.2. Nguyên lý bù trH:
Khi hai công vi-c có thF ñưc làm ñMng thi, ta không thF dùng quy tTc cng ñF
tính s$ cách th!c hi-n nhi-m v_ gMm c/ hai vi-c. ðF tính ñúng s$ cách th!c hi-n nhi-m
v_ này ta cng s$ cách làm m;i mt trong hai vi-c rMi tr> ñi s$ cách làm ñMng thi c/
hai vi-c. Ta có thF phát biFu nguyên lý ñm này bLng ngôn ng, t'p hp. Cho A
1
, A
2
là
hai t'p h,u hn, khi ñó
|A
1
∪ A
2
| = |A
1
| + |A
2
| − |A
1
∩ A
2
|.
T> ñó v\i ba t'p hp h,u hn A
1
, A
2
, A
3
, ta có:
|A
1
∪ A
2
∪ A
3
| = |A
1
| + |A
2
| + |A
3
| − |A
1
∩ A
2
| − |A
2
∩ A
3
| − |A
3
∩ A
1
| + |A
1
∩ A
2
∩ A
3
|,
và bLng quy np, v\i k t'p h,u hn A
1
, A
2
, ..., A
k
ta có:
| A
1
∪ A
2
∪ ... ∪ A
k
| = N
1
− N
2
+ N
3
− ... + (−1)
kd1
N
k
,
trong ñó N
m
(1 ≤ m ≤ k) là tng phn t% ca t4t c/ các giao m t'p l4y t> k t'p ñã cho,
nghĩa là
N
m
=
|...|
...1
21
21
∩∩∩
∑
≤<<<≤
Bây gi ta ñMng nh4t t'p A
m
(1 ≤ m ≤ k) v\i tính ch4t A
m
cho trên t'p vũ tr_ h,u
hn U nào ñó và ñm xem có bao nhiêu phn t% ca U sao cho không thBa mãn b4t kỳ
mt tính ch4t A
m
nào.
Gi
là s$ cn ñm, N là s$ phn t% ca U. Ta có:
= − | A
1
∪ A
2
∪ ... ∪ A
k
| = − N
1
+ N
2
− ... + (−1)
k
N
k
,
trong ñó N
m
là tng các phn t% ca U thBa mãn m tính ch4t l4y t> k tính ch4t ñã cho.
Công thc này ñưc gi là nguyên lý bù trH. Nó cho phép tính
qua các N
m
trong
trưng hp các s$ này du tính toán hơn.
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

Thí dA 3: Có n lá thư và n phong bì ghi svn ñ5a chg. BB ngwu nhiên các lá thư vào các
phong bì. HBi xác su4t ñF x/y ra không mt lá thư nào ñúng ñ5a chg.
M;i phong bì có n cách bB thư vào, nên có t4t c/ n! cách bB thư. V4n ñ2 còn li
là ñm s$ cách bB thư sao cho không lá thư nào ñúng ñ5a chg. Gi U là t'p hp các cách
bB thư và A
m
là tính ch4t lá thư th m bB ñúng ñ5a chg. Khi ñó theo công thc v2 nguyên
lý bù tr> ta có:
= n! − N
1
+ N
2
− ... + (−1)
n
N
n
,
trong ñó N
m
(1 ≤ m ≤ n) là s$ t4t c/ các cách bB thư sao cho có m lá thư ñúng ñ5a chg.
Nh'n xét rLng, N
m
là tng theo mi cách l4y m lá thư t> n lá, v\i m;i cách l4y m lá thư,
có (ndm)! cách bB ñF m lá thư này ñúng ñ5a chg, ta nh'n ñưc:
N
m
=
(n d m)! =
!
!
và
= n!(1 −
1
1
+
1
2!
− ... + (−1)
n
1
),
trong ñó
=
)!(!
!
−
là thp ch'p m ca t'p n phn t% (s$ cách chn m ñ$i
tưng trong n ñ$i tưng ñưc cho). T> ñó xác su4t cn tìm là: 1 −
1
1
+
1
2!
− ... + (−1)
n
1
. Mt ñi2u lý thú là xác su4t này dn ñn ed
1
(nghĩa là còn >
1
3
) khi n khá l\n.
S$
trong bài toán này ñưc gi là s$ m4t th t! và ñưc ký hi-u là D
n
. Dư\i
ñây là mt vài giá tr5 ca D
n
, cho ta th4y D
n
tăng nhanh như th nào so v\i n:
n 2 3 4 5 6 7 8 9 10 11
D
n
1 2 9 44 265 1854 14833 133496 1334961 14684570
2.2. NGUYÊN LÝ DIRICHLET.
2.2.1. MQ ñRu:
Gi/ s% có mt ñàn chim bM câu bay vào chuMng. Nu s$ chim nhi2u hơn s$ ngăn
chuMng thì ít nh4t trong mt ngăn có nhi2u hơn mt con chim. Nguyên lý này dĩ nhiên là
có thF áp d_ng cho các ñ$i tưng không ph/i là chim bM câu và chuMng chim.
Mnh ñ (Nguyên lý):
Nu có k+1 (hoZc nhi2u hơn) ñM v't ñưc ñZt vào trong k hp
thì tMn ti mt hp có ít nh4t hai ñM v't.
ChTng minh: Gi/ s% không có hp nào trong k hp cha nhi2u hơn mt ñM v't. Khi ñó
tng s$ v't ñưc cha trong các hp nhi2u nh4t là bLng k. ði2u này trái gi/ thit là có ít
nh4t k + 1 v't.
Nguyên lý này thưng ñưc gi là nguyên lý Dirichlet, mang tên nhà toán hc
ngưi ðc Y th kz 19. Ông thưng xuyên s% d_ng nguyên lý này trong công vi-c ca
mình.
Thí dA 4:
Trong b4t kỳ mt nhóm 367 ngưi th nào cũng có ít nh4t hai ngưi có
ngày sinh nh't gi$ng nhau bYi vì chg có t4t c/ 366 ngày sinh nh't khác nhau.
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

2) Trong kỳ thi hc sinh giBi, ñiFm bài thi ñưc ñánh giá bYi mt s$ nguyên trong
kho/ng t> 0 ñn 100. HBi rLng ít nh4t có bao nhiêu hc sinh d! thi ñF cho chTc chTn tìm
ñưc hai hc sinh có kt qu/ thi như nhau?
Theo nguyên lý Dirichlet, s$ hc sinh cn tìm là 102, vì ta có 101 kt qu/ ñiFm
thi khác nhau.
3) Trong s$ nh,ng ngưi có mZt trên trái ñ4t, ph/i tìm ñưc hai ngưi có hàm răng
gi$ng nhau. Nu xem m;i hàm răng gMm 32 cái như là mt xâu nh5 phân có chi2u dài
32, trong ñó răng còn ng v\i bit 1 và răng m4t ng v\i bit 0, thì có t4t c/ 2
32
=
4.294.967.296 hàm răng khác nhau. Trong khi ñó s$ ngưi trên hành tinh này là vưt
quá 5 tg, nên theo nguyên lý Dirichlet ta có ñi2u cn tìm.
2.2.2. Nguyên lý Dirichlet tUng quát:
Mnh ñ:
Nu có N ñM v't ñưc ñZt vào trong k hp thì s| tMn ti mt hp cha ít nh4t
N/k ñM v't.
(~ ñây, x là giá tr5 ca hàm trn ti s$ th!c x, ñó là s$ nguyên nhB nh4t có giá tr5 l\n
hơn hoZc bLng x. Khái ni-m này ñ$i ngwu v\i [x] – giá tr5 ca hàm sàn hay hàm phn
nguyên ti x – là s$ nguyên l\n nh4t có giá tr5 nhB hơn hoZc bLng x.)
ChTng minh:Gi/ s% mi hp ñ2u cha ít hơn N/k v't. Khi ñó tng s$ ñM v't là
≤ k (
− 1) < k
= .
ði2u này mâu thuƒn v\i gi/ thit là có ñM v't cn xp.
Thí dA 5: 1)Trong 100 ngưi, có ít nh4t 9 ngưi sinh cùng mt tháng.
Xp nh,ng ngưi sinh cùng tháng vào mt nhóm. Có 12 tháng t4t c/. V'y theo
nguyên lý Dirichlet, tMn ti mt nhóm có ít nh4t 100/12= 9 ngưi.
2) Có năm loi hc bng khác nhau. HBi rLng ph/i có ít nh4t bao nhiêu sinh viên ñF
chTc chTn rLng có ít ra là 6 ngưi cùng nh'n hc bng như nhau.
Gi N là s$ sinh viên, khi ñó N/5 = 6 khi và chg khi 5 < N/5 ≤ 6 hay 25 < N ≤
30. V'y s$ N cn tìm là 26.
3) S$ mã vùng cn thit nhB nh4t ph/i là bao nhiêu ñF ñ/m b/o 25 tri-u máy ñi-n thoi
trong nư\c có s$ ñi-n thoi khác nhau, m;i s$ có 9 ch, s$ (gi/ s% s$ ñi-n thoi có dng
0XX d 8XXXXX v\i X nh'n các giá tr5 t> 0 ñn 9).
Có 10
7
= 10.000.000 s$ ñi-n thoi khác nhau có dng 0XX d 8XXXXX. Vì v'y
theo nguyên lý Dirichlet tng quát, trong s$ 25 tri-u máy ñi-n thoi ít nh4t có
25.000.000/10.000.000 = 3 có cùng mt s$. ðF ñ/m b/o m;i máy có mt s$ cn có ít
nh4t 3 mã vùng.
2.2.3. M?t sY Tng dAng cZa nguyên lý Dirichlet.
Trong nhi2u ng d_ng thú v5 ca nguyên lý Dirichlet, khái ni-m ñM v't và hp
cn ph/i ñưc l!a chn mt cách khôn khéo. Trong phn nay có vài thí d_ như v'y.