Chủ đề này có 2 trả lời

[manhhung2013]

Một hoán vị $x_{1},x_{2},...,x_{n}$ của tập hợp M={1,2,...,2n},(n là số nguyên dương) được gọi là có tính chất P nếu $\left | x_{i}-x_{i+1} \right |=n$, với ít nhất một giá trị $i\in \left \{ 1,2,..,2n-1 \right \}$. Chứng minh rằng với mỗi số n, số hoán vị có tính chất P lớn hơn số hoán vị không có tính chất P(hoán vị đề cập trong bài là hoán vị không lặp.

[HoaiBao]

Trong trường hợp $n=1,2$ thấy có vẻ nó ko thỏa bài nhỉ (còn hơi lúng túng chỗ này).

 

Gọi $A_i$ với $i =\overline{1,n}$ là tập hợp các hoán vị thõa mãn tính chất: có cặp $i$ và $n+i$ đứng cạnh nhau trong hoán vị đó.

Dễ thấy trong một hoán vị thì số tính chất thõa mãn trên không quá $\left [  \frac{n}{2} \right ]$. Nên theo nguyên lý bù trừ có số tính chất P :

$\left |\bigcap_{i=1}^{n} A_i \right | = \sum_{I=\left \{i_1,i_2,...,i_k \right \} \\ I \subset \left \{1,2,...,n \right \}  } (-1)^{|I|+1} \left |\bigcup_{j=1}^{k} A_{i_{j}} \right |$ . Dễ dàng tính được $\left |\bigcup_{j=1}^{k} A_{i_{j}} \right | = 2^k(n-k)!\binom{2n-2k}{n-2k} $ kết hợp với tính đối xứng của các tính chất. Suy ra $\left |\bigcap_{i=1}^{n} A_i \right | = \sum_{k=1}^{\left [  \frac{n}{2} \right ]} (-1)^{k+1} 2^k(n-k)!\binom{n}{k}\binom{2n-2k}{n-2k} $

Từ đây ta sử dụng quy nạp để chứng minh nó lớn hơn $\frac{2n!}{2.n!}$. Suy ra điều phải chứng minh với $n>2$.

 

Lời giải còn hơi mơ hồ . Ai có cách khác ko

[redfox]

Trong trường hợp $n=1,2$ thấy có vẻ nó ko thỏa bài nhỉ (còn hơi lúng túng chỗ này).

 

Gọi $A_i$ với $i =\overline{1,n}$ là tập hợp các hoán vị thõa mãn tính chất: có cặp $i$ và $n+i$ đứng cạnh nhau trong hoán vị đó.

Dễ thấy trong một hoán vị thì số tính chất thõa mãn trên không quá $\left [  \frac{n}{2} \right ]$. Nên theo nguyên lý bù trừ có số tính chất P :

$\left |\bigcap_{i=1}^{n} A_i \right | = \sum_{I=\left \{i_1,i_2,...,i_k \right \} \\ I \subset \left \{1,2,...,n \right \}  } (-1)^{|I|+1} \left |\bigcup_{j=1}^{k} A_{i_{j}} \right |$ . Dễ dàng tính được $\left |\bigcup_{j=1}^{k} A_{i_{j}} \right | = 2^k(n-k)!\binom{2n-2k}{n-2k} $ kết hợp với tính đối xứng của các tính chất. Suy ra $\left |\bigcap_{i=1}^{n} A_i \right | = \sum_{k=1}^{\left [  \frac{n}{2} \right ]} (-1)^{k+1} 2^k(n-k)!\binom{n}{k}\binom{2n-2k}{n-2k} $

Từ đây ta sử dụng quy nạp để chứng minh nó lớn hơn $\frac{2n!}{2.n!}$. Suy ra điều phải chứng minh với $n>2$.

 

Lời giải còn hơi mơ hồ . Ai có cách khác ko

Xét ánh xạ từ các hoán vị không có tính chất $P$ đến các hoán vị có tính chất $P$: $f\left ( x_1,x_2,...,x_n \right )=\left ( x_2,...,x_{k-1},x_1,x_k,...,x_{2n} \right )$ với $x_k$ thỏa $\left | x_1-x_k \right |=n$ (dễ thấy $\left | x_{k-1}-x_1 \right |\neq n$. Giả sử $f\left ( x_1,x_2,...,x_{2n} \right )= \left ( z_1,z_2,...,z_{2n} \right )$, xét chỉ số $i>1$ thỏa $\left | z_i-z_{i+1} \right |=n$ (có một chỉ số duy nhất), ta xác định được ngay bộ $\left ( x_1,x_2,...,x_n \right)$: $x_1=z_i,k=i+1,x_l=z_l\left ( l\geq k \right ),x_l=z_{l+1}\left ( l<k-1 \right )$, vậy đây là đơn ánh. Xét hoán vị $\left ( 1,n+1,... \right )$, ta thấy nó không là ảnh của hoán vị không có tính chất $P$. Vậy đây là đơn ánh, không phải là toàn ánh. Vậy số hoán vị có tính chất $P$ nhiều hơn.

(Q.E.D)

Bài viết đã được chỉnh sửa nội dung bởi redfox: 10-06-2017 - 14:57