Sum Free Set - Một chứng minh đẹp

Đi lang thang lướt trên internet, mình tìm thấy một bài toán rất hay được chứng minh bằng kỹ thuật xác suất của Erdos được post trên blog của Algorithm Soup đúng vào ngày sinh của mình.

Định lý (Erdos, 1965):

Một tập hợp $X$ được gọi là sum-free nếu $\forall a,b \in X$, ta luôn có $a+b \not \in X$. Với mọi tập $S$ hữu hạn của các số nguyên dương, luôn tồn tại một tập hợp sum-free set $X \subset S$ thỏa $\displaystyle |X| \gt \frac {|S|} 3$.

Chứng minh

Đầu tiên, ta giả sử tập $S$ nằm trong trường $\mathbb Z_p$ với $p$ là số nguyên tố được chọn đủ lớn. Đây chính là điểm thú vị của phương pháp này, vì Erdos đã khéo léo tận dụng các tính chất đặc biệt của só nguyên tố để chứng minh mà chúng ta sẽ xem xét kỹ hơn sau đây.

Chọn $p=3k+2$ là số nguyên tố thỏa $p > s, \forall s \in S$.

Thiết lập một sum-free set lớn $\Omega$ trong $\mathbb Z_p$ (không nhất thiết phải là tập con của $S$):

Tập $\Omega$ nằm ở khoảng chính giữa của $\mathbb Z_p$, dễ dàng nhận thấy $\Omega$ cũng là sum-free set trong $\mathbb Z_p$.

Chọn một số ngẫu nhiên $r \in \{1,2,\dots,p-1\}$. Xét tập hợp: $X_r = S \cap (r. \Omega \})$, ta thấy các phần tử tập hợp này có thể viết dưới dạng

Cần chứng minh rằng $X_r$ sum-free và có size lớn hơn $\displaystyle \frac {|S|} 3$.

Rõ ràng, $X_r$ luôn sum-free với mọi $r$ vì xét $a,b,c \in X_r$ nếu $\displaystyle a+b=c \implies \frac a r + \frac b r = \frac cr$ vô lý, vì theo $(*)$: $\displaystyle \frac a r, \frac b r, \frac c r \in \Omega$.

Tiếp theo, chứng minh $\displaystyle |X_r| \gt \frac{|S|} 3$. Thay vì chỉ ra một giá trị cụ thể $r$, Erdos chứng minh mệnh đề xác suất sau:

Kỳ vọng của giá trị $|X_r|$ cho một biến ngẫu nhiên $r$ thỏa:

Rõ ràng, nếu kỳ vọng trên thỏa thì nhất định phải tồn tại một giá trị $r$ nào đó làm cho $\displaystyle |X_r| \gt \frac {|S|} 3$.

Từ $(*)$, ta có thể biểu diễn $\mathbb E[|X_r|]$ là xác suất $rx \in S$ với $x \in \{k+1, k+2, \dots, 2k+1\}$, từ đó:

Để ý rằng, trong $\mathbb Z_p$, mọi phần tử $x \ne 0$ đều là phần tử sinh cộng tính, hay nói cách khác các bội số $x,2x,3x,\dots,(p-1)x$ cũng là một hoán vị của các số $1,2,\dots,p-1$. Vì thế: