tailieunhanh - Ứ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! | Ứ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 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ó k gt 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 lt 1. Ta có .n k C 1 .n k C 2 .n 1 n n n n nk Cnk D lt D kŠ kŠ kŠ Suy ra Ck2 nk 1 Ck2 Cnk 21 lt 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 kŠ kŠ k 22 Bằng quy nạp ta chứng minh được 2 lt 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 lt 1. 2 3 Giả sử bất đẳng thức đã đúng với k 1 k gt 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 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 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