Ứng dụng của xác suất

Nghiên cứu trình bày phương pháp xác suất đã phát triển mạnh mẽ và trở thành một công cụ hữu hiệu để giải quyết các bài toán tổ hợp. Cơ sở của phương pháp xác suất có thể được diễn tả như sau: để chứng minh sự tồn tại của một cấu trúc tổ hợp thỏa tính chất nào đó, cũng đề cập đến một số ứng dụng của phương pháp xác suất trong tổ hợp, đặc biệt là chứng minh bài toán tồn. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Ứng dụng của xác suất ỨNG DỤNG CỦA XÁC SUẤT Huỳnh Xuân Tín (Trường THPT Chuyên Lương Văn Chánh, Phú Yên) 1. Mở đầu Các số Ramsey R.k; l/ được chỉ ra là luôn tồn tại với mọi k; l 2 N, nhưng chỉ rất ít trong các số đó là được biết giá trị chính xác. Năm 1947, P. Erd˝os đã đưa ra một chứng minh cho cận dưới của số Ramsey dạng đối xứng bằng một phương pháp mới lúc bấy giờ: phương pháp xác suất. Bài toán như sau: k Định lý 1. Với mọi số nguyên dương k  3, ta có R.k; k/ > 2 2 . k Chứng minh. Đặt G D Kn ; n  2 2 , và xét 2 tô màu cạnh cho G một cách ngẫu nhiên (mỗi cạnh được tô đỏ hoặc xanh ngẫu nhiên với xác suất 12 ). Ta chứng minh tồn tại ít nhất một cách 2 tô màu cho G sao cho nó không chứa đồ thị con Kk cùng màu. Gọi S là một Kk -đồ thị con của G, đặt AS là biến cố chỉ S có cùng màu cạnh. Chú ý rằng, một Kk -đồ thị con của G có tất cả Ck2 cạnh, mỗi cạnh có 2 cách tô màu. Do đó 2 Ck2 PŒAS  D D 21 : Ck2 2 Theo tính chất của xác suất và chú ý rằng đồ thị G có tất cả Cnk đồ thị con Kk , nên h[ i X 2 P AS  PŒAS  D Cnk
21 Ck : S S 2 Ta chứng minh Cnk
21 Ck < 1. Ta có .n k C 1/.n k C 2/


.n 1/n n
n



n nk Cnk D < D : (1.1) kŠ kŠ kŠ Suy ra Ck2 nk 1 Ck2 Cnk
21 <
2 : kŠ k k 1 Ck2 .k 1/k 21C 2 Vì n  2 I 2 2 D2
2 2 D k2 , nên ta có 2 2 k nk 1 Ck2 22
2 2
: (1.2) kŠ kŠ k 22 Bằng quy nạp, ta chứng minh được 2
< 1. Thật vậy, kŠ 75 Tạp chí Epsilon, Số 04, 08/2015 23=2 Với k D 3, ta có 2
< 1. 2:3 Giả sử bất đẳng thức đã đúng với k 1; k > 3. Ta chứng minh bất đẳng thức đúng với k vì k k 1 1 1 22 2 2
22 22 3 2
D2
0. Điều này cho thấy rằng tồn tại một cách 2 tô màu cho V sao cho không có cạnh cùng màu. 76 Tạp chí Epsilon, Số 04, 08/2015 Dưới đây là một số bài toán liên quan: Bài 1. Cho G D .V; E/ là đồ thị hai mảng n đỉnh với một tập S.v/ chứa nhiều hơn log2 n màu gắn với mỗi đỉnh v 2 V . Chứng minh rằng có một cách tô màu thích hợp cho G mà mỗi đỉnh v được tô một màu từ tập màu S.v/ của nó. Lời giải. Do G là đồ thị hai mảng nên tập V có thể phân hoạch thành hai tập rời S nhau V1 và V2 sao cho mỗi cạnh trong G có một đỉnh trong V1 và một đỉnh trong V2 , đặt S D S.v/ là tập v2V tất cả các màu có thể. Xét phân hoạch ngẫu nhiên S D S1 [ S2 , trong đó mỗi màu được chọn ngẫu nhiên, độc lập cho vào S1 hoặc S2 với xác suất bằng nhau (và bằng 21 ). Ta sẽ chứng minh tồn tại một phân hoạch của S sao cho tất cả các đỉnh trong Vi ; i D 1; 2, có thể được tô màu bằng các màu trong Si ; i D 1; 2. Lấy v 2 Vi ; i D 1; 2; khi đó xác suất để không có màu nào trong tập màu S.v/ nằm trong Si xác định bởi: ...