Luận văn Phương pháp xác suất trong toán trung học phổ thông

Ví dụ 2.3.3. Chứng minh rằng khi ta tô đồ thị đầy đủ K17 bởi ba màu xanh,

đỏ, vàng thì luôn tồn tại K3 có màu xanh hoặc đỏ hoặc vàng.

Lời giải. Chọn một đỉnh V tùy ý của K17, bậc của V là 16. Khi đó ta có ít

nhất 6 cạnh để 6 cạnh đó tô cùng một màu (theo nghuyên lí Đirichle). Giả sử 6

cạnh đó được tô màu đỏ. Khi đó gọi K6 có một cạnh tô màu đỏ. Gọi B là tập

các đỉnh cuối của 6 cạnh được tô màu đỏ đó. Khi đó gọi K6 là đồ thị con có 6

đỉnh thuộc B, giả sử trong K6 có một cạnh tô màu đỏ khi đó tồn tại một tam

giác được tô màu đỏ tức K6 được tô bởi hai màu xanh, vàng, khi đó theo ví dụ

2.3.1 k6 chứa K3 - xanh hoặc K3 - vàng. Ta có điều phải chứng minh.

pdf83 trang | Chia sẻ: dungnc89 | Lượt xem: 1237 | Lượt tải: 0download
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Phương pháp xác suất trong toán trung học phổ thông, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
G và PG là một đỉnh
của đồ thị G1. Với mỗi đỉnh P của đồ thị G1, ta chọn đường đi W nối đỉnh P0
với đỉnh P . Nếu đường đi W có độ dài chẵn thì đỉnh P thuộc tập X, còn nếu
đường đi W có độ dài lẻ thì đỉnh P được lấy vào tập Y . Sự phân loại các đỉnh
của đồ thị G1 không phụ thuộc vào cách chọn đường đi W . Thật vậy, nếu có
đường đi W ′ với độ dài lẻ nối đỉnh P0 với đỉnh P thì đồ thị G1 sẽ có chu trình
với độ dài lẻ, mâu thuẫn với giả thiết ban đầu.
Với cách thiết lập tập hợp X và Y này, các đỉnh của đồ thị G1 hoặc thuộc tập
hợp X hoặc thuộc tập hợp Y . Bây giờ ta chứng minh rằng G1 chỉ có các cạnh
nối các đỉnh không cùng một tập hợp nối với nhau. Thật vậy, giả sử rằng có hai
đỉnh P và Q kề nhau trong đồ thị G1 thì chúng không thể cùng thuộc một tập
hợp X hoặc Y , nếu không từ P0 ta có thể đi tới đỉnh P rồi tới đỉnh Q bởi cạnh
(P,Q) và trở về đỉnh P0 với một đường đi lẻ cạnh, điều này không thể xảy ra
trong đồ thị G do G chỉ có chu trình với số chẵn cạnh mà thôi. Như vậy, đồ thị
G là đồ thị lưỡng phân với hai tập đỉnh X và Y .

Ta ký hiệu Km,n là đồ thị lưỡng phân đầy đủ, |X| = m, |Y | = n. Mỗi đỉnh của
tập X được nối với tất cả các đỉnh của tập Y .
Ví dụ 2.2.4. Đồ thị lưỡng phân đầy đủ K3,3
33
Chương 2. Lý thuyết đồ thị cơ bản
Hình 2.7: K3,3.
d) Cây và rừng
Định nghĩa 2.2.9. Một cây là một đồ thị liên thông vô hướng với ít nhất một
đỉnh và không có chu trình.
Định lý 2.2.5. Một cây bất kì với ít nhất hai đỉnh có ít nhất hai đỉnh treo.
Chứng minh.
Ta xét W = (P1, P2, ..., Pk) là một con đường có nhiều cạnh nhất. Khi đó ta
có k > 1 do cây phải có ít nhất hai đỉnh.
Hai đỉnh đầu và cuối của W,P1, Pk rõ ràng là hai đỉnh treo. Giả sử ngược lại,
P1 không phải là đỉnh treo thì đỉnh P1 được nối với một đỉnh Q 6= P2.
Do W có nhiều cạnh nhất có thể nên Q ≡ Pi với i > 2 nào đó. Nhưng như
vậy, ta sẽ thu được một chu trình K = (P1, P2, ..., Pi, Pl) trái với định nghĩa cây
không có chu trình.

Định lý 2.2.6. Một cây n đỉnh có đúng n− 1 cạnh.
Chứng minh. Ta chứng minh bằng quy nạp theo số đỉnh n của cây.
Với n = 1, rõ ràng cây với 1 đỉnh không có cạnh nào cả.
Giả sử một cây tùy ý với n đỉnh có đúng n− 1 cạnh.
34
Chương 2. Lý thuyết đồ thị cơ bản
Xét G là một cây có n+ 1 đỉnh tùy ý. Theo định lý đã chứng minh ở trên, G
có ít nhất một đỉnh treo P nào đó. Xét đồ thị G− {P}.
Vì đỉnh P là đỉnh treo, nên đồ thị G − {P} là một đồ thị liên thông. Thật
vậy, giả sử ngược lại, đồ thị G−{P} có ít nhất hai thành phần liên thông G1 và
G2 nào đó. Do G là đồ thị liên thông, cho nên có một con đường nối G1 với G2
trong G. Rõ ràng con đường này phải đi qua đỉnh P và nhận đỉnh P làm đỉnh
trong của nó. Vậy P có bậc ít nhất là 2, mâu thuẫn với giả thiết P là đỉnh treo
trong đồ thị G.
Do G không có chu trình nên đồ thị G−{P} không có chu trình. Tóm lại, đồ
thị G− {P} là một cây có n đỉnh. Theo giả thiết quy nạp thì đồ thị G− {P} có
đúng n − 1 cạnh. Suy ra đồ thị G có đúng n cạnh vì bậc của P trong đồ thị G
bằng 1.

35
Chương 2. Lý thuyết đồ thị cơ bản
Định lý 2.2.7. Cho đồ thị G = (V,E) có n đỉnh, khi đó các tính chất sau là
tương đương:
(i) G là một cây.
(ii) G không có chu trình và có n− 1 cạnh.
(iii) G liên thông và có n− 1 cạnh.
(iv) G không có chu trình và nếu thêm vào một cạnh nối hai đỉnh không kề nhau
thì G có một chu trình duy nhất.
(v) G liên thông và nếu bỏ đi một cạnh tùy ý thì G không liên thông.
(vi) Mỗi cặp đỉnh trong G được nối với nhau bằng một đường duy nhất.
Chứng minh. Ta chứng minh theo trình tự sau:
i)⇒ ii)⇒ iii)⇒ iv)⇒ v)⇒ vi)⇒ i).
i)⇒ ii): Điều này hiển nhiên đúng theo định nghĩa của cây và định lý về số cạnh
của cây.
ii)⇒ iii) Ta chỉ còn phải chứng minh G liên thông. Thật vậy, nếu G có p thành
phần liên thông thì mỗi thành phần liên thông là một cây và số cạnh của G theo
định lí về số cạnh của cây sẽ là |V | − p (bằng tổng các cạnh của các cây thành
phần). Do số cạnh của G được cho biết là n − 1, nên ta có |V | − p = n − 1, vậy
p = 1 hay nói cách khác, G là đồ thị liên thông.
iii) ⇒ iv) Trước hết ta thấy G là cây, vì nếu không có thể lần lượt bỏ bớt các
cạnh khỏi G sao cho đồ thị thu được là đồ thị liên thông, và đến lúc nào đó
không còn có thể bỏ được cạnh nào nữa, đồ thị lúc đó không còn chu trình (nếu
không có thể bỏ bất kì cạnh nào trên chu trình vẫn không ảnh hưởng tình liên
thông của đồ thị). Đồ thị thu được sau cùng là cây, và sẽ có n − 1 cạnh theo
định lí về số cạnh của cây. Suy ra số cạnh bỏ đi là 0, tức G là cây và không có
chu trình.
Giả sử thêm vào cạnh (x, y) với x.y không kề nhau trong G để được đồ thị G′.
Khi đó, ta được một chu trình W gồm đường đi L trong G nối x với y và cạnh
(x, y), W là chu trình duy nhất của G′. Thật vậy, nếu có chu trình W ′ trong G
thì hiển nhiên W ′ đi qua cạnh (x, y) và W có chứa đường đi L′ trong G, L′ đi từ
x đến y. Như vậy hai đường L và L′ tạo thành một chu trình trong G, vô lí. Vậy
ta có điều phải chứng minh.
iv) ⇒ v) Cho trước G không có chu trình và biết rằng nếu thêm vào một cạnh
36
Chương 2. Lý thuyết đồ thị cơ bản
nối hai đỉnh không kề nhau thì G có duy nhất một chu trình, ta phải chứng
minh G liên thông và bỏ đi cạnh tùy ý thì G không còn liên thông.
Giả sử ngược lại G không liên thông, tức là tồn tại cặp đỉnh x, y trong G mà
không có đường nào nối x với y. Khi đó nối x với y bởi 1 cạnh, đồ thị nhận được
vẫn không có chu trình, điều này mâu thuẫn với iv). Vậy G là liên thông. Nếu
bỏ đi 1 cạnh trong G mà đồ thị vẫn liên thông thì nếu khôi phục lại cạnh này
đồ thị sẽ có chu trình. Điều nàu mâu thuẫn với iv) vậy ta có v).
v) ⇒ vi) Nếu trong G có tồn tại cặp đỉnh x, y không nối với nhau bằng đường
nào cả, khi đó G không liên thông, mâu thuẫn với v). Vậy mỗi cặp đỉnh đều có
đường đi nối với nhau. Đường nối đó là duy nhất vì nếu có nhiều hơn thì sau
khi bỏ đi một cạnh trên chu trình xuất hiện bởi hai đường nối đình này thì đồ
thị vẫn liên thông, trái với v).
vi)⇒ i) Do mỗi cặp đỉnh nối với nhau bởi một đường nên G là liên thông. Giả
sử G có chu trình thì xét cặp đỉnh X, y trên chu trình đó. Khi đó x, y có 2 cặp
đường nối với nhau, mâu thuẫn với vi).

Định nghĩa 2.2.10. Rừng là một đồ thị vô hướng không có chu trình.
Định lý 2.2.8. Rừng với n đỉnh và k thành phần liên thông có đúng n−k cạnh.
Chứng minh. Giả sử số đỉnh của thành phần liên thông thứ i là ni. Theo định
lí 2.2.6, mỗi thành phần liên thông này có đúng ni − 1 cạnh. Như vậy số cạnh
của rừng là
k∑
i=1
(ni − 1) = n− k.

e) Đồ thị phẳng
Định nghĩa 2.2.11. Những đồ thị có thể biểu diễn mặt phẳng sao cho không
có hai cạnh nào cắt nhau được gọi là đồ thị phẳng.
Ví dụ 2.2.5. Đồ thị biểu diễn khối thập nhị diện đều là một đồ thị phẳng
37
Chương 2. Lý thuyết đồ thị cơ bản
Hình 2.8: Thập nhị diện đều.
Định lý 2.2.9. Lớp biểu diễn của các khối đa diện lồi chính là lớp các đồ thị
phẳng có 3 thành phần liên thông.
Định lý 2.2.10. Cho đồ thị biểu diễn khối đa diện lồi có d đỉnh và c cạnh, m
miền ta có đẳng thức d+m = c+ 2.
Chứng minh. Để chứng minh định lí này, ta gọi một cạnh của đồ thị phẳng
cho trước G là cầu nếu bỏ nó đi thì số thành phần liên thông của đồ thị tăng
lên ít nhất 1, và gọi là cạnh biên nếu cạnh này không phải là cầu của đồ thị G.
Hiển nhiên một cạnh e của một đồ thị phẳng G cho trước là cạnh biên khi và
chỉ khi nó là cạnh chng của hai miền khác nhau của đồ thị G.
Dễ thấy một cạnh bất kì của đồ thị phẳng chỉ có thể hoặc là cầu hoặc là cạnh
biên mà thôi.

38
Chương 2. Lý thuyết đồ thị cơ bản
2.3 Bài toán tô màu và các số Ramsey
Ở phần này ta sẽ nghiên cứu một số lý thuyết cơ bản trong bài toán tô màu đồ
thị, từ đó dẫn tới lý thuyết Ramsey. Trước hết ta tìm hiểu lý thuyết Ramsey
cho đồ thị hữu hạn.
2.3.1 Lý thuyết Ramsey cho đồ thị hữu hạn
Ví dụ 2.3.1. Chứng minh rằng cứ 6 người bất kỳ trong đó hoặc có 3 người quen
biết nhau hoặc có 3 người không quen biết nhau.
Lời giải.
Giả sử 6 người đó được biểu diễn bởi 6 đỉnh của K6. K6 có 15 cạnh, ta tô màu
các cạnh của K6 như sau: 2 người quen nhau được nối với nhau bằng 1 cạnh
màu đỏ, 2 người không quen nhau được nối với nhau bằng 1 cạnh màu xanh.
Lấy 1 đỉnh A bất kì trong đồ thị tô màu, khi đó bậc của đỉnh A là 5. Khi đó
ít nhất có 3 cạnh kề với A có cùng màu, giả sử đó là màu đỏ, giả sử X, Y, Z là 3
đỉnh cuối của các cạnh màu đỏ đó.
Bây giờ nếu bất kì một cạnh nào trong ∆XY Z được tô bởi màu đỏ ta có tam
giác có màu đỏ (trong đó 2 cạnh nối với A). Ngược lại nếu cả 3 cạnh của tam
giác XY Z màu xanh ta có X.Y, Z không quen nhau. Từ đó ta có điều phải chứng
minh.
Rất nhiều bài toán thực tế dẫn đến bài toán Ramsey cho đồ thị hữu hạn,
khái quát hóa ta chứng minh được.
Định lý 2.3.1. Cho k, l là hai số nguyên dương (lớn hơn hoặc bằng 2), khi đó
tồn tại một số R(k, l) nhỏ nhất sao cho khi ta tô màu tất cả các cạnh của một
đồ thị đầy đủ có R(k, l) đỉnh bởi hai màu xanh và đỏ thì luôn có đồ thị con Kk
có tất cả các cạnh màu đỏ hoặc đồ thị con Kl có tất cả các cạnh màu xanh.
Chứng minh. Ta chứng minh bằng quy nạp theo k, l.
• Trước hết ta chứng minh với mọi k, l ≥ 2 tồn tại R(k, 2) và R(2, k).
Thật vậy ta có R(k, 2) = k,R(2, l) = l.
R(k, 2) = k vì hoặc là tất cả các cạnh của Kk màu đỏ hoặc ít nhất có một
cạnh màu xanh. Khi ít nhất một cạnh màu xanh ta có đồ thị con K2 có
cạnh màu xanh.
• Tiếp theo ta chứng minh nếu tồn tại R(k, l − 1) thì cũng tồn tại R(k − 1, l)
và R(k, l)
39
Chương 2. Lý thuyết đồ thị cơ bản
Ta chứng minh R(k, l) ≤ R(k, l − 1) + R(k − 1), l. Ta xét một đồ thị đầy đủ
G có R(k, l − 1) + R(k − 1, l) đỉnh, lấy một đỉnh V tùy ý của đồ thị G. Khi
đó bậc của V = R(k, l− 1) +R(k− 1, l)− 1. Khi đó có ít nhất R(k− 1, l) cạnh
kề với V có màu xanh hoặc có ít nhất R(k − 1, l) cạnh kề với V có màu đỏ.
Không giảm tính tổng quát ta xét trường hợp.
Trường hợp 1: Nếu có R(k, l−1) cạnh kề với V có màu xanh. Gọi B là tập hợp
R(k, l − 1) đỉnh của các cạnh có màu xanh. Theo định nghĩa của R(k, l − 1)
tập B hoặc chứa đồ thị con Kk có tất cả các cạnh có màu xanh hoặc có
Kl−1 màu xanh, khi đó ta thêm đỉnh V vào Kl−1 ta có Kl có tất cả các cạnh
màu xanh. Ta có điều phải chứng minh.
Trường hợp 2: Gọi C là tập tất cả R(k − 1, l) đỉnh của các cạnh tô màu đỏ.
Khi đó C chứa một đồ thị con Kl được tô màu xanh hoặc có Kk−1 được tô
màu đỏ, khi đó ta thêm V vào C ta lại có đồ thị Kk được tô màu đỏ.

Từ ví dụ 2.3.1 và định lý ta có
Ví dụ 2.3.2. R(3, 3) = 6; R(2, 2) = 2; R(k, 2) = k; R(2, l) = l. Ta chứng minh
được R(4, 3) = R(3, 4) = 9.
Chứng minh. Thật vậy theo định lý trên ta có
R(4, 3) ≤ R(4, 2) +R(3, 3)
= 4 + 6 = 10
Ta chứng minh R(4, 3) = 9.
Khi tô màu đồ thị K9 bởi hai màu xanh đỏ thì hoặc K9 chứa đồ thị con K4
có màu đỏ hoặc đồ thị con K3 có màu xanh, điều đó không đúng với K8.
Với đỉnh V bất kì của đồ thị K9 đã tô màu, bậc của V là 8. Ta chứng minh
rằng có một đỉnh V của K9 thỏa mãn hoặc có ít nhất 6 cạnh kề với V có màu
đỏ hoặc ít nhất 4 cạnh kề với V có màu xanh. Nếu ngược lại tức mọi đỉnh của
K9 đều có 5 cạnh liền kề màu đỏ. Khi đó có một đồ thị con của K9 có tổng bậc
là 5.9=45. Mâu thuẫn với lý thuyết "tổng bậc của đồ thị là số chẵn".
a) Nếu có 6 cạnh kề với V là đỏ, gọi A là tập 6 đỉnh cuối của 6 cạnh đỏ liền kề
với V . Khi đó K6 chứa đồ thị con K3 có tất cả các cạnh màu dỏ hoặc chứa
đồ thị con K3 có tất cả các cạnh màu xanh nên K9 có chứa đồ thị con K4
xanh hoặc K3 đỏ nếu V tô màu xanh.
40
Chương 2. Lý thuyết đồ thị cơ bản
b) Mặt khác, nếu bốn cạnh kề V màu xanh. Gọi B là tập 4 đỉnh cuối của bốn
cạnh kề màu xanh đó. Nếu tất cả các cạnh của K4 có các đỉnh là B được
tô màu đỏ, ta có điều phải chứng minh. Nếu tồn tại một cạnh của K4 được
tô màu xanh thì cạnh ssos cùng V taoh thành K3 được tô màu xanh.
Cuối cùng ta chỉ ra với K8 có một cạnh tô màu không thỏa mãn định lí. Ta tô
các cạnh (i, j).i > j màu xanh, nếu j − i = 1, 4, 7. Các cạnh còn lại màu đỏ.
Đồ thị này không chứa một tam giác màu xanh vì nếu chứa một tam giác
màu xanh thì nó phải chứa số i nhỏ nhất i ∈ {1, 2, ..., 8} sao cho đỉnh i và 2 trong
3 đỉnh i+ 1, i+ 4, i+ 7 lại được nối bởi các cạnh màu xanh; mà cứ hai trong ba
đỉnh i+ 1, i+ 4, i+ 7 lại được nối bởi một cạnh màu đỏ. Điều này vô lí.
Chứng minh tương tự ta có K8 không chứa K4 màu đỏ vì nếu chứa K4 màu
đỏ thì tồn tại số i nhỏ nhất sao cho đỉnh i và 3 đỉnh i+ 2, i+ 3, i+ 5, i+ 6 được
nối với nhau bằng cạnh màu đỏ. Điều này vô lí.
Tương tự ta chứng minh được R(4, 4) = 18.

Ở phần này chúng ta chỉ có thể tìm được một số kết quả cụ thế trong hệ
thống các số Ramsey. Ta chưa tìm được công thức cụ thể tính các số R(k, k),
tuy nhiên ta có thể tìm được cận trên của các số Ramsey.
Định lý 2.3.2. Cho k, l là các số nguyên dương lớn hơn 1. Khi đó
R(k, l) ≤ Ck−1k+l−2. (2.1)
Chứng minh. Với k = 2 ta có
R(2, l) = l
Ck−1k+l−2 = l
⇒ R(k, l) ≤ Ck−1k+l−2.
Giả sử mệnh đề đúng với R(k, l − 1) và R(k − 1, l),
tức là
R(k, l − 1) ≤ Ck−1k+l−3
R(k − 1, l) ≤ Ck−2k+l−3.
Suy ra
R(k, l) ≤ R(k, l − 1) +R(k − 1, l)
≤ Ck−1k+l−3 + Ck−2k+l−3 = Ck−1k+l−2.

41
Chương 2. Lý thuyết đồ thị cơ bản
Hệ quả 2.3.1. Với mọi k ∈ N∗, n ≥ 2, ta có
R(k, k) ≤ 4k−1. (2.2)
Chứng minh. Thật vậy R(k, k) ≤ Ck−12k−2 ≤ 4k−1. 
2.3.2 Lý thuyết Ramsey trong trường hợp tổng quát
Ở phần 2.3.1 ta đã xem xét bài toán tô màu với hai màu xanh, đỏ, phần này ta
xem xét bài toán tô màu với số màu lớn hơn 2.
Ví dụ 2.3.3. Chứng minh rằng khi ta tô đồ thị đầy đủ K17 bởi ba màu xanh,
đỏ, vàng thì luôn tồn tại K3 có màu xanh hoặc đỏ hoặc vàng.
Lời giải. Chọn một đỉnh V tùy ý của K17, bậc của V là 16. Khi đó ta có ít
nhất 6 cạnh để 6 cạnh đó tô cùng một màu (theo nghuyên lí Đirichle). Giả sử 6
cạnh đó được tô màu đỏ. Khi đó gọi K6 có một cạnh tô màu đỏ. Gọi B là tập
các đỉnh cuối của 6 cạnh được tô màu đỏ đó. Khi đó gọi K6 là đồ thị con có 6
đỉnh thuộc B, giả sử trong K6 có một cạnh tô màu đỏ khi đó tồn tại một tam
giác được tô màu đỏ tức K6 được tô bởi hai màu xanh, vàng, khi đó theo ví dụ
2.3.1 k6 chứa K3 - xanh hoặc K3 - vàng. Ta có điều phải chứng minh.
Định lý 2.3.3. Cho n1, n2, ..., nk là các số nguyên dương, k ∈ N∗ cố định. Khi
đó tồn tại số nguyên dương nhỏ nhất N = R(n1, n2, ..., nk) sao cho nếu n > N và
ta tô màu tất cả các cạnh của G = Kn với 1, 2, ..., k màu thì luôn tồn tại ít nhất
một chỉ số i ∈ {1, 2, ..., k} sao cho G chứa một đồ thị con Kni được tô bởi màu i.
Chứng minh. Ta chứng minh bằng phương pháp với tổng n1 +n2 + ...+nk. Với
n1 = n2 = ... = nk = 1, trường hợp tầm thường định lí đúng.
Giả sử định lí đúng với các số nguyên dương n1, n2, ..., nk mà n1+n2+...+nk < n.
Ta chứng minh định lí đúng với các trường hợp n1 + n2 + ...+ nk = m.
Giả thiết quy nạp tức là các số R(n1 − 1, n2, ..., nk) tồn tại.
Đặt N = k(R(n1 − 1, n2, ..., nk)− 1) + 2. Giả sử G là một đồ thị đầy đủ có một
đỉnh V mà các cạnh liền kề với V được tô nhiều nhất bởi màu 1.
Gọi S là tập hợp tất cả các điểm cuối của các cạnh liền kề với V (khác V )
được tô bởi màu 1. Gọi Ks là đồ thị đầy đủ với tập đỉnh S.
Theo định nghĩa R(n1− 1, n2, ..., nk) hoặc tồn tại một chỉ số i ∈ {2, 3, ..., k} sao
cho Ks chứa một đồ thị con Kn. Có tất cả các cạnh được tô màu i (khhi đó ta
có điều phải chứng minh) hoặc Ks chứa đồ thị Kn1−1 có tất cả các cạnh được tô
42
Chương 2. Lý thuyết đồ thị cơ bản
màu 1, khi đó thêm đỉnh V vào Ks ta có tồn tại chỉ số i = 1 để tồn tại Kn1 có
tất cả các cạnh được tô bởi màu 1.

Ở chương này ta đã chỉ ra sự tồn tại và tìm được cận trên của các số Ramsey.
Ở chương 3 với việc sử dụng phương pháp xác suất ta sẽ tìm được cận dưới và
một số tính chất khác của các số Ramsey.
43
Chương 3
Xác suất và một số ứng dụng
Nội dung của chương từ mục 3.1 đến mục 3.5 được tham khảo ở tài liệu tham
khảo sau:
1. Đào Hữu Hồ(1996), “Xác suất thống kê” – NXB Đại học Quốc gia Hà Nội,
trang 3 – 49.
2. Đào Hữu Hồ(2011), “Hướng dẫn giải bài toán xác suất thống kê” – NXB Đại
học Quốc gia Hà Nội, trang 3 – 52.
3. Đoàn Quỳnh, Trần Nam Dũng, Hà Huy Khoái, Đặng Hùng Thắng, Nguyễn
Trọng Tuấn(2012), “Tài liệu chuyên toán Hình học 12” – NXB Giáo dục Việt
Nam.
4. Nguyễn Cao Văn, Trần Thái Ninh(2005), “Lý thuyết xác suất và thống kê
toán” – NXB Thống kê, trang 9 -122.
5. Nguyễn Cao Văn, Trần Thái Ninh(2006), “Bài tập xác suất và thống kê toán”
– Đại học Kinh tế Quốc dân, trang 5 -74.
3.1 Phép thử và biến cố
Định nghĩa 3.1.1. Việc thực hiện một nhóm các điều kiện cơ bản để quan sát
một hiện tượng nào đó có xảy ra hay không được gọi là thực hiện một phép thử.
Ví dụ 3.1.1. Thực hiện tung một đồng xu bốn lần là một phép thử nhằm quan
sát trong bốn lần tung đồng xu ta nhận được mặt ngửa hay mặt sấp. Khi đó tất
cả các kết quả có thể xảy ra sau 4 lần tung là 24 = 16. Khả năng xảy ra một
trong các kết quả là
1
16
.
Định nghĩa 3.1.2. Không gian mẫu Ω của phép thử T là tập hợp tất cả các
kết quả của một phép thử T sao cho các kết quả có khả năng xảy ra như nhau.
44
Chương 3. Xác suất và một số ứng dụng
Tập A ⊂ Ω thì A được gọi là biễn cố ngẫu nhiên.
Khi A = Ω thì A được gọi là biến cố chắc chắn (chắc chắn xảy ra).
Khi A = ∅ thì A được gọi là biễn cố không (không xảy ra).
3.2 Xác suất của biến cố
Trở lại với ví dụ 3.1.1 ta xét biến cố A là "kết quả bốn lần tung có ít nhất ba
lần xuất hiện mặt ngửa". Khi đó số kết quả của Ω làm A xuất hiện là: NNNN,
NSNN, NNSN, NNNS, SNNN. Khi đó năm kết quả này được gọi là kết quả có
lợi cho biến cố A, khả năng xảy ra biến cố A là
5
16
.
Định nghĩa 3.2.1. Xác suất của một biến cố là một số đặc trưng cho khả năng
xảy ra biến cố đó khi thực hiện một phép thử.
3.2.1 Định nghĩa cổ điển của xác suất
Định nghĩa 3.2.2. Xét phép thử T với không gian mẫu Ω là hữu hạn. Biến cố
A ⊂ Ω, khi đó tỉ số
P (A) =
|A|
|Ω|
được gọi là xác suất của biến cố A.
Nói một cách khác P là một hàm số xác định trên tập tất cả các tập con của
Ω, mà tập giá trị của P là [0,1] vì |A| ≤ |Ω| với mọi A ⊂ Ω. Ta có một số tính
chất của xác suất như sau
1) 0 ≤ P (A) ≤ 1, ∀A ⊂ Ω.
2) P (Ω) = 1.
3) P (∅) = 0.
Ví dụ 3.2.1. Gieo đồng thời hai đồng xu cân đối đồng chất tìm xác suất để có
biến cố:
A: " Xuất hiện hai mặt sấp".
B: "Một mặt sấp, một mặt ngửa".
C: "Ít nhất một mặt sấp".
Lời giải.
Phép thử T là tung hai đồng xu cân đối đồng chất không gian mẫu
45
Chương 3. Xác suất và một số ứng dụng
Ω = {SS,NN,NS,NN}, |Ω| = 4
A = {SS}, |A| = 1;
B = {SN,NS}, |B| = 2;
C = {SS, SN,NS}, |C| = 3.
nên P (A) =
1
4
= 0, 25;P (B) =
2
4
= 0, 5;P (C) =
3
4
= 0, 75.
Ví dụ 3.2.2. Một hộp có a quả cầu trắng, b quả cầu đen, lấy ngẫu nhiên lần
lượt hai quả cầu. Tìm xác suất để biến cố sau xảy ra
a) A : "Quả cầu thứ nhất là trắng".
b) B : " Quả cầu thứ hai là trắng biết quả cầu thứ nhất là trắng".
Lời giải.
a) Ta có
Số cách lấy lần lượt hai quả bóng là (a+b)(a+b−1) nên |Ω| = (a+b)(a+b−1).
Số cách lấy quả bóng đầu tiên là trắng, quả thứ hai là tùy ý là a.(a+ b− 1)
nên |A| = a(a+ b− 1).
Vậy P (A) =
a(a+ b− 1)
(a+ b)(a+ b− 1) =
a
a+ b
.
b) Sau khi lần đầu lấy quả trắng, số cách để lần thứ hai lấy được quả trắng là
a− 1 nên |B| = a− 1.
Số cách để lấy được một quả từ a+ b− 1 quả là a+ b− 1, tức |Ω| = a+ b− 1
nên P (B) =
a− 1
a+ b− 1 .
Ví dụ 3.2.3. Lấy ngẫu nhiên ra 8 con bài từ bộ tú lơ khơ 52 con. Tìm xác suất
của biến cố sau
A : "Lấy được 5 con màu đỏ".
B : "Lấy được một con cơ, hai con rô, ba con bích".
C : "Lấy được một con át, hai con J, ba con 9, hai con 2".
D : "Lấy được ba con cùng một chất đã chọn trước".
Lời giải.
Để lấy 8 con từ 52 con tú có C852 (cách) nên |Ω| = C852.
Ta cần lấy 5 con đỏ, 3 con đen, nên
|A| = C526.C326 = 171028000.
46
Chương 3. Xác suất và một số ứng dụng
Ta cần lấy 1 con cơ, 2 con rô, 3 con bích, 2 con tép, nên
|B| = C513.C326.C313.C213 = 22620312.
Ta cần lấy 1 con át, hai con J, ba con 9, hai con 2, nên
|C| = C14 .C24 .C34 .C24 = 576.
Ta cần lấy ba con cùng một chất và năm con thuộc ba chất khác nên
|D| = C313.C539 = 286575757.
Ta có:
P (A) =
171028000
752538150
= 0, 227268;
P (B) =
22620312
752538150
= 0, 03006;
P (C) =
576
752538150
= 0, 0000007654;
P (D) =
286575757
752538150
= 0, 218

File đính kèm:

  • pdfPhuong_phap_xac_suat_trong_toan_trung_hoc_pho_thong.pdf