[Trần Nam Dũng] Phương Pháp Xác Suất

Bài viết này có mục tiêu giới thiệu với bạn đọc những ý tưởng cơ bản nhất trong phương pháp xác suất để áp dụng vào các bài toán thuộc nhiều lĩnh vực. Những ứng dụng này còn mới mẻ với học sinh Việt Nam nên chúng tôi sẽ trình bày từ những vấn đề rất cơ bản. Một phần quan trọng trong bài viết sẽ là những ứng dụng của phương pháp xác suất trong các bài toán Olympic, Trong phần cuối, chúng tôi giới thiệu ứng dụng của phương pháp xác suất để chứng minh một vài định lý quan trọng trong lý thuyết cực trị tập hợp hữu hạn, qua đó giới thiệu đến bạn đọc một số vấn đề của lĩnh vực đang rất phát triển này.

MỘT SỐ BÀI TOÁN MỞ ĐẦU

Lần đầu tiên tôi biết đến ứng dụng của phương pháp xác suất trong các bài toán thi học sinh giỏi trung học phổ thông là qua bài toán đại số sau đây

Bài toán 1 (Bungari, 1984). Cho $x_{i}, y_{i}$, $(i=1,2, \ldots, n)$ là $2 n$ số thực dương sao cho $x_{i}+y_{i}=1$. Chứng minh rằng với mọi số nguyên dương $m$, ta đều có $$\left(1-x_{1} x_{2} \cdots x_{n}\right)^{m}+\left(1-y_{1}^{m}\right)\left(1-y_{2}^{m}\right) \cdots\left(1-y_{n}^{m}\right) \geq 1.$$

Có nhiều lời giải cho bài toán này, trong đó có cách giải thuần túy đại số. Tuy nhiên, các cách giải đó đều khá phức tạp. Lời giải dưới đây của Pierre Bornsztein thật đẹp đẽ và thanh thoát.

Lời giải. Cho $c_{1}, c_{2}, \ldots, c_{n}$ là các đồng xu sao cho với mỗi $i$, xác suất để $c_{i}$ ra mặt sấp là $x_{i}$. Ta tung các xu này một cách độc lập $m$ lần. Khi đó, $\left(1-x_{1} x_{2} \cdots x_{n}\right)^{m}$ là xác suất $P(A)$ của biến cố "với mỗi một trong $m$ lần tung, có ít nhất một đồng xu ra mặt ngửa". Chú ý rằng $A=B \cup C$, trong đó $B$ là biến cố "tồn tại một đồng xu ra mặt ngửa ở mỗi một trong $m$ lần tung", và $C$ là biến cố "có ít nhất một đồng xu ra mặt ngửa ở mỗi lần tung, nhưng đồng xu này không giống nhau qua mỗi lần tung". Hơn nữa, $B \cap C=\varnothing$, do đó $P(A)=P(B)+P(C)$. Mặt khác, $\left(1-y_{1}^{m}\right)\left(1-y_{2}^{m}\right) \cdots\left(1-y_{n}^{m}\right)$ là xác suất của biến cố mỗi một đồng xu ít nhất một lần không ra mặt ngửa trong $m$ lần tung bằng $P(\bar{B})$, trong đó $\bar{B}$ là biến cố đối lập với biến cố $B$. Như vậy bất đẳng thức đã cho là $$\begin{aligned}P(A)+P(\bar{B}) &=P(B)+P(\bar{B})+P(C) \\&=1+P(C) \geq 1 .\end{aligned}$$ Chú ý rằng đẳng thức xảy ra khi và chỉ khi $n=1$. Trong bài toán trên, biểu thức vế trái và đặc biệt là điều kiện $x_{i}+y_{i}=1$ dù sao cũng gợi ý khá nhiều đến ý tưởng xác suất. Thế nhựng trong bài toán sau tuyệt nhiên không có "dấu hiệu" của xác suất.

Bài toán 2 (Putnam 2000 và Singapore, 2012). Cho $a_{j}, b_{j}, c_{j}, 1 \leq j \leq N$ là các số nguyên. Giả sử rằng với mỗi $j$, trong ba số $a_{j}, b_{j}, c_{j}$ có ít nhất một số lẻ. Chứng minh rằng tồn tại các số nguyên $r, s, t$ sao tho $r a_{j}+s b_{j}+t c_{j}$ là lẻ với ít nhất $\frac{4 N}{7}$ giá trị của $j, 1 \leq j \leq N$.

Lời giải. Dưới đây là hai cách giải rất đẹp cho bài toán này.

Cách 1. (Bhargava, Kiran Kedlaya và Lenny Ng) Xét $8$ bộ ba $(r, s, t)$ với $r, s, t \in\{0,1\}$, không phải tất cả đều bằng 0 . Chú ý rằng vì $a_{j}, b_{j}, c_{j}$ không phải tất cả đều chẵn, nên 4 trong các tổng $r a_{j}+s b_{j}+t c_{j}$ là chẵn và 4 là lẻ. Tất nhiên là tổng với $r=s=t=0$ là chã̃n, do đó ít nhất 4 trong 7 tổng với $r, s, t$ không đồng thời bằng 0 có tổng lẻ. Nói cách khác, có ít nhất $4 N$ trong các bộ $(r, s, t, j)$ cho tổng lẻ. Theo nguyên lý Dirichlet, tồn tại một bộ $(r, s, t)$ với ít nhất $\frac{4 N}{7}$ tổng là lẻ.

Cách 2 (Phương pháp xác suất). Xét tất cả theo $\bmod 2$, vì trong bài ta chỉ quan tâm đến tính chẵn lẻ. Có 7 cách chọn bộ $(r, s, t)$ với $r, s, t$ không đồng thời bằng 0 ; với mỗi bộ $(a, b, c)$ có đúng 4 trong 7 bộ sao cho $r a+s b+t c \equiv 1$. Suy ra, với $\left(a_{i}, b_{i}, c_{i}\right)$ đã cho nếu ta chọn ngẫu nhiên $(r, s, t) \neq(0,0,0)$ thì giá trị kỳ vọng của số các biểu thức lẻ là $\frac{4 N}{7}$. Nhưng nếu đây là số trung bình thì phải có ít nhất một bộ $(r, s, t)$ có số này lớn hơn hay bằng $\frac{4 N}{7}$. Bài toán được chứng minh xong. Lời giải trên đây đã sử dụng một nguyên lý rất đơn giản: Nếu trung bình của một số số là $A$ thì có ít nhất một trong các số đó $\geq A$ và ít nhất một trong các số đó $\leq A$. Dưới ngôn ngữ xác suất thì giá tri trung bình sẽ tương ứng với giá tri kỳ vong. Đây là môt nguyên lý rất hữu hiêu mà ta sẽ còn nhắc tới ở những phần sau.

Cuối cùng chúng tôi xin giới thiêu lời giải bài toán APMO 1998 của Leung Wing Chung.

Bài toán 3. Cho $F$ là tập hợp tất cả các bộ $\left(A_{1}, A_{2}, \ldots, A_{n}\right)$ trong đó mỗi $A_{i}, i=$ $1,2, \ldots$, , là tập con của $\{1,2, \ldots, 1998\}$. Giả sử $|A|$ ký hiệu số phần tử của tập hợp $A$, hãy tìm $$\sum_{\left(A_{1}, A_{2}, \ldots, A_{n}\right) \in F}\left|A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right| .$$

Lời giải. Chú ý rằng tập hợp $\{1,2, \ldots, 1998\}$ có $2^{1998}$ tập con. Vì ta có thể chọn hay không chọn một phần tử vào tập con, nên có tất cả $2^{1998}$ số hạng trong tổng trên. Bây giờ ta tính giá trị trung bình của mỗi số hạng. Với mỗi $i=1,2, \ldots, 1998$, ta có $i$ là phần tử của $A_{1} \cup A_{2} \cup \cdots \cup A_{n}$ nếu và chỉ nếu nó là phần tử của ít nhất một trong các $A_{1}, A_{2}, \ldots, A_{n}$. Xác suất của biến cố này là $1-2^{-n}$. Do đó, giá trị trung bình của mỗi số hạng trong tổng là $1998\left(1-2^{-n}\right)$, và như thế đáp số là $2^{1998 n} \cdot 1998\left(1-2^{-n}\right)$. Chú ý là bài toán này còn có nhiều cách giải khác, trong đó có cách dùng phương pháp đếm theo phần tử khá gần với lý luận ở trên.

Qua các ví dụ trên, ta thấy phương pháp xác suất có những ứng dụng bất ngờ và hiệu quả trong nhiều dạng toán: từ Đại số, Số học đến Tổ hợp. Bên cạnh đó, có thể thấy phương pháp xác suất khá gần gũi với một số kỹ thuật khác như nguyên lý Dirichlet, bài toán đếm, phương pháp đếm theo hai cách...

Bài Tập

1. (IMO 1970) Trên mặt phẳng cho 100 điểm, trong đó không có 3 điểm nào thẳng hàng. Xét tất cả các tam giác có đỉnh tại các điểm đã cho. Chứng minh rằng không quá $70 \%$ các tam giác này là tam giác nhọn.
2. (IMO 1971) Chứng minh rằng với mỗi số nguyên dương $m$, tồn tại tập hữu hạn $S$ các điểm trên mặt phẳng với tính chất sau: Với mỗi điểm $A$ trong $S$, có đúng $m$ điểm của $S$ có khoảng cách 1 đến $A$.
3. (Trung Quốc, 1986) Cho $z_{1}, z_{2}, \ldots, z_{n}$ là các số phức. Chứng minh rằng tồn tại tập con $S \subseteq\{1,2, \ldots,, n\}$ sao cho $$\left|\sum_{j \in S} z_{j}\right| \geq \frac{1}{\pi} \sum_{j=1}^{n}\left|z_{j}\right| .$$
4. (IMO Shortlist, 1987) Chứng minh rằng ta có thể tô màu các phần tử của tập hợp $\{1,2, \ldots, 1987\}$ bởi 4 màu sao cho mọi cấp số cộng 10 phần tử của tập hợp này đều không đơn sắc.
5. (Zarankiewicz) Chứng minh rằng tồn tại một cách chia tập hợp các số nguyên dương thành hai tập con sao cho mỗi tập con đều không chứa cấp số cộng với vô số phần tử và không chứa ba số nguyên liên tiếp.
6. (IMO 1987) Gọi $p_{n}(k)$ là số các hoán vị của tập hợp $\{1, \ldots, n\}, n \geq 1$, có đúng $k$ điểm bất động. Chứng minh rằng $$\sum_{k=0}^{n} k p_{n}(k)=n ! .$$
7. (IMO 1998) Trong một cuộc thi, có $a$ thí sinh và $b$ giám khảo, trong đó $b \geq 3$ là số nguyên lẻ. Mỗi một giám khảo sẽ đánh giá thí sinh "đậu" hoặc "rớt". Giả sử $k$ là số sao cho với mỗi cặp hai giám khảo, đánh giá của họ trùng ở nhiều nhất $k$ thí sinh. Chứng minh rằng $\frac{k}{a} \geq \frac{b-1}{2 b}$.

ĐẠI CƯƠNG VỀ LÝ THUYẾT XÁC SUẤT

Biến Cố Và Xác Suất Của Biến Cố.

Phép thử ngẫu nhiên và không gian mẫu. Phép thử ngẫu nhiên $T$ (gọi tắt là phép thử) là một thí nghiệm hay hành động mà

• Kết quả không dự đoán trước được;
• Có thể xác định được tập hợp tất cả kết quả có thể xảy ra.

Tập tất cả các kết quả có thể xảy ra được gọi là không gian mẫu của phép thử và được ký hiệu là $\Omega$. Ví dụ, hành động gieo hai con súc sắc là một phép thử với không gian mẫu là $$\Omega=\{(1,1),(1,2),(1,3), \ldots,(6,6)\} .$$

Biến cố. Một biến cố $A$ (hay sự kiện $A$) liên quan đến phép thử $T$ là biến cố mà việc xảy ra hay không xảy ra của nó tùy thuộc vào kết quả của $T$. Mỗi kết quả của phép thử $T$ làm cho biến cố $A$ xảy ra được gọi là một kết quả thuận lợi của $A$. Tập hợp các kết quả thuận lợi cho $A$ hay được ký hiệu bởi $\Omega_{A}$. Trong bài này, để đơn giản ta dùng $A$ để ký hiệu $\Omega_{A}$, ta cũng nói biến cố $A$ được mô tả bởi tập $A$. Biến cố chắc chắn là biến cố luôn xảy ra khi thực hiện phép thử $T$. Biến cố chắc chắn được mô tả bởi tập $\Omega$ và được ký hiệu là $\Omega$. Biến cố không thể là biến cố không bao giờ xảy ra khi thực hiện phép thử $T$. Biến cố không thể được mô tả bởi tập rỗng và được ký hiệu là $\varnothing$.

Xác suất của biến cố. Định nghĩa cổ điển của xác suất. Giả sử phép thử $T$ có một số hữu hạn kết quả và có đồng khả năng. Khi đó xác suất của một biến cố $A$ liên quan tới $T$ là $$P(A)=\frac{|A|}{|\Omega|} .$$ Như vậy, việc tính xác suất của một biến cố $A$ được quy về bài toán tổ hợp: đếm số kết quả có thể của $T$ và đếm số kết quả thuận lợi của $A$. Một giả thiết quan trọng khi áp dụng định nghĩa này là các kết quả của phép thử $T$ (tức là các phần tử của $\Omega$ ) được coi là có khả năng xảy ra như nhau.

Ví dụ 2.1. Rút ngẫu nhiên 5 quân bài từ bộ bài 52 quân. Tính xác suất của các biến cố

• A: Tất cả 5 quân đều cùng màu;
• B: Không có quân nào có giá trị giống nhau;
• C: Có hai đôi và một quân khác.

Lời giải. Có $C_{52}^{5}$ cách rút 5 quân bài từ bộ bài 52 quân, tức là $|\Omega|=C_{52}^{5}$. Để xảy ra sự kiện $A$, đầu tiên ta chọn ra một trong hai màu. Với mỗi màu có $C_{26}^{5}$ cách chọn ra 5 quân của màu đó. Vậy xác suất của biến cố $\mathrm{A}$ là $$P(A)=\frac{2 C_{26}^{5}}{C_{52}^{5}} .$$ Với biến cố $\mathrm{B}$, đầu tiên ta chọn 5 giá trị khác nhau từ 13 giá trị, có $C_{13}^{5}$ cách chọn như vậy. Với 5 giá trị này, vì mỗi giá trị tương ứng với 4 quân bài của 4 chất nên ta có 4 cách chọn. Có tất cả $C_{13}^{5} \cdot 4^{5}$ cách chọn, và như thế $$P(B)=\frac{C_{13}^{5} \cdot 4^{5}}{C_{52}^{5}} .$$ Tính xác suất của biến cố $\mathrm{C}$ xin được dành lại cho bạn đọc.

Định nghĩa thống kê của xác suất. Xét phép thử $T$ và biến cố $A$ liên quan đến $T$. Ta không cần giả sử các kết quả của phép thử có đồng khả năng. Tiến hành lặp đi lặp lại $N$ lần phép thử. Giả sử trong $N$ lần đó, biến cố $A$ xuất hiện $k=k(N)$ lần. Người ta chứng minh được rằng khi $N$ tiến ra vô cùng thì tỉ sô $\frac{k(\dot{N})}{N}$ luôn dần tới một giới hạn xác định. Giới hạn đó được gọi là xác suất của $A$, tức là $$P(A)=\lim _{N \rightarrow \infty} \frac{k(N)}{N} .$$ Trong trường hợp phép thử $T$ có một số hữu hạn kết quả có thể đồng khả năng thì xác suất của biến cố $A$ theo định nghĩa thống kê cũng trùng với xác suất của biến cố $A$ theo định nghĩa cổ điển. Tỉ số $\frac{k(N)}{N}$ được gọi là tần suất của $A$ trong $N$ lần thực hiện phép thử $T$. Khi $N$ càng lớn thì tần suất này càng gần với xác suất. Thành thử tần suất được xem như giá trị gần đúng của xác suất.

Quy Tắc Cộng Xác Suất.

Biến cố hợp. Cho hai biến cố $A$ và $B$. Biến cố " $A$ hoặc $B$ xảy ra", ký hiệu là $A \cup B$, được gọi là biến cố hợp của hai biến cố $A$ và $B$. Một cách tổng quát, cho $k$ biến cố $A_{1}, A_{2}, \ldots, A_{k}$. Biến cố "có ít nhất một trong các biến cố $A_{1}, A_{2}, \ldots, A_{k}$ xảy ra”, ký hiệu là $A_{1} \cup A_{2} \cup \cdots \cup A_{k}$, được gọi là hợp của các biến cố đó.

Biến cố xung khắc. Hai biến cố $A$ và $B$ được gọi là xung khắc với nhau nếu như biến cố này xảy ra thì biến cố kia không xảy ra.

Biến cố đối. Cho $A$ là một biến cố. Khi đó biến cố "không xảy ra $A$ " được gọi là biến cố đối của $A$, ký hiệu là $\bar{A}$. Rõ ràng $A$ và $\bar{A}$ là hai biến cố xung khắc và hợp của chúng là một biến cố chắc chắn $\Omega=A \cup \bar{A}$.

Quy tắc cộng xác suất.

• Nếu hai biến cố $A$ và $B$ xung khắc với nhau thì $P(A \cup B)=P(A)+P(B)$.
• Nếu $A_{1}, A_{2}, \ldots, A_{k}$ là $k$ biến cố đôi một xung khắc với nhau thì $$P\left(A_{1} \cup A_{2} \cup \cdots \cup A_{k}\right)=P\left(A_{1}\right)+P\left(A_{2}\right)+\cdots+P\left(A_{k}\right) .$$
• $P(\bar{A})=1-P(A)$.

Xác Suất Có Điều Kiện.

Biến cố giao. Cho hai biến cố $A$ và $B$. Biến cố "cả $A$ và $B$ đều xảy ra", ký hiệu là $A B$, được gọi là giao của hai biến cố $A$ và $B$. Một cách tổng quát, giao của $k$ biến cố $A_{1}, A_{2}, \ldots, A_{k}$ là biến cố "tất cả biến cố $A_{1}, A_{2}, \ldots, A_{k}$ đều xảy ra", ký hiêu là $A_{1} A_{2} \cdots A_{k}$

Xác suất có điều kiện. Nếu $A$ và $B$ là hai biến cố với $P(B)>0$ thì ta định nghĩa xác suất có điều kiện của biến cố $A$ biết $B$ đã xảy ra là $$P(A \mid B)=\frac{P(A B)}{P(B)} .$$ Xác suất có điều kiện có một số tính chất trực quan đẹp đẽ sau:

• Nếu $A B=\varnothing$ thì $P(A \mid B)=0$.
• Nếu $A \subset B$ thì $P(A \mid B) \geq P(A)$.
• Nếu $A \supset B$ thì $P(A \mid B)=1$.

Quy tắc nhân. Từ định nghĩa xác suất có điều kiện, ta suy ra $$P\left(A_{2} A_{1}\right)=P\left(A_{2} \mid A_{1}\right) \cdot P\left(A_{1}\right) .$$ Tương tự, $$P\left(A_{3} A_{2} A_{1}\right)=P\left(A_{3} \mid A_{2} A_{1}\right) \cdot P\left(A_{2} A_{1}\right) =P\left(A_{3} \mid A_{2} A_{1}\right) \cdot P\left(A_{2} \mid A_{1}\right) \cdot P\left(A_{1}\right)$$ Tiếp tục như thế, ta được $$P\left(A_{n} \cdots A_{2} A_{1}\right)= P\left(A_{n} \mid A_{n-1} \cdots A_{1}\right) \cdots P\left(A_{2} \mid A_{1}\right) \cdot P\left(A_{1}\right) .$$

Biến cố độc lập. Hai biến cố $A$ và $B$ được gọi là độc lập với nhau nếu việc xảy ra hay không xảy ra của biến cố này không làm ảnh hưởng đến xác suất xảy ra của biến cố kia, nói cách khác, $P(A \mid B)=$ $P(A)$ và $P(B \mid A)=P(B)$. Theo định nghĩa xác suất có điều kiện, điều này xảy ra khi và chỉ khi $P(A B)=P(A) \cdot P(B)$. Tổng quát, $k$ biến cố $A_{1}, A_{2}, \ldots, A_{k}$ được gọi là độc lập với nhau nếu việc xảy ra hay không xảy ra của một nhóm bất kỳ trong các biến cố trên không làm ảnh hưởng tới xác suất xảy ra của các biến cố còn lại. Như vậy, nếu $k$ biến cố $A_{1}, A_{2}, \ldots, A_{k}$ là độc lập thì $$P\left(A_{1} A_{2} \cdots A_{k}\right)=P\left(A_{1}\right) \cdot P\left(A_{2}\right) \cdots P\left(A_{k}\right).$$ Đây được gọi là quy tắc nhân xác suất. Chú ý là nếu $A$ và $B$ độc lập thì ta cũng có $A, \bar{B}$ độc lập, $\bar{A}, B$ độc lập và $\bar{A}, \bar{B}$ độc lập.

Quy tắc Bayes. Sử dụng quy tắc nhân xác suất có điều kiện, ta có thể khai triển $P(A B)$ bằng hai cách $$P(A \mid B) \cdot P(B)=P(A B)=P(B \mid A) \cdot P(A).$$ Từ đây ta suy ra quy tắc Bayes như sau $$P(B \mid A)=\frac{P(A \mid B) \cdot P(B)}{P(A)} .$$

Quy Tắc Cộng Mở Rộng.

Trong trường hợp $A$, $B$ là hai biến cố bất kỳ, không nhất thiết xung khắc, để tính xác suất của biến cố $A \cup B$, ta có công thức sau goi là quy tắc công mở rộng của hai biến cố bất kỳ $$P(A \cup B)=P(A)+P(B)-P(A B) .$$ Một cách tổng quát, ta có công thức $$P\left(\bigcup_{i=1}^{n} A_{i}\right) =\sum_{i=1}^{n} P\left(A_{i}\right)-\sum_{1 \leq i<j \leq n} P\left(A_{i} A_{j}\right) +\cdots+(-1)^{n-1} P\left(A_{1} \cdots A_{n}\right) .$$ Công thức trên còn được gọi là công thức bao hàm và loại trừ.

Biến Ngẫu Nhiên Rời Rạc.

Đại lượng $X$ được gọi là biến ngẫu nhiên rời rạc nếu nọ nhận giá trị bằng số thuộc một tập hợp hữu hạn nào đó và giá trị ây là ngẫu nhiên, không dự đoán trước được.

Ví dụ 2.2. Nếu ta tung hai con súc sắc một cách ngẫu nhiên rồi cộng các mặt xuất hiện để được tổng $X$, thì $X$ là một biến ngẫu nhiên rời rạc nhận các giá trị $2,3, \ldots, 12$. 

Phân bố xác suất. Giả sử $X$ là một biến ngẫu nhiên rời rạc nhận các giá trị $\left\{x_{1}, x_{2}, \ldots, x_{n}\right\}$. Để hiểu rõ về $X$, ta cần quan tâm đến xác suất để $X$ nhận các giá trị nói trên là bao nhiêu, tức là cần tính các xác suất $p_{i}=P\left(X=x_{i}\right)$, trong đó $\left\{X=x_{i}\right\}$ là biến cố " $X$ nhận giá trị $x_{i}$ " $\left\{X=x_{i}\right\}$ là biền cô "X nhận giá trị $x_{i}$ " vây đươc trình bày dưới dâng "bảng phân bố xác suất" của $X$ như sau \begin{array}{|l|l|l|l|l|}\hline X & x_{1} & x_{2} & \cdots & x_{n}\\ \hline P & p_{1} & p_{2} & \cdots & p_{n} \\ \hline\end{array}

Ví dụ 2.3. Một túi có 10 chiếc the đỏ và 6 chiếc thẻ xanh. Rút ngẫu nhiên ra ba tấm thẻ. Gọi X là số thẻ đỏ trong ba thẻ rút ra. Lập bảng phân bố xác suất của $X$.

Lời giải. Tính toán trực tiếp, ta có $$P(X=0)=\frac{C_{6}^{3}}{C_{16}^{3}}=\frac{2}{56} .$$ Tương tự, ta nhận được $P(X=1)=\frac{15}{56}$, $P(X=2)=\frac{27}{56}$, và $P(X=3)=\frac{12}{56}$. Bảng phân bố xác suất của $X$ như sau \begin{array}{|c|c|c|c|c|}\hline X & 0 & 1 & 2 & 3 \\ \hline P & \frac{2}{56} & \frac{15}{56} & \frac{27}{56} & \frac{12}{56} \\\hline\end{array}

Hai biến ngẫu nhiên rời rạc độc lập. Cho $X$ và $Y$ là hai biến ngẫu nhiên rời rạc, trong đó $X$ có thể nhận các giá trị $\left\{x_{1}, x_{2}, \ldots, x_{n}\right\}$ và $Y$ có thể nhận các giá trị $\left\{y_{1}, y_{2}, \ldots, y_{m}\right\}, X$ và $Y$ được gọi là độc lập với nhau nếu với mọi $i=1, \ldots, n$ và $j=1, \ldots, m$, hai biến cố $\left\{X=x_{i}\right\}$ và $\left\{Y=y_{j}\right\}$ là độc lập.

Kỳ vọng. Kỳ vọng của $X$, ký hiệu $E(X)$, là một số được tính theo công thức sau $$E(X)=\sum_{i=1}^{n} x_{i} p_{i}.$$ Ý nghĩa. Kỳ vọng $E(X)$ cho ta ý niệm về độ lớn trung bình của biến ngẫu nhiên $X$. Vì thế kỳ vọng còn được gọi là giá trị trung bình của $X$. Ví dụ, biến ngẫu nhiên $X$ ở Ví dụ $2.3$ có kỳ vọng là $$\begin{aligned}E(X) &=0 \cdot \frac{2}{56}+1 \cdot \frac{15}{56}+2 \cdot \frac{27}{56}+3 \cdot \frac{12}{56} \\&=\frac{105}{56}=1.875,\end{aligned}$$ tức là nếu bốc ngẫu nhiên ba thẻ từ 16 thẻ như trên, ta sẽ được trung bình $1.875$ thẻ đỏ. Qua ví dụ trên ta cũng thấy rằng kỳ vọng $E(X)$ không nhất thiết phải là một giá trị của $X$. Kỳ vọng có tính chất quan trọng là tính tuyến tính: Nếu $X, Y$ là hai đại lượng ngẫu nhiên bất kỳ (không nhất thiết độc lập) thì ta có $$E(X+Y)=E(X)+E(Y) .$$

PHƯƠNG PHÁP XÁC SUẤT ỨNG DỤNG TRONG CÁC BÀI TOÁN OLYMPIC

Kết quả đơn giản sau đây là bổ đề chìa khóa cho rất nhiều bài toán giải bằng phương pháp xác suất:

Bổ đề 3.1. Cho $X$ là biến ngẫu nhiên. Khi đó tồn tại điểm nào đó của không gian xác suất mà $X \geq E(X)$, và tồn tại điểm bào đó của không gian xác suất mà $X \leq E(X)$.

Bài toán 4 (Iran TST, 2008). Giả sử rằng 799 đội bóng chuyền tham gia vào một giải đấu mà trong đó hai đội bất kỳ đấu với nhau đúng một lần. Chứng minh rằng tồn tại hai nhóm $A$ và $B$ rời nhau, mỗi nhóm có 7 đội sao cho mô̂i đội bóng của nhóm $A$ đều thua các đội bóng của nhóm $B$.

Lời giải. Xét giải đấu như một đồ thị có hướng đầy đủ. Ta xét $A$ là một tập ngẫu nhiên có 7 phần tử. Gọi $X$ là số đội thắng tất cả các đội của $A$. Gọi $d\left(v^{-}\right)$là bậc vào của $v$, ta có $$E(X)=\frac{\sum_{v} C_{d\left(v^{-}\right)}^{7}}{C_{799}^{7}} .$$ Nhưng $\sum_{v} d\left(v^{-}\right)=C_{799}^{2}$, nghĩa là bậc trong trung bình của một đỉnh đúng bằng 399. Theo tính lồi của hàm $C_{x}^{7}$ ta có $$E(X) \geq \frac{799 C_{399}^{7}}{C_{799}^{7}} \approx 800 \cdot\left(\frac{1}{2}\right)^{7} \approx 6.25 .$$ Do $X$ nhận giá trị nguyên, tồn tại $A$ sao cho $X(A) \geq 7$. Với $A$ như vậy, chỉ cần chọn 7 đội bóng của $B$ từ nhóm đội thắng tất cả các đội của $A$.

Bài toán 5 (Nga, 1996). Trong viện Duma quốc gia có $1600$ đại biểu, lập thành $16000$ tiểu ban, mỗi tiểu ban có $80$ người. Chứng minh rằng ta có thể tìm được hai tiểu ban có ít nhất $4$ thành viên chung.

Lời giải. Chọn ngẫu nhiên một cặp tiểu ban (tức là lấy một cách ngẫu nhiên một cặp trong $C_{16000}^{2}$ cặp). Gọi $X$ là số người có trong cả hai tiểu ban được chọn. Chú ý rằng $X=X_{1}+X_{2}+\cdots+X_{1600}$, trong đó mỗi $X_{i}$ là biến ngẫu nhiên $\{0,1\}$ nói rằng người thứ $i$ có mặt trong cả hai tiểu ban hay không. Theo tính tuyến tính của kỳ vọng, ta có $$E(X)=E\left(X_{1}\right)+E\left(X_{2}\right)+\cdots+E\left(X_{1600}\right).$$ Điều thần kỳ ở đây là mỗi một $E\left(X_{i}\right)$ có thể tính dễ dàng. Gọi $n_{i}$ là số tiểu ban mà người thứ $i$ thuộc vào. Khi đó, $$E\left(X_{i}\right)=P(\text { người thứ } i \text { được chọn vào cả hai tiểu ban })=\frac{C_{n_{i}}^{2}}{C_{16000}^{2}} .$$ Thông tin duy nhất mà chúng ta biết về $\left\{n_{i}\right\}$ là tổng của chúng: $\sum_{i} n_{i}=16000 \cdot 80$. Điều này gợi ý chúng ta sử dụng tính lồi để đánh giá $E(X)$ thông qua giá trị trung bình của $\left\{n_{i}\right\}$, được ký hiện là $\bar{n}$ và bằng $\bar{n}=\frac{16000 \cdot 80}{1600}= 800$ $$E(X) \geq \frac{1600 C_{\bar{n}}^{2}}{C_{16000}^{2}}=\frac{1600 C_{800}^{2}}{C_{16000}^{2}}=3.995 .$$ Nhưng theo bổ đề, ta biết rằng sẽ có một kết quả nào đó cho ta $$X \geq 3.995 \text {. }$$ Vì $X$ luôn là số nguyên, kết quả này thực sự phải có $X \geq 4$. Nói riêng, ta kết luận rằng có một cặp hai tiểu ban có ít nhất 4 thành viên chung.

Bài toán 6. Giả sử $a$, $b$, $c$ là các số thực dương sao cho với mọi $n$ nguyên thì $$\lfloor a n\rfloor+\lfloor b n\rfloor=\lfloor c n\rfloor .$$ Chứng minh rằng ít nhất một trong ba số $a, b, c$ nguyên. (Ghi chú. Bạn có thể sử dụng kết quả lý thuyết số quen thuộc sau đây: Nếu $x$ là số vô tỷ thì phần lẻ của các bội số của $x$ phân bố đều trên đoạn $[0,1]$. Nói riêng, nếu ta chọn $n$ một cách ngẫu nhiên trong $\{1,2, \ldots, N\}$ thì $E(\{x n\}) \rightarrow \frac{1}{2}$ khi $N \rightarrow \infty$.)

Lời giải. Giả sử rằng không có số nào trong $a, b, c$ là số nguyên. Chia hai vế cho $n$ và cho $n$ dần đến vô cùng, ta được $a+b=c$. Từ đó ta suy ra $$\{a n\}+\{b n\}=\{c n\} .$$ Nếu $x$ vô tỷ thì $\{x n\}$ phân bố đều trên đoạn $[0,1]$. Nói riêng, nếu ta chọn $n$ một cách ngẫu nhiên trong $\{1,2, \ldots, N\}$ thì $E(\{x n\}) \rightarrow \frac{1}{2}$ khi $N \rightarrow \infty$. Mặt khác, nếu $x$ là số hữu tỷ có dạng tối giản là $\frac{p}{q}$ thì $\{x n\}$ có kỳ vọng tiến đến $\frac{q-1}{2 q}=\frac{1}{2}-\frac{1}{2 q}$. Như vậy nó nằm trong khoảng $\left[\frac{1}{4}, \frac{1}{2}\right)$. Tóm lại, với mọi số không nguyên $x$, ta có $E(\{x n\}) \rightarrow t$, trong đó $t \in\left[\frac{1}{4}, \frac{1}{2}\right]$. Lấy kỳ vọng hai vế của (1), và cho $n$ dần đến vô cùng, ta thấy rằng cách duy nhất để có đẳng thức là $E(\{a n\})$ và $E(\{b n\})$ phải tiến đến $\frac{1}{4}$, và $E(\{c n\}) \rightarrow$ $\frac{1}{2}$. Nhưng cách duy nhất để có kỳ vọng $\frac{1}{4}$ là khi $a, b$ hữu tỷ, còn cách duy nhất để có kỳ vọng $\frac{1}{2}$ là $c$ vô tỷ. Nhưng do $a+b=c$ nên ta không thể có hai số hữu tỷ cộng lại ra số vô tỷ. Mâu thuẫn.

Phương pháp xác suất có ứng dụng rất hiệu quả trong việc chứng minh sự tồn tại của một cấu trúc. Sau đây chúng ta xem xét một số ví dụ như vậy: Ta biết rằng trong 6 người bất kỳ tồn tại ba người đôi một quen nhau hoặc ba người đôi một không quen nhau. Khi 6 được thay bởi 5 thì điều này không còn đúng nữa và ta có thể chứng tỏ điều này bằng cách chỉ ra phản ví dụ. Khi các con số là lớn, việc xây dựng phản ví dụ trở nên khó khăn. Trong những trường hợp như thế phương pháp xác suất tỏ ra hữu dụng.

Bài toán 7. Chứng minh rằng giũa $2^{100}$ người, không nhất thiết phải có $200$ người đôi một quen nhau hoặc $200$ người đôi một không quen nhau.

Lời giải. Ta sẽ cho một cặp hai người bất kỳ quen nhau hoặc không quen nhau bằng cách tung một đồng xu đối xứng. Trong một nhóm gồm 200 người, xác suất để họ đôi một quen nhau hoặc đôi một không quen nhau là $$2 \cdot 2^{-C_{200}^{2}}=2^{-19899}.$$ Vì có $C_{2^{100}}^{200}$ cách chọn ra 200 người, xác suất tồn tại 200 người đôi một quen nhau hoặc đôi một không quen nhau nhiều nhất bằng $$C_{2^{100}}^{200} \cdot 2^{-19899}<\frac{\left(2^{100}\right)^{200}}{200 !} \cdot 2^{-19899}<1 .$$ Từ đây suy ra xác suất không tồn tại 200 người đôi một quen nhau hoặc đôi một không quen nhau lớn hơn 0 . Nói cách khác, không nhất thiết phải có 200 người đôi một quen nhau hoặc 200 người đôi một không quen nhau. Bài toán được chứng minh. Ta thấy ở đây một phương pháp tổng quát để xây dựng ví dụ ngẫu nhiên: Nếu xác suất của tồn tại ví dụ ta cần là dương thì tồn tại ví dụ đó.

Bài toán 8. Trong mỗi ô của bảng $100 \times$ 100 , ta viết một trong các số nguyên $1,2, \ldots, 5000$. Hơn nữa, mỗi một số nguyên xuất hiện trong bảng đúng hai lần. Chứng minh rằng ta có thể chọn được 100 ô của bảng thỏa mân ba điều kiện sau

• (1) Mỗi một hàng được chọn đúng một ô.
• (2) Mỗi một cột được chọn đúng một ô.
• (3) Các số trong các ô được chọn đôi một khác nhau.

Lời giải. Chọn hoán vị ngẫu nhiên $\left(a_{1}, \ldots, a_{100}\right)$ của $\{1, \ldots, 100\}$ và chọn ô thứ $a_{i}$ trong hàng thứ $i$. Cách chọn như vậy thỏa mãn (1) và (2). Với mỗi $j=1,2, \ldots, 5000$, xác suất để chọn hai ô có cùng số $j$ là 0 nếu hai ô này cùng hàng hoặc cùng cột và là $\frac{1}{100} \cdot \frac{1}{99}$ trong trường hợp ngược lại. Do đó xác suất để cách chọn này thỏa mãn (3) ít nhất là $$1-5000 \cdot \frac{1}{100 \cdot 999}>0$$ và ta có điều phải chứng minh.

Tất nhiên, ta có thể dễ dàng chuyển hai lời giải xác suất nói trên sang lời giải chỉ sử dụng thuần túy phép đếm (bằng cách tính số các kết quả thuận lợi thay vì tính xác suất), mà thực chất sẽ hoàn toàn giống. Nhưng, theo chúng tôi, lời giải xác suất ngắn gọn và tự nhiên hơn. Một tính chất mang tính đặc trưng của xác suất là đẳng thức $$P\left(A_{1}\right)+P\left(A_{2}\right)+\cdots+P\left(A_{n}\right)=1,$$ nếu $\left\{A_{1}, A_{2}, \ldots, A_{n}\right\}$ là một phân hoạch của không gian xác suất $\Omega$. Tính chất này có thể dùng để chứng minh nhiều đẳng thức tổ hợp bằng phương pháp xác suất. Ta bắt đầu bằng bài toán đơn giản sau

Bài toán 9. Cho $p$, $q$ là các số thực dương sao cho $p+q=1$. Chứng minh rằng $$p+p q+p q^{2}+p q^{3}+\cdots=1 .$$

Lời giải. Xét thí nghiệm tung đồng xu với xác suất ra mặt ngửa là $p$ và mặt xấp là $q$. Ta thực hiện thí nghiệm cho đến khi ra được mắt ngửa. Goi $X$ là số lần tung, khi đó $$P(X=n)=p q^{n-1} .$$ Vế trái của đẳng thức trên bằng $P(X=$ 1) $+P(X=2)+\cdots+P(X=n)+\cdots$ và dĩ nhiên là bằng $1$.

Bài toán 10 (IMO Shortlist, 2006). Cho $S$ là tập hṹu hạn các điểm trên mặt phẳng sao cho không có ba điểm nào thẳng hàng. Với mỗi một đa giác lồi $P$ với các đỉnh thuộc $S$, gọi a $(P)$ là số các đỉnh của $P$ và $b(P)$ là số các điểm của $S$ nằm ngoài $P$. Chứng minh rằng với mọi số thực $x$, ta có đẳng thức $$\sum_{P} x^{a(P)}(1-x)^{b(P)}=1,$$ trong đó tổng được tính theo tất cả các đa giác lồi có đỉnh thuộc $S$. (Chú ý quan trọng: đoạn thẳng, một điểm và tập rỗng được coi là đa giác lồi với $2$, $1$ và $0$ đỉnh tương ứng.)

Lời giải. Ta tô màu một cách ngẫu nhiên các điểm bằng màu đen và màu trắng, trong đó các điểm được tô màu đen với xác suất $x$. Với mỗi đa giác lồi $P$, gọi $E_{P}$ là biến cố tất cả các đỉnh của $P$ có màu đen và tất cả các điểm nằm ngoài $P$ có màu trắng. Các biến cố này đôi một xung khắc nhau, như thế vế trái là xác suất của sự kiện có một $E_{P}$ nào đó đúng. Nhưng đây là sự kiện chắc chắn xảy ra: ta chỉ cần xét bao lồi của tất cả các điểm màu đen! Để tính xác suất của một biến cố theo định nghĩa cổ điển ta thường phải giải quyết hai bài toán tổ hợp: tính số các kết quả thuận lợi và tính số các kết quả có thể. Thông thường, bài toán sau đơn giản hơn bài toán trước. Điều này tao ra một tình huống ứng dưng thú vị: Nếu ta tính được số kết quả có thể và xác suất thì sẽ tính được số kết quả thuận lợi.

Bài toán 11. Trong số cách chọn ra ba đỉnh từ 8 đỉnh của hình lập phương đơn vị, có bao nhiêu cách chọn mà ba đỉnh được chọn là đỉnh của một tam giác đều?

Bài toán này không khó, nhưng cũng khá rối. Ta giải bài này bằng cách tính xác xuất ba đỉnh được chọn ngẫu nhiên tạo thành ba đỉnh của một tam giác đều.

Lời giải. Ta lần lượt chọn các đỉnh

• Đỉnh đầu tiên có thể là một đỉnh bất kỳ.
• Với đỉnh thứ hai, khi đỉnh thứ nhất đã được chọn thì ta chỉ có thể chọn một trong ba đỉnh có khoảng cách $\sqrt{2}$ đến đỉnh đầu. Xác suất thành công là $\frac{3}{7}$.
• Ở lượt cuối, xác suất thành công là $\frac{2}{6}$.

Như vậy xác suất để ba đỉnh được chọn là ba đỉnh của một tam giác đều sẽ là $\frac{1}{7}$. Vì số cách chọn ba đỉnh từ 8 đỉnh là $C_{8}^{3}$ nên số cách chọn thỏa mãn điều kiện 3 đỉnh được chọn là đỉnh của một tam giác đều sẽ bằng $\frac{1}{7} C_{8}^{3}=8$.

Các ví dụ trên đây cho thấy phương pháp xác suất đôi khi mạnh hơn các phương pháp truyền thống. Ta kết thúc phần này bằng ví dụ sau, sử dụng một tính chất mang tính hiển nhiên của xác suất, đó là xác suất của một biến cố luôn nằm giữa $0$ và $1$.

Bài toán 12. Trong một kỳ thi có n môn thi, trong đó có đề tiếng Pháp và đề tiếng Anh. Thí sinh có thể thi bao nhiêu môn tùy ý nhưng chỉ có thể chọn một trong hai ngôn ngũ cho mỗi môn thi. Với hai môn thi bất kỳ, tồn tại một thí sinh thi hai môn này bằng các ngôn ngû̃ khác nhau. Nếu mỗi một môn có nhiều nhất 10 thí sinh dự thi, hã̃ tìm giá trị lớn nhất có thể của $n$.

Lời giải. Đáp số là $1024$. Ví dụ sau đây cho thấy $n=1024$ là có thể. Giả sử có $10$ thí sinh (đánh số từ $1$ đến $10$) tham dự tất cả $1024$ môn thi (đánh số từ $0$ đến $1023$). Với thí sinh $i$, môn thi thứ $j$ sẽ được thi bằng tiếng Pháp nếu chữ số thứ $i$ tính từ bên phải sang trong biểu diễn nhị phân của $j$ là 0 và sẽ thi bằng tiếng Anh trong trường hợp ngược lại. Bằng cách này dễ dàng kiểm tra được điều kiện được thỏa mãn. (Kết quả cũng như ví dụ có thể thu được không mấy khó khăn nếu ta thay $10$ bằng một số nhỏ hơn và quan sát quy luật.) Để chứng minh rằng $1024$ là số lớn nhất, ta gán ngẫu nhiên cho các thí sinh là "người Pháp" hoặc "người Anh". Gọi $E_{j}$ là biến cố "mọi thí sinh thi môn $j$ đều thi bằng đề đúng với quốc tịch mình được gán". Vì có nhiều nhất 10 thí sinh ở mỗi môn, ta có xác suất $P\left(E_{j}\right) \geq 2^{-10}$. Vì với hai môn thi bất kỳ, tồn tại một thí sinh thi hai môn này bằng hai ngôn ngữ khác nhau, nên không có hai $E_{j}$ nào có thể xảy ra đồng thời. Từ đây ta suy ra $$P(\text { ít nhất một trong các } E_{j} \text { xảy ra)} = P\left(E_{1}\right)+\cdots+P\left(E_{n}\right) \geq \frac{n}{1024} .$$ Nhưng vì xác suất của một biến cố bất kỳ không vượt quá $1$ nên từ đây ta suy ra $1 \geq \frac{n}{1024}$, hay $n \leq 1024$. Đó chính là điều phải chứng minh.

Bài Tập

1. Trong bảng $n \times n$ mỗi một trong các số $1,2, \ldots, n$ xuất hiện đúng $n$ lần. Chứng minh rằng tồn tại ít nhất một hàng hoặc một cột với ít nhất $\sqrt{n}$ số phân biệt.
2. (IMO Shortlist, 1999) Cho $A$ là một tập hợp gồm $n$ thặng dư modulo $n^{2}$. Chứng minh rằng tồn tại tập hợp $B$ gồm $n$ thặng dư modulo $n^{2}$ sao cho ít nhất một nửa thặng dư modulo $n^{2}$ có thể viết dưới dạng $a+b$ với $a \in A$ và $b \in B$.
3. Trong một giải cờ vua có 40 kỳ thủ. Có tổng cộng 80 ván đã được đấu, và hai kỳ thủ bất kỳ đấu với nhau nhiều nhất một lần. Với một số nguyên $n$, chứng minh rằng tồn tại $n$ kỳ thử chưa hề đầu với nhau. (Tất nhiên là số $n$ càng lớn càng tốt.)
4. Cho $A_{1}, \ldots, A_{n}$ và $B_{1}, \ldots, B_{n}$ là các tập con hữu hạn khác nhau của $\mathbb{N}$ sao cho
   • $A_{i} \cap B_{i}=\varnothing$ với mọi $i$;
   • $\left(A_{i} \cap B_{j}\right) \cup\left(A_{j} \cap B_{i}\right) \neq 0$ với mọi $i \neq j$.
   Chứng minh rằng với mọi số thực $p, 0 \leq$ $p \leq 1$, ta có $$\sum_{i=1}^{n} p^{\left|A_{i}\right|}(1-p)^{\left|B_{i}\right|} \leq 1 .$$
5. (Bay Area MO, 2004) Cho $n$ số thực không đồng thời bằng 0 và có tổng bằng 0 . Chứng minh rằng tồn tại một cách đánh số $a_{1}, a_{2}, \ldots, a_{n}$ các số này sao cho $$a_{1} a_{2}+a_{2} a_{3}+\cdots+a_{n-1} a_{n}+a_{n} a_{1}<0$$
6. Cho $p$ và $q$ là các số không âm có tổng bằng 1 và $m, n$ là các số nguyên không âm. Chứng minh rằng $\left(1-p^{m}\right)^{n}+\left(1-q^{n}\right)^{m} \geq 1$.
7. (Mỹ TST, 2001) Với tập hợp $S$, ký hiệu $|S|$ là số phần tử của $S$. Cho $A$ là tập hợp các số nguyên dương với $|A|=2001$. Chứng minh rằng tồn tại tập $B$ sao cho
• $B \subseteq A$;
• $|B| \geq 668$;
• Với mọi $u, v \in B$ (không nhất thiết phân biệt), ta có $u+v \in B$.

PHƯƠNG PHÁP XÁC SUẤT TRONG LÝ THUYẾT TẬP HỢP HỮU HẠN CỰC TRỊ

Trong phần này, chúng tôi trình bày lại những nội dung cơ bản từ bài báo "Probabilistic Method in Extremal Finite Set Theory" [3] của Noga Alon.

Lý thuyết tập hợp hữu hạn cực trị là một trong những lĩnh vực phát triển nhanh nhất trong Tổ hợp, có nhiều ứng dụng trong các lĩnh vực của Toán và Khoa học máy tính, trong đó có Hình học rời rạc, Giải tích hàm, lý thuyết xác suất... Có nhiều ứng dụng của lý luận xác suất trong lý thuyết tập hợp hữu hạn cực trị . Trong những ứng dụng này có nhiều ví dụ về chứng minh xác suất cho sự tồn tại của họ các tập hợp với những điều kiện nào đó, cũng như một số chứng minh các kết quả mà phát biểu dường như không có liên quan gì đến xác suất.

Ba Định Lý Cơ Bản Của Lý Thuyết Tập Hợp Hữu Hạn Cực Trị. 

Trong phần này, chúng ta sẽ xem xét phép chứng minh của ba định lý kinh điển trong lý thuyết tập hợp hữu hạn cực trị , sau đó trình bày mô hình xây dựng ngẫu nhiên.

Mỗi một trong ba kết quả dưới đây có nhiều mở rộng, tổng quát hóa và nhiều ứng dụng. Chứng minh xác xuất đơn giản của chúng minh họa một cách đẹp đẽ các ứng dụng của lý luận xác suất.

Kết quả thứ nhất là định lý Sperner, được nhiều nhà nghiên cứu coi là điểm bắt đầu của lý thuyết tập hợp hữu hạn cực trị . Nhắc lại là họ $F$ các tập con của $\{1,2, \ldots, n\}$ được gọi là đối xích nếu không có tập nào của $F$ chứa trong một tập khác.

Định lý 4.1 (Sperner). Cho $F$ là một đối xích. Khi đó, ta có $$\sum_{A \in F} \frac{1}{C_{n}^{|A|}} \leq 1 .$$

Chứng minh. Gọi $\sigma$ là một hoán vị của $\{1,2, \ldots, n\}$ được chọn ngẫu nhiên với xác suất đều và đặt $$C_{\sigma}=\{\{\sigma(j): 1 \leq j \leq i\}: 0 \leq i \leq n\} .$$ (Trường hợp i $i=0, n$ cho ta $\varnothing,\{1,2, \ldots, n\} \in C_{\sigma}$, tương ứng). Định nghĩa biến ngẫu nhiên $X=\left|F \cap C_{\sigma}\right|$. Rõ ràng $$X=\sum_{A \in F} X_{A},$$ trong đó $X_{A}$ là biến ngẫu nhiên đặc trưng cho $A \in C$. Khi đó, ta có $$e\left(X_{A}\right)=\operatorname{Pr}\left(A \in C_{\sigma}\right)=\frac{1}{C_{n}^{|A|}}$$ vì $C_{\sigma}$ chứa đúng một tập hợp kích thước $|A|$, được phân bố đều trong các $|A|$-tập. Do tính tuyến tính của kỳ vọng nên $$E(X)=\sum_{A \in F} \frac{1}{C_{n}^{|A|}} .$$ Với mỗi $\sigma, C_{\sigma}$ tạo thành một xích - mọi cặp tập hợp đều so sánh được. Vì $F$ là một đối xích nên ta phải có $$X=\left|F \cap C_{\sigma}\right| \leq 1 .$$ Do đó $E(X) \leq 1$ và ta có điều phải chứng minh. Từ kết quả này, cùng với nhận xét rằng $C_{n}^{|A|}$ đạt cực đại với $|A|=\left\lfloor\frac{n}{2}\right\rfloor$, ta dễ dàng suy ra được hệ quả sau về số phần tử lớn nhất của một đối xích.

Hệ quả 4.2. Nếu $F$ là một đối xích thì $$|F| \leq C_{n}^{\left\lfloor\frac{n}{2}\right\rfloor} .$$ Kết quả thứ hai là định lý Erdös-Ko-Rado. Họ $F$ các tập hợp được gọi là giao nếu với mỗi $A, B$ thuộc $F$, ta có $A \cap B \neq \varnothing$.

Định lý 4.3 (Erdös-Ko-Rado). Giả sử $n \geq 2 k$ và $F$ là một họ giao các tập con $k$ phần tử của một tập n phần tử. Khi đó, ta có $$|F| \leq C_{n-1}^{k-1} .$$ Chú ý rằng kết quả này là chặt: ta có thể chọn họ tất cả các $k$-tập cùng chứa chung một phần tử cho trước nào đó. Chứng minh ngắn gọn dưới đây được đưa ra bởi G. Katona (1972).

Chứng minh. Giả sử $F$ là một họ giao các tập con của $\{0,1, \ldots, n-1\}$. Ta có bổ đề sau.

Bổ đề 4.4. Với $0 \leq s \leq n-1$, đặt $A_{s}=$ $\{s, s+1, \ldots, s+k-1\}$, trong đó phép cộng lấy theo modulo $n$. Khi đó, $F$ chứa nhiều nhất k trong số các tập $A_{s}$.

Chứng minh bổ đề. Do tính đối xứng, ta có thể giả sử $A_{0} \in F$. Các tập hợp $A_{s}$ khác $A_{0}$ có giao với $A_{0}$ gồm $2 k-2$ tập $A_{s}$ với $-(k-1) \leq s \leq k-1, s \neq 0$ (trong đó các chỉ số được lấy theo modulo $n$ ). Các tập hợp này có thể được chia thành $k-1$ cặp tập hợp rời nhau, $A_{i}, A_{i+k}$, với $-k \leq i \leq-1$. Vì $F$ chỉ có thể chứa nhiều nhất một trong hai tập của một cặp như thế nên ta có khẳng định của bổ đề.

Bây giờ ta chứng minh định lý Erdös-KoRado. Giả sử hoán vị $\sigma$ của $\{0, \ldots, n-1\}$ và $i \in\{0, \ldots, n-1\}$ được chọn một cách ngẫu nhiên với phân bố đều và độc lập với nhau và đặt $A=\{\sigma(i), \ldots, \sigma(i+k-1)\}$, trong đó phép cộng theo modulo $n$. Với mọi cách chọn $\sigma$, bổ đề cho ta $$\operatorname{Pr}(A \in F) \leq \frac{k}{n} .$$ Vì thế, $\operatorname{Pr}(A \in F) \leq \frac{k}{n}$. Nhưng $A$ được chọn ngẫu nhiên từ tập hợp tất cả các $k$-tập nên ta có $$\frac{k}{n} \geq \operatorname{Pr}(A \in F)=\frac{|F|}{C_{n}^{k}} .$$ Suy ra $$|F| \leq \frac{k}{n} C_{n}^{k}=C_{n-1}^{k-1} .$$ Định lý được chứng minh.

Ta kết thúc phần này với định lý Bollobas. Chứng minh dưới đây thuộc về Jaeger, Payan và Katona.

Giả sử $F=\left\{\left(A_{i}, B_{i}\right)\right\}_{i=1}^{h}$ là họ các cặp tập con của một tập hợp bất kỳ. Ta gọi $F$ là một $(k, l)$-hệ nếu $\left|A_{i}\right|=k$ và $\left|B_{i}\right|=l$ với mọi $1 \leq i \leq h, A_{i} \cap B_{i}=\varnothing$ and $A_{i} \cap B_{j} \neq \varnothing$ với mọi $1 \leq i \neq j \leq h$.

Định lý 4.5. Nếu $F=\left\{\left(A_{i}, B_{i}\right)\right\}_{i=1}^{h}$ là một $(k, l)$-hệ thì $$h \leq C_{k+l}^{k} .$$

Chứng minh. Đặt $X=\bigcup_{i=1}^{h}\left(A_{i} \cup B_{i}\right)$ và xét thứ tự ngẫu nhiên $\pi$ của $X$. Với mỗi $i, 1 \leq i \leq$ $h$, gọi $X_{i}$ là biến cố mà mọi phần tử của $A_{i}$ đều đứng trước mọi phần tử của $B_{i}$ trong thứ tự này. Rõ ràng $$\operatorname{Pr}\left(X_{i}\right)=\frac{1}{C_{k+l}^{k}} .$$ Ta cũng có thể kiểm tra dễ dàng rằng các biến cố $X_{i}$ là đôi một xung khắc nhau. Thật vậy, giả sử điều này sai và $\pi$ là thứ tự mà ở đó mọi phần tử của $A_{i}$ đều đứng trước mọi phần tử của $B_{i}$ và mọi phần tử của $A_{j}$ đều đứng trước mọi phần tử của $B_{j}$. Không mất tính tổng quát ta có thể giả sử rằng phần tử cuối cùng của $A_{i}$ không xuất hiện sau phần tử cuối cùng của $A_{j}$. Nhưng trong trường hợp này tất cả các phần tử của $A_{i}$ đều đứng trước tất cả các phần tử của $B_{j}$, mâu thuẫn với sự kiện $A_{i} \cap B_{j} \neq \varnothing$. Như vậy, tất cả các biến cố $X+i$ đôi một xung khắc nhau. Từ đó, $$1 \geq \operatorname{Pr}\left(\bigcup_{i=1}^{h} X_{i}\right)=\sum_{i=1}^{h} \operatorname{Pr}\left(X_{i}\right)=h \cdot C_{k+l}^{k},$$ và phép chứng minh hoàn tất. Định lý $4.5$ là chặt. Ta có thể chọn họ $F=\{(A, X \backslash A): A \subset X,|A|=k\}$, trong đó $X=\{1,2, \ldots, k+l\}$.

Xây Dựng Ngẫu Nhiên

Lý luận xác suất rất hữu ích trong việc chứng minh sự tồn tại của các cấu trúc tổ hợp thỏa mãn các điều kiện ràng buộc. Chứng minh tồn tại dạng này được gọi là xây dựng ngẫu nhiên. Sau đây là một ví dụ mẫu mực và đơn giản. Họ $F$ các tập con của tập $N=\{1,2, \ldots, n\}$ được gọi là $k$-độc lập nếu với mọi $k$ tập phân biệt $F_{1}, F_{2}, \ldots, F_{k}$ của $F$, tất cả $2 k$ giao $\bigcap_{i=1}^{k} G_{i}$ đều khác rỗng, trong đó mỗi $G_{i}$ hoặc là $F_{i}$ hoặc phần bù $N \backslash F_{i}$. Kleitman và Spencer đã xét bài toán ước lượng số phần tử lớn nhất của một họ $k$-độc lập. Cận dưới của họ được chứng minh bằng xây dựng ngẫu nhiên.

Định lý 4.6. Nếu $$C_{m}^{k} \cdot 2^{k} \cdot\left(1-2^{-k}\right)^{n}<1,\quad (1)$$ thì tồn tại một họ k-độc lập các tập con của $N=\{1,2, \ldots, n\}$ có số phần tử ít nhất là $m$.

Chứng minh. Giả sử (1) đúng và $v_{1}, v_{2}, \ldots, v_{m}$ là dãy của $m$ vector nhị phân độ dài $n$ được chọn ngẫu nhiên, trong đó mỗi tọa độ của vector $v_{i}$ được chọn ngẫu nhiên và độc lập bằng $0$ hoặc $1$ với xác suất bằng nhau. Với tập hợp cố định $I$ của $k$ chỉ số khác nhau $1 \leq i_{1}<i_{2}<\cdots<i_{k} \leq m$ và mỗi giá trị cố định của $\varepsilon=\left(\varepsilon_{1}, \ldots, \varepsilon_{k}\right) \in\{0,1\}^{k}$, ta ký hiệu $A(I, \varepsilon)$ là biến cố không tồn tại tọa độ $j, 1 \leq j \leq n$ sao cho $v_{i_{l}}(j)=\varepsilon_{l}$ với mọi $1 \leq l \leq k$. Rõ ràng $$\operatorname{Pr}(A(I, \varepsilon))=\left(1-2^{-k}\right)^{n} .$$ Như vậy, theo (1), khả năng không một biến cố $A(I, \varepsilon)$ nào xảy ra có xác suất dương. Gọi $v_{1}, v_{2}, \ldots, v_{m}$ là dãy cố định mà ở đó không một biến cố nào xảy ra và $F_{i}$ là tập con của $N$ có hàm đặc trưng là $v_{i}$. Ta có thể kiểm tra dễ dàng rằng họ $F=\left\{F_{1}, \ldots, F_{m}\right\}$ là $k$-độc lập và phép chứng minh hoàn tất.

Ví dụ ngẫu nhiên thứ hai mà ta sẽ mô tả thuộc về Erdös và Furedi, ví dụ này tương tự với ví dụ trên và có nhiều ứng dụng thú vị trong Hình học tổ hợp.

Mệnh đề 4.7. Với mọi $n \geq 1$, tồn tại họ $F$ gồm $m$ tập con của tập $N=\{1,2, \ldots, n\}$, trong đó $m=\left\lfloor\frac{1}{2}\left(\frac{2}{\sqrt{3}}\right)^{n}\right\rfloor$, sao cho không tồn tại ba phần tử phân biệt $A, B$ và $C$ của $F$ thỏa mãn điều kiện $$A \cap B \subset C \subset A \cup B .\quad (2)$$

Chứng minh. Đặt $m=\left\lfloor\frac{1}{2}\left(\frac{2}{\sqrt{3}}\right)^{n}\right\rfloor$ và chọn một cách ngẫu nhiên và độc lập $2 m$ vector 0,1 độ dài $n$, trong đó mỗi tọa độ của mỗi vector được chọn bằng 0 hoặc 1 một cách động lập với xác suất bằng nhau. Mỗi một vector là vector đặc trưng cho một tập con tương ứng của $N$. Với mỗi bộ ba $a, b$ và $c$ cố định, các vector được chọn, xác suất để các tập hợp tương ứng thỏa mãn bao hàm thức (2) đúng bằng $\left(\frac{3}{4}\right)^{n}$. Thật vậy, (2) có nghĩa là với mọi $i, 1 \leq i \leq$ $n$, ta không thể có $a_{i}=b_{i}=0, c_{i}=1$ hoặc $a_{i}=b_{i}=1, c_{i}=0$. Như thế xác suất để với ba chỉ số $i, j$ và $k$, các tập hợp $A, B, C$ tương ứng với các vector $a, b, c$ tương ứng thỏa mãn (2) là $\left(\frac{3}{4}\right)^{n}$. Vì có $3 C_{2 m}^{3}$ bộ ba như trên, giá trị kỳ vọng các bộ $A, B, C$ thỏa mãn (2) là $3 C_{2 m}^{3}\left(\frac{3}{4}\right)^{n} \leq$ $m$, trong đó bất đẳng thức cuối suy ra từ cách chọn $m$. Như vậy tồn tại một cách chọn họ $X, 2 m$ tập con của $N$ trong đó số các bộ $A, B, C$ thỏa mãn (2) không quá $m$. Bằng cách xóa đi một tập hợp từ mỗi bộ ba như vậy, ta thu được họ $F$ gồm ít nhất $2 m-m$ tập con của $N$ thỏa mãn điều kiện của mệnh đề. Chú ý mọi thành viên của $F$ đều phân biệt vì (2) hiển nhiên được thỏa mãn nếu $A=C$. Phép chứng minh hoàn tất.

Có một số ví dụ độc đáo trong các lĩnh vực khác nhau của Tổ hợp, trong đó phương pháp xác suất đưa ra các phản ví dụ đơn giản cho các giả thuyết vốn từ lâu chưa giải quyết được. Hệ quả sau đây của mệnh đề vừa chứng minh ở trên là một ví dụ như vậy.

Định lý 4.8. Với mọi $n \geq 1$, tồn tại tập hợp có ít nhất $\left[\frac{1}{2}\left(\frac{2}{\sqrt{3}}\right)^{n}\right\rfloor$ diểm trong không gian Euclid n chiều $R^{n}$, sao cho mọi góc xác định bởi ba điểm thuộc tập hợp này là nhỏ hơn $\frac{\pi}{2}$.

Định lý này bác bỏ giả thuyết của Danzer và Grunbaum rằng số phần tử lớn nhất của một tập hợp như vậy nhiều nhất là $2 n-1$. Trước đó Danzer và Grunbaum đã đánh giá được cận trên của số phần tử lớn nhất các điểm trong $R^{n}$ mà góc tạo bởi ba điểm không vượt quá $\frac{\pi}{2}$ là $2^{n}$.

Chứng minh. Ta chọn các điểm của tập hợp $X$ trong $R^{n}$ từ các đỉnh của hình lập phương $n$ chiều. Cũng như trước, ta xem đỉnh của hình lập phương, vốn là các vector 0,1 có độ dài $n$ như vector đặc trưng của các tập con của tập $n$ phần tử. Ta dễ dàng kiểm tra được rằng

• Mọi góc xác định bởi ba điểm bất kỳ của hình lập phương $n$ chiều đều không vượt quá $\frac{\pi}{2}$.
• Ba đỉnh $a, b$ và $c$ của hình lập phương $n$ chiều, tương ứng với các tập hợp $A, B$ và $C$,, sẽ xác định một góc vuông tại $c$ khi và chỉ khi (2) đúng.

Kết quả định lý được suy ra trực tiếp từ Mệnh đề 4.1.

HƯỚNG DẪN GIẢI CÁC BÀI TẬP

Trong phần này, chúng tôi hướng dẫn ngắn gọn cho các bài tập đề nghị ở phần 1 và phần 3.

Hướng Dẫn Giải Bài Tập Phần 1

1. Trước hết ta chứng minh rằng trong 4 điểm, xác suất để một tam giác là nhọn không quá $75 \%$. Sử dụng kêt quả này, hãy chứng minh rằng trong 5 điểm thì xác suất một tam giác là nhọn không quá $70 \%$. Cuối cùng sử dụng kế quả này để giải bài toán.
2. Chọn $m$ vector ngẫu nhiên trên đường tròn đơn vị. Gọi $S$ là tập hợp các tổng của mỗi một trong $2^{m}$ tập con các vector.
3. Cho $r$ là một tia ngẫu nhiên xuất phát từ gốc tọa độ. Gọi $S$ là tập các chỉ số $j$ sao cho $z_{j}$ tạo một góc nhọn với $r$. Xét hình chiếu của mỗi $z_{j}$ lên $r$. Kỳ vọng của trị tuyệt đối của mỗi hình chiếu là bao nhiêu?
4. Xét một phép tô ngẫu nhiên các số từ 1 đến 1987 bằng 4 màu. Xác suất để một cấp số cộng độ dài 10 đơn sắc bằng bao nhiêu? Có bao nhiêu cấp số cộng độ dài 10 trong $1,2, \ldots, 1987 ?$
5. Tô màu mỗi số nguyên lẻ bằng hai màu đỏ và xanh một cách ngẫu nhiên. Tô màu mỗi số chẵn bằng màu đối của màu số lẻ trước nó.
6. Gọi $f$ là một hoán vị ngẫu nhiên của $1,2, \ldots, n$. Xác suất để 1 là điểm bất động bằng bao nhiêu? 2? Và cứ như thế cho đến n. Cộng các xác suất này lại để tìm kỳ vọng của số các điểm bất động của $f$. Bạn có thấy là kết quả này giống với kết quả bài toán đã cho?
7. Gọi $C$ là một thí sinh ngẫu nhiên. Gọi $p$ là số các giám khảo cho $C$ đậu và $f$ là số các giám khảo cho $C$ rớt. Sử dụng bất đẳng thức $$C_{p}^{2}+C_{f}^{2} \geq \frac{(b-1)^{2}}{4} .$$ Lấy kỳ vọng của cả hai vế. Bạn có thể giải thích $E\left(C_{p}^{2}\right)$ thế nào theo ngôn ngữ bài toán ban đầu? $E\left(C_{f}^{2}\right)$ ?

Hướng Dẫn Giải Bài Tập Phần 3

1. Chọn ngẫu nhiên một hàng hoặc một cột (2n cách chọn). Gọi $X$ là số phần tử khác nhau trên nó. Bây giờ $X=\sum I_{i}$, trong đó mỗi $I_{i}$ là biến đặc trưng cho sự xuất hiện của phần tử $i$ (có thể là hơn một lần) trong hàng hoặc cột ngẫu nhiên của chúng ta. Rõ ràng mỗi $E\left(I_{i}\right)=P\left(I_{i} \geq 1\right)$. Để đánh giá chặn dưới, ta nhận xét rằng trường hợp xấu nhất xảy ra khi tất cả $n$ lần xuất hiện của $i$ đều ở trong một ma trận con $\sqrt{n} \times \sqrt{n}$, do đó $$P\left(I_{i} \geq 1\right) \geq \frac{2 \sqrt{n}}{2 n}=\frac{1}{\sqrt{n}} .$$ Từ đây, do tính tuyến tính nên $E(X) \geq \sqrt{n}$.
2. Gọi $B$ là tập $n$ thặng dư $\bmod n^{2}$ được chọn một cách ngẫu nhiên (có lặp). Bạn có thể đánh giá chặn trên xác suất một thặng dư nào đó không nằm trong $A+B$?
3. Ta gán một xếp hạng ngẫu nhiên cho 40 kỳ thủ, và ta chọn ra những người chỉ chơi với những người có thứ hạng thấp hơn. Chú ý rằng bằng cách này hai kỳ thủ bất kỳ được chọn không đấu với nhau. Giả sử rằng kỳ thủ thứ $i$ chơi $d_{i}$ ván. Vì có $80$ ván đấu ta có $$_{1}+d_{2}+\cdots+d_{40}=80 \cdot 2 .$$ Ta cũng thấy, kỳ thủ thứ $i$ được chọn nếu và chỉ nếu anh ta được gán thứ hạng cao nhất giữa chính anh ta và những người anh ta chơi với, và xác suất của sự kiện này là $\frac{1}{d_{i}+1}$. Như vậy số trung bình kỳ thủ được chọn là $$\frac{1}{d_{1}+1}+\cdots+\frac{1}{d_{40}+1} \geq \frac{40^{2}}{d_{1}+\cdots+d_{40}+40}=\frac{40^{2}}{160+40}=8 .$$ Ở đây ta sử dụng bất đẳng thức CauchySchwarz. Có nghĩa là tồn tại $8$ kỳ thủ đôi một không đấu với nhau.
4. Ta tạo ra một tập con ngẫu nhiên của tập vũ trụ bằng cách chọn mỗi một phần tử với xác suất $p$. Gọi $E_{i}$ là biến cố mà mọi phần tử trong $A_{i}$ được chọn và mọi phần tử trong $B_{i}$ không được chọn, thế thì vế trái là xác suất để một $E_{i}$ nào đó xảy ra, và do đó $\leq 1$.
5. Giả sử $a_{1}, a_{2}, \ldots, a_{n}$ là hoán vị ngẫu nhiên của các số ban đầu. Giá trị kỳ vọng của biểu thức vế trái bằng bao nhiêu?
6. Xét một ma trận ngẫu nhiên kích thước $m \times n$ trong đó mỗi một ô được điền số $1$ với xác suất $p$ và số $0$ với xác suất $q$. Xác suất để mỗi một dòng có ít nhất một số $1$ bằng bao nhiêu? Xác suất để mỗi cột có ít nhất một số $0$ bằng bao nhiêu?

TÀI LIỆU THAM KHẢO

1. Đoàn Quỳnh, Trần Nam Dũng, Nguyễn Vũ Lương, Đặng Hùng Thắng, Tài liệu Giáo khoa chuyên Toán, Đại số và Giải tích 11 , Nhà xuất bản Giáo dục Việt Nam, $2010 .$
2. Noga Alon, Joel Spencer, The Probabilistic Method,
3. Noga Alon, Probabilistic Method in Extremal Finite Set Theory.
4. Law Ka Ho, Probabilistic Method, Mathematica Excalibur, October-November $2009 .$
5. Manjul Bhargava, Kiran Kedlaya và Lenny $\mathrm{Ng}$, Solutions to the 61st William Lowell Putnam Mathematical Competition.
6. Ravi Boppana, Unexpected Uses of Probability.
7. Po-Shen Loh, Probabilistic Method in Combinatorics.