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.
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:
- Phuong_phap_xac_suat_trong_toan_trung_hoc_pho_thong.pdf