Bài tổ hợp VMO 2018
 

Cho các số nguyên dương $n$ và $d$. Xét tập hợp $S_{n}(d)$ gồm tất cả các bộ số có thứ tự $(x_1;...;x_d)$ thỏa mãn điều kiện sau:

1. $x_{i}\in{1;2;...;n}$ với mọi chỉ số $1\leq i\leq d$.
2. $x_{i}\neq x_{i+1}$ với mọi chỉ số $1\leq i\leq d-1$.
3. Không tồn tại các chỉ số $1\leq i< j< k< l\leq d$ sao cho $x_i=x_k$ và $x_j=x_l$.

a)Tính số phần tử của tập hợp $S_{3}(5)$.

b)Chứng minh rằng tập hợp $S_{n}(d)$ khác rỗng khi và chỉ khi $d\leq 2n-1$.

Câu b: Ta có các nhận xét sau

1. Nếu $|S_n(d)|=0$ thì $|S_n(d+1)|=0$,
2. Nếu $|S_n(d)|>0$ với $d>1$ thì $|S_n(d-1)|>0$.
3. Bộ $(1,2,...,n-1,n,n-1,...,2,1)$ thuộc $S_n(2n-1)$.

Từ các nhận xét trên ta dễ dàng suy ra $S_n(d)$ khác rỗng với mọi $1\leq d\leq 2n-1$. Bây giờ ta chỉ cần chứng minh $S_n(d)=\emptyset$ với mọi $d\geq 2n$ bằng quy nạp.
Rỏ ràng $S_1(d)=\emptyset,\forall d\geq 2.$ Giả sử $(x_1,x_2,...,x_d)\in S_n(2n)$(ở đây $d=2n$). Ta xét các trường hợp sau

• Nếu có một số nào đó từ $1$ đến $n$ không xuất hiện trong dãy $(x_1,x_2,...,x_d)$. Khi đó $(x_1,x_2,...,x_d)\in S_{n-1}(2n)$. Rỏ ràng điều này mâu thuẩn với giả thiết quy nạp.
• Nếu có một số nào đó từ $1$ đến $n$ chỉ xuất hiện trong dãy $(x_1,x_2,...,x_d)$ đúng một lần. Giả sử số đó là $a$.
  • Nếu $x_1=a$ hoặc $x_d=a$, khi đó xóa số đó khỏi dãy thì ta được $(x_2,x_3,...,x_d)\in S_{n-1}(2n-1)$ hoặc $(x_1,x_2,...,x_{d-1})\in S_{n-1}(2n-1)$. Rỏ ràng điều này cũng mâu thuẩn với giả thiết quy nạp.
  • Giả sử tồn tại $d>k>1$ sao cho $x_k=a$. Xóa $x_k$ ra khỏi dãy. Nếu $x_{k-1}\neq x_{k+1}$ thì ta có dãy $(x_1,x_2,...,x_{k-1},x_{k+1},...,x_d)\in S_{n-1}(2n-1)$ và điều này cũng trái với giả thiết quy nạp. Nếu $x_{k-1}=x_{k+1}$ thì xóa luôn số $x_{k-1}$ ra khỏi dãy, khi đó dãy còn lại thuộc $S_{n-1}(2n-2)$ và điều này cũng trái với giả thiết quy nạp.
• Nếu mỗi số từ $1$ đến $n$ xuất hiện trong dãy $(x_1,x_2,...,x_d)$ đúng hai lần. Không giảm tổng quát giả sử $x_1=n$ và $x_k=n$ với $1<k\leq 2n$. Kết hợp với giả thiết suy ra trong dãy $(x_2,x_3,...,x_{k-1})$ mỗi số lặp lại đúng hai lần và $k$ là số chẵn, từ đây ta có $(x_2,x_3,...,x_{k-1})\in S_m(2m)$ với $m=\dfrac{k-2}{2}$. Rỏ ràng điều này trái với giả thiết quy nạp.

Vậy ta có $S_n(d)=\emptyset, \forall d\geq 2n$. Hay bài toán hoàn toàn được chứng minh.