Về bài toán tổ hợp khó nhất thi VN TST 2001

[huynhcongbang]

Trong kì thi VN TST 2001, có hai bài Tổ hợp khá thú vị. Bài đầu tiên là bài 3 của ngày 1 về các cặp nam-nữ trong CLB. Bài này trong sách của thầy Vũ Đình Hoà có một cách giải rất "khiếp" theo lý thuyết graph - đồ thị lưỡng phân; tuy nhiên, trên mathlinks.ro có một cách tiếp cận nhẹ nhàng hơn theo nguyên lí Dirichlet. Bài toán mà mình muốn đề cập trong bài viết này là về bài 5 trong ngày 2. Bài toán về tô màu điểm trong không gian Oxyz.
Có thể phát biểu ban đầu của bài toán rất đơn giản, dễ hiểu nhưng trên thực tế, nó đã dựa trên 2 định lí khó của số học- tổ hợp và đây cũng chính là dạng tổng quát cho 1 bài trong IMO Shortlist 1988.
Dưới đây là đề bài và lời giải đầy đủ cho bài toán đó. Mời mọi người tham khảo thử và đóng góp ý kiến.

Đề bài.
Cho số nguyên dương $n$ lớn hơn 1. Trong không gian vuông góc $Oxyz$, gọi T là tập hợp tất cả các điểm có tọa độ là $(x,y,z)$ với $x,y,z$ là các số nguyên dương thỏa mãn $1\le x,y,z\le n$. Tô màu tất cả các điểm thuộc tập hợp T sao cho: nếu điểm $A({{x}_{0}},{{y}_{0}},{{z}_{0}})$ được tô màu thì những điểm có dạng $B({{x}_{1}},{{y}_{1}},{{z}_{1}})$ với ${{x}_{1}}\le {{x}_{0}},{{y}_{1}}\le {{y}_{0}},{{z}_{1}}\le {{z}_{0}}$ sẽ không được tô màu.
Tìm giá trị lớn nhất các điểm được tô màu thỏa mãn điều kiện trên.

Lời giải.

Nếu hai bộ $(x,y,z)$ và $({x}',{y}',{z}')$ thỏa mãn $x\le {x}',y\le {y}',z\le {z}'$ thì ta nói bộ $({x}',{y}',{z}')$ trội hơn bộ $(x,y,z)$, ta quy ước gọi hai bộ đó là hai bộ trội. Ta có thể phát biểu bài toán dưới dạng tương đương là:
Tìm số lớn nhất $S(n)$ tất cả các bộ $(x,y,z)$ thỏa mãn $0\le x,y,z\le n-1$ sao cho trong đó, không tồn tại hai bộ trội. (thay $1\to 0,n\to n-1$).
Rõ ràng với hai bộ trội bất kì thì tổng của chúng là phân biệt vì nếu có hai bộ trội như trên và tổng bằng nhau thì $x+y+z\le {x}'+{y}'+{z}'$ và đẳng thức xảy ra khi $x={x}',y={y}',z={z}'$, vô lí.
Tổng lớn nhất có thể có của các bộ này là $3(n-1)$ và tổng nhỏ nhất là 0. Ta sẽ chứng minh các mệnh đề sau với hai trường hợp $n$ chẵn và lẻ.
(1) Số các bộ $(x,y,z)$ thỏa mãn $ x+y+z=\left\lceil \frac{3(n-1)}{2} \right\rceil $ và $0\le x,y,z\le n-1$ là $\left\lfloor \frac{3{{n}^{2}}+1}{4} \right\rfloor $.
(2) Với mọi cách chọn $\left\lfloor \frac{3{{n}^{2}}+1}{4} \right\rfloor +1$ đều tồn tại hai bộ mà bộ này là bộ trội của bộ kia.
Ta xét hai trường hợp:
*Nếu $n=2k,k\in \mathbb{N}$ thì ta sẽ đếm số bộ thỏa $x+y+z=\left\lceil \frac{3(2k-1)}{2} \right\rceil =3k-1$ và $1\le x,y,z\le 2k-1$.
+ Nếu $x=0$ thì $y+z=3k-1$ và $k\le y\le 2k-1$: có $k$ nghiệm thỏa.
+ Nếu $x=k$ thì $y+z=2k-1$ và $0\le y\le 2k-1$: có $2k$ nghiệm thỏa.
+ Nếu $x=i,1\le i\le k-1$ thì $y+z=3k-i$ và $k-i\le y\le 2k-1$: có $k+i$ nghiệm thỏa.

Do đó, số nghiệm tổng cộng là $k+2k+2\left( \sum\limits_{i=k+1}^{2k-1}{i} \right)=3k+\frac{2k(2k-1)-k(k+1)}{2}=3{{k}^{2}}$.
Rõ ràng $\left\lfloor \frac{3{{(2k)}^{2}}+1}{4} \right\rfloor =3{{k}^{2}}$. Mệnh đề (1) được chứng minh.
Gọi $A$ là tập hợp tất cả các bộ ba $(x,y,z)$ với $0\le x,y,z\le n-1$ hay $A=\left\{ (x,y,z)|0\le x,y,z\le n-1 \right\}$
Giả sử $B\subset A$ là một tập con có đúng $3{{k}^{2}}$ phần tử.
Ta cần chứng minh rằng trong $B$, tồn tại ít nhất hai bộ mà bộ này là bộ trội của bộ kia.
Ta sẽ chứng minh mệnh đề (2) bằng cách xây dựng các tập con sau đây của tập tất cả các bộ ba:
$\begin{align}
& {{C}_{1}}=\left\{ (x,y,z)\in A|x=0\vee y=2k-1 \right\} \\
& {{C}_{2}}=\left\{ (x,y,z)\in A|\left( x=1\wedge y\le 2k-2 \right)\vee \left( x\ge 1\wedge y=2k-2 \right) \right\} \\
& {{C}_{2}}=\left\{ (x,y,z)\in A|\left( x=2\wedge y\le 2k-3 \right)\vee \left( x\ge 2\wedge y=2k-3 \right) \right\} \\
& ... \\
& {{C}_{k}}=\left\{ (x,y,z)\in A|\left( x=k-1\wedge y\le k \right)\vee \left( x\ge k-1\wedge y=k \right) \right\} \\
\end{align}$
Đặt $C=\bigcup\limits_{i=1}^{k}{{{C}_{i}}}$ và $D=A\backslash C=\left\{ (x,y,z)\in A|x\ge k\wedge y\le k-1 \right\}$.
Xét các tập hợp ${{C}_{i,j}}=\left\{ (x,y,z)\in {{C}_{i}}|z=j \right\}$ trong đó $1\le i\le k,0\le j\le 2k-1$. Rõ ràng có tất cả $2{{k}^{2}}$ tập hợp như thế và chúng là các phân hoạch của $C$.
Xét các tập hợp ${{D}_{p,q}}=\left\{ (x,y,z)\in D|x=p\wedge y=q \right\}$ trong đó $k\le p\le 2k-1,0\le q\le k-1$. Rõ ràng có tất cả ${{k}^{2}}$ tập hợp như thế là chúng là các phân hoạch của $D.$
Ta có hai trường hợp sau:
- Nếu $\left| B\cap C \right|\ge 2{{k}^{2}}$ phần tử thì theo nguyên lí Dirichlet, tồn tại hai bộ thuộc cùng một tập ${{C}_{i,j}}$.
Giả sử hai phần tử $({{x}_{1}},{{y}_{1}},{{z}_{1}}),({{x}_{2}},{{y}_{ 2}},{{z}_{2}})$ cùng thuộc tập ${{C}_{i,j}}=\left\{ (x,y,z)\in {{C}_{i}}|z=j \right\}$. Rõ ràng, ta thấy rằng ${{z}_{1}}={{z}_{2}}=j$ và có ba trường hợp như sau:
+ Nếu ${{x}_{1}}={{x}_{2}}=i-1$ thì ${{y}_{1}},{{y}_{2}}\le i$ nên trong hai bộ trên, phải tồn tại một bộ là bộ trội của bộ kia.
+ Nếu ${{x}_{1}}={{x}_{2}}=i$ thì ${{y}_{1}},{{y}_{2}}\le i-1$ nên trong hai bộ trên, phải tồn tại một bộ là bộ trội của bộ kia.
+ Nếu ${{x}_{1}}=i,{{x}_{2}}\le i-1$ thì ${{y}_{1}}\le i-1,{{y}_{2}}=i$ nên dễ thấy rằng bộ $({{x}_{1}},{{y}_{1}},{{z}_{1}})$ trội hơn bộ $({{x}_{2}},{{y}_{2}},{{z}_{2}}).$
- Nếu $\left| B\cap C \right|<2{{k}^{2}}$ thì $\left| B\cap D \right|>{{k}^{2}}$ thì do $D$ chỉ có ${{k}^{2}}$ phần tử nên tồn tại hai bộ thuộc $D,$ lập luận tương tự trên, ta thấy rằng $B$ chứa hai bộ mà bộ này là bộ trội của bộ kia.
Như thế, hai mệnh đề đã được chứng minh trong trường hợp $n$ chẵn.
* Nếu $n=2k+1,k\in \mathbb{N}$, cách chứng minh hoàn toàn tương tự.
Tóm lại, trong mọi trường hợp, hai mệnh đề ban đầu là đúng.
Từ đó suy ra ta chỉ cần tô màu tất cả các điểm nằm trên mặt phẳng \[x+y+z=\left\lceil \frac{3(n-1)}{2} \right\rceil \] thì số điểm tô được sẽ lớn nhất và là $\left\lfloor \frac{3{{n}^{2}}+1}{4} \right\rfloor $.
Nhận xét.
Để hiểu rõ hơn bản chất của lời giải trên, ta cần phải xem xét hai định lí nổi tiếng sau:
*Định lí de Bruijn-Tengbergen-Kruyswijk:
Với mỗi số nguyên dương $n=p_{1}^{{{a}_{1}}}\cdot p_{2}^{{{a}_{2}}}\cdot p_{3}^{{{a}_{3}}}\cdot ...\cdot p_{k}^{{{a}_{k}}}$, tổng $t(n)={{a}_{1}}+{{a}_{2}}+{{a}_{3}}+...+{{a}_{k}}$ được gọi là bậc của n. Chứng minh rằng tập hợp $S$gồm các ước dương của $n$, có bậc là $\left\lfloor \frac{t(n)}{2} \right\rfloor $ sẽ không chứa hai phần tử nào mà phần tử này chia hết cho phần tử kia.
*Định lí Dilworth:
Một thứ tự bộ phận yếu trên tập P là quan hệ hai ngôi giữa các phần tử trong P. Ta nói hai phần tử $x,y$ so sánh được nếu $x<y$ hoặc $x>y$. Một xích (chain) là một tập hợp Y là con của P sao cho bất kì phần tử nào trong Y đều so sánh được. Nếu không có hai phần tử khác nhau nào của Y so sánh được thì ta có đối xích (antichain). Khi đó, nếu xét $\left| P \right|\ge rs+1$ thì tồn tại xích có kích thước là r hoặc đối xích có kích thước là s.

Các tài liệu phát biểu-chứng minh của chúng có thể tìm được khá nhiều trên mạng. Có lẽ 2 kết quả này chính là cơ sở để xây dựng nên bài toán trên. Rõ ràng, bài toán này có nhiều hướng phát triển và có thể liên hệ được với nhiều vấn đề số học-tổ hợp khác. Các bạn thử tìm hiểu thử xem!

*******************

Thông qua bài toán này, mình cảm nhận được một điều thế này và mình muốn chia sẻ với mọi người!
Trong cuộc sống này, mỗi chúng ta cần tạo ra một điều đặc biệt gì đó riêng cho bản thân mình. Nếu để thua kém một người khác về mọi mặt, như các điểm không được tô màu trong không gian Oxyz kia, thì ta cần phải suy nghĩ lại và cố gắng phấn đấu để thay đổi.

Đây chỉ là suy nghĩ cá nhân thôi, mong mọi người đừng ném đá. Hihi!

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]