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 đi u ki n nh t đ nh 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 c u hìnhầ ủ ầ ứ ỗ ố ư ậ ọ ộ ấ
t h p. Ch đ này đã đ c nghiên c u t th k 17, khi nh ng câu h i v 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 ch t 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 đ gi i nhi u bài toán khác nhau. H n n a cácầ ả ế ố ượ ể ả ề ơ ữ
k thu t đ m đ c dùng r t nhi u khi tính xác su t c a các bi n c . ỹ ậ ế ượ ấ ề ấ ủ ế ố
2.1. C S C A PHÉP Đ M.Ơ Ở Ủ Ế
2.1.1. Nh ng nguyên lý đ m c b n:ữ ế ơ ả
1) Quy t c c ng:ắ ộ Gi s có k công vi c Tả ử ệ 1, T2, ..., Tk. Các vi c này có th làm t ngệ ể ươ
ng b ng nứ ằ 1, n2, ..., nk cách và gi s không có hai vi c nào có th làm đ ng th i. Khiả ử ệ ể ồ ờ
đó s cách làm m t trong k vi c đó là nố ộ ệ 1+n2+ ... + nk.
Thí d 1:ụ 1) M t sinh viên có th 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 t c c ng có 23 + 15 + 19 = 57ươ ứ ậ ắ ộ
cách ch n bài th c hành.ọ ự
2) Giá tr c a bi n m b ng bao nhiêu sau khi đo n ch ng trình sau đ c th c hi n?ị ủ ế ằ ạ ươ ượ ự ệ
m := 0
for i1 := 1 to n1
m := m+1
for i2 :=1 to n2
m := m+1
.......................
for ik := 1 to nk
m := m+1
Giá tr kh i t o c a m b ng 0. Kh i l nh này g m k vòng l p khác nhau. Sauị ở ạ ủ ằ ố ệ ồ ặ
m i b c l p c a t ng vòng l p giá tr c a k đ c tăng lên m t đ n v . G i Tỗ ướ ặ ủ ừ ặ ị ủ ượ ộ ơ ị ọ i là vi cệ
thi hành vòng l p th i. Có th làm Tặ ứ ể i b ng nằi cách vì vòng l p th i có nặ ứ i b c l p. Doướ ặ
các vòng l p không th th c hi n đ ng th i nên theo quy t c c ng, giá tr cu i cùngặ ể ự ệ ồ ờ ắ ộ ị ố
c a m b ng s cách th c hi n m t trong s các nhi m v Tủ ằ ố ự ệ ộ ố ệ ụ i, t c là m = nứ1+n2+ ... + nk.
Quy t c c ng có th phát bi u d i d ng c a ngôn ng t p h p nh sau: N uắ ộ ể ể ướ ạ ủ ữ ậ ợ ư ế
A1, A2, ..., Ak 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 b ng 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ệ ọ ộ
22
ph n t t t p Aầ ử ừ ậ i v i i=1,2, ..., k. Có |Aới| cách làm Ti và không có hai vi c nào có thệ ể
đ 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 m tượ ộ ố ọ ộ ầ ử ủ ợ ậ ợ ộ ặ
b ng s ph n t c a nó, m t khác theo quy t c c ng nó b ng |Aằ ố ầ ử ủ ặ ắ ộ ằ 1|+|A2|+ ... +|Ak|. Do đó
ta có:
|A1 ∪ A2 ∪...∪ Ak| = |A1| + |A2| + ... + |Ak|.
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, T2, ..., Tk.
N u vi c Tế ệ i có th làm b ng nể ằ i cách sau khi các vi c Tệ1, T2, ... Ti-1 đã đ c làm, khi đóượ
có n1.n2....nk cách thi hành nhi m v đã cho.ệ ụ
Thí d 2: ụ1) Ng i ta có th ghi nhãn cho nh ng chi c gh trong m t gi ng đ ngườ ể ữ ế ế ộ ả ườ
b ng m t ch cái và m t s nguyên d ng không v t quá 100. B ng cách nh v y,ằ ộ ữ ộ ố ươ ượ ằ ư ậ
nhi u nh t có bao nhiêu chi c gh có th đ c ghi nhãn khác nhau?ề ấ ế ế ể ượ
Th t c ghi nhãn cho m t chi c gh g m 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 t c nhân ch ra r ng có 26.100=2600ộ ố ươ ắ ỉ ằ
cách khác nhau đ gán nhãn cho m t chi c gh . Nh v y nhi u nh t ta có th gán nhãnể ộ ế ế ư ậ ề ấ ể
cho 2600 chi c gh .ế ế
2) Có bao nhiêu xâu nh phân có đ dài n.ị ộ
M i m t trong n bit c a xâu nh phân có th ch n b ng hai cách vì m i bit ho cỗ ộ ủ ị ể ọ ằ ỗ ặ
b ng 0 ho c b ng 1. B i v y theo quy t c nhân có t ng c ng 2ằ ặ ằ ở ậ ắ ổ ộ n xâu nh phân khác nhauị
có đ dài b ng n.ộ ằ
3) Có th 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 đ nh nghĩa, m t ánh x xác đ nhị ộ ạ ị trên A có giá tr 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 - 1 ph n t đ u, đ ch n nh c a ph n t th i c a A ta có n cách. Vì v yả ủ ầ ử ầ ể ọ ả ủ ầ ử ứ ủ ậ
theo quy t c nhân, ta có n.n...n=nắm ánh x xác đ nh trên A nh n giá tr trên B.ạ ị ậ ị
4) Có bao nhiêu đ n ánh xác đ nh trên t p A có m ph n t và nh n giá tr trên t p B cóơ ị ậ ầ ử ậ ị ậ
n ph n t ?ầ ử
N u m > n thì v i m i ánh x , ít nh t có hai ph n t c a A có cùng m t nh,ế ớ ọ ạ ấ ầ ử ủ ộ ả
đi u đó 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,a2,...,am. 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 ch có n - 1 cách ch n nhỉ ọ ả
cho ph n t aầ ử 2. Nói chung, đ ch n nh c a aể ọ ả ủ k ta có n - k + 1 cách. Theo quy t c nhân,ắ
ta có
n(n − 1)(n − 2)...(n − m + 1) =
n
n m
!
( )!−
đ n ánh t t p A đ n t p B.ơ ừ ậ ế ậ
5) Giá tr c a bi n k b ng bao nhiêu sau khi ch ng trình sau đ c th c hi n?ị ủ ế ằ ươ ượ ự ệ
m := 0
23
for i1 := 1 to n1
for i2 := 1 to n2
.......................
for ik := 1 to nk
k := k+1
Giá tr kh i t o c a k b ng 0. Ta có k vòng l p đ c l ng nhau. G i Tị ở ạ ủ ằ ặ ượ ồ ọ i là vi cệ
thi hành vòng l p th i. Khi đó s l n đi qua vòng l p b ng s cách làm các vi c Tặ ứ ố ầ ặ ằ ố ệ 1, T2,
..., Tk. S cách th c hi n vi c Tố ự ệ ệ j là nj (j=1, 2,..., k), vì vòng l p th j đ c duy t v iặ ứ ượ ệ ớ
m i giá tr nguyên iỗ ị j n m gi a 1 và nằ ữ j. Theo quy t c nhân vòng l p l ng nhau này đ cắ ặ ồ ượ
duy t qua nệ1.n2....nk l n. Vì v y giá tr cu i cùng c a k là nầ ậ ị ố ủ 1.n2....nk.
Nguyên lý nhân th ng đ c phát bi u b ng ngôn ng t p h p nh sau. N uườ ượ ể ằ ữ ậ ợ ư ế
A1, A2,..., Ak 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ậ ữ ạ ố ầ ử ủ ủ ậ
b ng tích c a s các ph n t c a m i t p thành ph n. Ta bi t r ng vi c ch n m tằ ủ ố ầ ử ủ ọ ậ ầ ế ằ ệ ọ ộ
ph n t c a tích Descartes Aầ ử ủ 1 x A2 x...x Ak đ c ti n hành b ng 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 t c nhân taắ
có:
|A1 x A2 x ... x Ak| = |A1|.|A2|...|Ak|.
2.1.2. Nguyên lý bù tr :ừ
Khi hai công vi c có th đ c làm đ ng th i, ta không th dùng quy t c c ngệ ể ượ ồ ờ ể ắ ộ
đ tính s cách th c hi n nhi m v g m c hai vi c. Đ 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 r i tr đi s cách làm đ ngệ ụ ộ ố ỗ ộ ệ ồ ừ ố ồ
th i c hai vi c. Ta có th phát bi u nguyên lý đ m này b ng ngôn ng t p h p. Choờ ả ệ ể ể ế ằ ữ ậ ợ
A1, A2 là hai t p h u h n, khi đóậ ữ ạ
|A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|.
T đó v i ba t p h p h u h n Aừ ớ ậ ợ ữ ạ 1, A2, A3, ta có:
|A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A2 ∩ A3| − |A3 ∩ A1| + |A1 ∩ A2 ∩ A3|,
và b ng quy n p, v i k t p h u h n Aằ ạ ớ ậ ữ ạ 1, A2, ..., Ak ta có:
| A1 ∪ A2 ∪ ... ∪ Ak| = N1 − N2 + N3 − ... + (−1)k-1Nk,
trong đó Nm (1 ≤ m ≤ k) là t ng ph n t c a t t c các giao m t p l y t k t p đã cho,ổ ầ ử ủ ấ ả ậ ấ ừ ậ
nghĩa là
Nm =
|...|
...1 21
21 m
m
i
kiii
ii AAA ∩∩∩
∑≤<<<≤
Bây gi ta đ ng nh t t p Aờ ồ ấ ậ m (1 ≤ m ≤ k) v i tính ch t 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 th a mãn b tữ ạ ế ầ ử ủ ỏ ấ
kỳ m t tính ch t Aộ ấ m nào. G i ọ
N
là s c n đ m, N là s ph n t c a U. Ta có:ố ầ ế ố ầ ử ủ
N
= N − | A1 ∪ A2 ∪ ... ∪ Ak| = N − N1 + N2 − ... + (−1)kNk,
24
trong đó Nm là t ng các ph n t c a U th a mãn m tính ch t l y t k tính ch t đã cho.ổ ầ ử ủ ỏ ấ ấ ừ ấ
Công th c này đ c g i là ứ ượ ọ nguyên lý bù trừ. Nó cho phép tính
N
qua các Nm trong
tr ng h p các s này d tính toán h n.ườ ợ ố ễ ơ
Thí d 3: ụCó n lá th và n phong bì ghi s n đ a ch . B ng u nhiên các lá th vào cácư ẵ ị ỉ ỏ ẫ ư
phong bì. H i xác su t đ x y ra không m t lá th nào đúng đ a ch .ỏ ấ ể ả ộ ư ị ỉ
M i phong bì có n cách b th vào, nên có t t c n! cách b th . V n đ còn l iỗ ỏ ư ấ ả ỏ ư ấ ề ạ
là đ m s cách b th sao cho không lá th nào đúng đ a ch . G i U là t p h p các cáchế ố ỏ ư ư ị ỉ ọ ậ ợ
b th và Aỏ ư m là tính ch t lá th th m b đúng đ a ch . Khi đó theo công th c vấ ư ứ ỏ ị ỉ ứ ề
nguyên lý bù tr ta có:ừ
N
= n! − N1 + N2 − ... + (−1)nNn,
trong đó Nm (1 ≤ m ≤ n) là s t t c các cách b th sao cho có m lá th đúng đ a ch .ố ấ ả ỏ ư ư ị ỉ
Nh n xét r ng, Nậ ằ m là t ng theo m i cách l y m lá th t n lá, v i m i cách l y m láổ ọ ấ ư ừ ớ ỗ ấ
th , có (n-m)! cách b đ m lá th này đúng đ a ch , ta nh n đ c:ư ỏ ể ư ị ỉ ậ ượ
Nm =
m
n
C
(n - m)! =
n
k
!
!
và
N
= n!(1 −
1
1!
+
1
2!
− ... + (−1)n
1
n!
),
trong đó
m
n
C
=
là t h 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 su t c n tìm là: 1 ượ ố ượ ượ ừ ấ ầ −
1
1!
+
1
2!
− ... + (−1)n
1
n!
. M t đi u lý thú là xác su t này d n đ n eộ ề ấ ầ ế -1 (nghĩa là còn >
1
3
) khi n khá l n.ớ
Số
N
trong bài toán này đ c g i là s m t th t và đ c ký hi u là Dượ ọ ố ấ ứ ự ượ ệ n. D iướ
đây là m t vài giá tr c a Dộ ị ủ n, cho ta th y Dấn tăng nhanh nh th nào so v i n:ư ế ớ
n 2 3 4 5 6 7 8 9 10 11
Dn1 2 9 44 265 1854 14833 133496 1334961 14684570
2.2. NGUYÊN LÝ DIRICHLET.
2.2.1. M đ u:ở ầ
Gi s có m t đàn chim b câu bay vào chu ng. N u s chim nhi u h n sả ử ộ ồ ồ ế ố ề ơ ố
ngăn chu ng thì ít nh t trong m t ngăn có nhi u h n m t con chim. Nguyên lý này dĩồ ấ ộ ề ơ ộ
nhiên là có th áp d ng cho các đ i t ng không ph i là chim b câu và chu ng chim.ể ụ ố ượ ả ồ ồ
M nh đ (Nguyên lý):ệ ề N u có k+1 (ho c nhi u h n) đ v t đ c đ t vào trong kế ặ ề ơ ồ ậ ượ ặ
h p thì t n t i m t h p có ít nh t hai đ v t.ộ ồ ạ ộ ộ ấ ồ ậ
Ch ng minh:ứ Gi s không có h p nào trong k h p ch a nhi u h n m t đ v t. Khiả ử ộ ộ ứ ề ơ ộ ồ ậ
đó t ng s v t đ c ch a trong các h p nhi u nh t là b ng k. Đi u này trái gi thi tổ ố ậ ượ ứ ộ ề ấ ằ ề ả ế
là có ít nh t k + 1 v t.ấ ậ
25
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 th k 19. Ông th ng xuyên s d ng nguyên lý này trong công vi c c aườ ứ ở ế ỷ ườ ử ụ ệ ủ
mình.
Thí d 4:ụ 1) Trong b t kỳ m t nhóm 367 ng i th nào cũng có ít nh t hai ng i cóấ ộ ườ ế ấ ườ
ngày sinh nh t gi ng nhau b i vì ch có t t c 366 ngày sinh nh t khác nhau.ậ ố ở ỉ ấ ả ậ
2) Trong kỳ thi h c sinh gi i, đi m bài thi đ c đánh giá b i m t s nguyên trongọ ỏ ể ượ ở ộ ố
kho ng t 0 đ n 100. H i r ng ít nh t có bao nhiêu h c sinh d thi đ cho ch c ch nả ừ ế ỏ ằ ấ ọ ự ể ắ ắ
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 đi mố ọ ầ ế ả ể
thi khác nhau.
3) Trong s nh ng ng i có m t trên trái đ t, 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 g m 32 cái nh là m t xâu nh phân có chi u dàiố ế ỗ ồ ư ộ ị ề
32, trong đó răng còn ng v i bit 1 và răng m t ng v i bit 0, thì có t t 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 t , nên theo nguyên lý Dirichlet ta có đi u c n tìm.ỉ ề ầ
2.2.2. Nguyên lý Dirichlet t ng quát:ổ
M nh đ :ệ ề N u có N đ v t đ c đ t vào trong k h p thì s t n t i m t h p ch a ítế ồ ậ ượ ặ ộ ẽ ồ ạ ộ ộ ứ
nh t ấ]N/k[ đ v t.ồ ậ
( đây, Ở]x[ là giá tr c a hàm tr n t i s th c x, đó là s nguyên nh nh t có giá trị ủ ầ ạ ố ự ố ỏ ấ ị
l n h n ho c b ng x. Khái ni m này đ i ng u v i [x] – giá tr c a hàm sàn hay hàmớ ơ ặ ằ ệ ố ẫ ớ ị ủ
ph n nguyên t i x – là s nguyên l n nh t có giá tr nh h n ho c b ng x.)ầ ạ ố ớ ấ ị ỏ ơ ặ ằ
Ch ng minh:ứ Gi s m i h p đ u ch a ít h n ả ử ọ ộ ề ứ ơ ]N/k[ v t. Khi đó t ng s đ v t làậ ổ ố ồ ậ
≤ k (]
N
k
[ − 1) < k
N
k
= N.
Đi u này mâu thu n v i gi thi t là có ề ẩ ớ ả ế N đ v t c n x p.ồ ậ ầ ế
Thí d 5:ụ 1) Trong 100 ng i, có ít nh t 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 t t c . V y theoế ữ ườ ộ ấ ả ậ
nguyên lý Dirichlet, t n t i m t nhóm có ít nh t ồ ạ ộ ấ ]100/12[= 9 ng i.ườ
2) Có năm lo i h c b ng khác nhau. H i r ng ph i có ít nh t bao nhiêu sinh viên đạ ọ ổ ỏ ằ ả ấ ể
ch c ch n r ng 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à ch 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 nh nh t ph i là bao nhiêu đ đ 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 - 8XXXXX v i X nh n các giá tr t 0 đ n 9).ạ ớ ậ ị ừ ế
Có 107 = 10.000.000 s đi n tho i khác nhau có d ng 0XX - 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 nh t có ổ ố ệ ệ ạ ấ ]
26