Administrator Tham gia ngày: Jun 2012 Bài gởi: 157 Thanks: 2 Thanked 84 Times in 53 Posts | Trích: Nguyên văn bởi kenzie 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: - $x_{i}\in{1;2;...;n}$ với mọi chỉ số $1\leq i\leq d$.
- $x_{i}\neq x_{i+1}$ với mọi chỉ số $1\leq i\leq d-1$.
- 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 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 - Nếu $|S_n(d)|=0$ thì $|S_n(d+1)|=0$,
- Nếu $|S_n(d)|>0$ với $d>1$ thì $|S_n(d-1)|>0$.
- 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. [RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] |