Một điểm lưới là một điểm $(x;y)$ trên mặt phẳng tọa độ sao cho $x$, $y$ là các số nguyên dương không vượt quá 20. Ta nói điểm $B=(x^{\prime };y^{\prime })$ nằm về phía Đông Bắc của điểm $A=(x;y)$ nếu $x^{\prime }>x$ và $y^{\prime }>y$. Ba điểm lưới $A$, $B$, $C$ được gọi là một bộ ba Đông Bắc nếu $B$ nằm về phía Đông Bắc của $A$ và $C$ nằm về phía Đông Bắc của $B$.

Một tập hợp gồm 20 điểm lưới được gọi là Lam Sơn nếu mọi đường thẳng đi qua hai điểm trong tập hợp đều không song song với các trục tọa độ, đồng thời tập hợp chứa ít nhất một bộ ba Đông Bắc.

a) Chứng minh rằng trong mỗi tập Lam Sơn luôn tồn tại ba điểm $X$, $Y$, $Z$ sao cho $X{Y}^2\ge X{Z}^2+Z{Y}^2+4$.

b) Hỏi có bao nhiêu tập Lam Sơn?

a) Chọn một bộ ba Đông Bắc $A,B,C$ của tập hợp và viết

$$B-A=(u,v),C-B=(p,q).$$

Khi đó $u,v,p,q$ đều là các số nguyên dương. Vì thế

$$A{C}^2-A{B}^2-B{C}^2=(u+p{)}^2+(v+q{)}^2-(u^2+v^2)-(p^2+q^2)=2(up+vq)\ge 4.$$

b) Vì không có đường thẳng qua hai điểm nào song song với một trục tọa độ nên các hoành độ đôi một khác nhau và các tung độ đôi một khác nhau. Vì tập hợp có 20 điểm nên sau khi sắp xếp các điểm theo hoành độ tăng dần, tập hợp bao gồm các điểm dạng

$$P_i=(i,{\pi }_i),1\le i\le 20,$$

trong đó $({\pi }_1,{\pi }_2,\dots ,{\pi }_{20})$ là một hoán vị của $(1,2,\dots ,20)$.

Ba điểm $P_i,P_j,P_k$ với $i<j<k$ tạo thành một bộ ba Đông Bắc khi và chỉ khi ${\pi }_i<{\pi }_j<{\pi }_k$.

Ta có kết quả sau về số Catalan:

Bổ đề: Số hoán vị $({\pi }_1,\dots ,{\pi }_n)$ của $(1,2,\dots ,n)$ sao cho không tồn tại ba chỉ số $i<j<k$ thoả mãn điều kiện ${\pi }_i<{\pi }_j<{\pi }_k$ bằng $\frac{1}{n+1}{C}_{2n}^n$.

Chứng minh bổ đề: Gọi $C_n$ là số lượng hoán vị như trên của tập hợp $(1,2,\dots ,n)$.

Trước hết, ta sẽ đưa bài toán về việc đếm các hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$. Ta gọi ${\pi }_i$ là một LIM nếu ${\pi }_i<{\pi }_j$ với mọi $j<i$.

Xét một hoán vị $\pi$ không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_j<{\pi }_k$. Ta có nhận xét rằng các phần tử không phải LIM phải xuất hiện theo thứ tự giảm dần.

Thật vậy, giả sử có hai vị trí $i<j$ sao cho ${\pi }_i,{\pi }_j$ đều không phải LIM và ${\pi }_i<{\pi }_j$. Vì ${\pi }_i$ không phải LIM nên tồn tại $h<i$ sao cho ${\pi }_h<{\pi }_i$. Khi đó $h<i<j$ và ${\pi }_h<{\pi }_i<{\pi }_j$, vô lý.

Do đó, một hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_j<{\pi }_k$ được xác định duy nhất nếu biết vị trí và giá trị của các LIM: các số còn lại chỉ cần được điền vào các vị trí còn trống theo thứ tự giảm dần.

Bây giờ, vẫn giữ nguyên vị trí và giá trị của các LIM. Ta đi từ trái sang phải qua các vị trí còn trống; tại mỗi vị trí, nếu $m$ là LIM gần nhất ở bên trái, ta điền số nhỏ nhất chưa được sử dụng và lớn hơn $m$.

Hoán vị thu được không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$. Thật vậy, giả sử tồn tại $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$. Gọi $m$ là LIM gần nhất đứng trước vị trí $j$. Khi đó $m\le {\pi }_i<{\pi }_k<{\pi }_j$. Nhưng tại thời điểm điền vào vị trí $j$, số ${\pi }_k$ vẫn chưa được sử dụng và lớn hơn $m$, trái với cách chọn ${\pi }_j$ là số nhỏ nhất chưa được sử dụng và lớn hơn $m$.

Ngược lại, từ một hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$, ta giữ nguyên các LIM và điền các số còn lại theo thứ tự giảm dần. Theo nhận xét trên, ta thu được duy nhất một hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_j<{\pi }_k$.

Như vậy, tồn tại một song ánh giữa hai tập hoán vị trên. Do đó, ta chỉ cần đếm số hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$, và vẫn ký hiệu số lượng này là $C_n$.

Xét một hoán vị $\pi =({\pi }_1,{\pi }_2,\dots ,{\pi }_n)$ thỏa mãn điều kiện trên. Giả sử ${\pi }_k=n$. Khi đó, hoán vị được chia thành hai phần:

- Phần bên trái $L$ gồm $k-1$ phần tử đứng trước $n$: $({\pi }_1,{\pi }_2,\dots ,{\pi }_{k-1})$.
- Phần bên phải $R$ gồm $n-k$ phần tử đứng sau $n$: $({\pi }_{k+1},\dots ,{\pi }_n)$.

Từ đây ta suy ra được:

- Mọi phần tử nằm ở bên trái $n$ trong $L$ bắt buộc phải lớn hơn mọi phần tử nằm ở bên phải $n$ trong $R$. Thật vậy, nếu tồn tại $l\in L$ và $r\in R$ sao cho $l<r$, thì do $r<n$, ta có ba phần tử $l,n,r$ xuất hiện theo thứ tự từ trái sang phải và thỏa mãn $l<r<n$. Khi đó tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$, vô lý. Do đó, tập hợp các giá trị của $L$ là $\{n-k+1,\dots ,n-1\}$, còn tập hợp các giá trị của $R$ là $\{1,\dots ,n-k\}$.
- Cả hai phần $L$ và $R$ cũng không tồn tại ba chỉ số $i<j<k$ sao cho phần tử thứ $i$ nhỏ hơn phần tử thứ $k$ và phần tử thứ $k$ nhỏ hơn phần tử thứ $j$.

Để ý số cách chọn phần bên trái $L$ có độ dài $k-1$ là $C_{k-1}$ và số cách chọn phần bên phải $R$ có độ dài $n-k$ là $C_{n-k}$. Suy ra $C_n={\sum }_{k=1}^n{C}_{k-1}{C}_{n-k}={\sum }_{i=0}^{n-1}{C}_i{C}_{n-1-i}$, và vì $C_0=1$ nên đây là dãy Catalan hay $C_n=\frac{1}{n+1}{C}_{2n}^n$, bổ đề được chứng minh.

Do đó, trong $20!$ hoán vị của $(1,2,\dots ,20)$, có đúng $\frac{1}{21}{C}_{40}^{20}$ hoán vị không tạo ra bộ ba Đông Bắc.

Vậy số tập hợp Lam Sơn là $20!-\frac{1}{21}{C}_{40}^{20}$.