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

[Nguyen Bao Khanh]

Những số $1;2;...;2003$ được viết theo thứ tự này. Một phép biến đổi là chọn 4 số bất kì trong chúng và đặt lại các vị trí chúng đã chiếm nhưng theo thứ tự ngược lại. Có thể bằng phép biến đổi này để thực hiên được việc sắp xếp thành $2003;2002;...;1$

[nguyenhuybao06]

Đặt theo thứ tự ngược lại là thế nào bạn nhỉ? Có phải nếu chọn ra từ trái sang phải lần lượt là $a_{m}, a_{n}, a_{p}, a_{q}$ (với $1\leq m<n<p<q\leq2003$) thì sẽ được xếp lại thành $a_{q}, a_{p}, a_{n}, a_{m}$ không nhỉ? (Ý mình là số thứ nhất được chọn theo chiều từ trái sang phải sẽ được đổi chỗ với số thứ tư được chọn cùng cách, và số thứ 2 được chọn theo cách đó sẽ đổi chỗ với số thứ 3.) 

[Nguyen Bao Khanh]

Đặt theo thứ tự ngược lại là thế nào bạn nhỉ? Có phải nếu chọn ra từ trái sang phải lần lượt là $a_{m}, a_{n}, a_{p}, a_{q}$ (với $1\leq m<n<p<q\leq2003$) thì sẽ được xếp lại thành $a_{q}, a_{p}, a_{n}, a_{m}$ không nhỉ? (Ý mình là số thứ nhất được chọn theo chiều từ trái sang phải sẽ được đổi chỗ với số thứ tư được chọn cùng cách, và số thứ 2 được chọn theo cách đó sẽ đổi chỗ với số thứ 3.) 

 Đúng rồi ạ

[perfectstrong]

Những số $1;2;...;2003$ được viết theo thứ tự này. Một phép biến đổi là chọn 4 số bất kì trong chúng và đặt lại các vị trí chúng đã chiếm nhưng theo thứ tự ngược lại. Có thể bằng phép biến đổi này để thực hiên được việc sắp xếp thành $2003;2002;...;1$

Thường những bài như này chúng ta sẽ dựa trên "nghịch thế": một cặp chỉ số $(i,j)$ của dãy $\sigma$ được gọi là nghịch thế nếu và chỉ nếu $i < j$ và $\sigma(i) > \sigma(j)$, hoặc $i > j$ và $\sigma(i) < \sigma(j)$ ($\sigma(a)$ là số tại chỉ số $a$ trong dãy $\sigma$).

Để tiện lợi, ta ký hiệu $I_{\sigma}(a,b)$ là hàm nghịch thế cho hai chỉ số $a,b$ của dãy $\sigma$. $I_{\sigma}(a,b)=1$ nếu $(a,b)$ là cặp chỉ số nghịch thế, còn không thì $I_{\sigma}(a,b)=0$.

Nói nôm na, "nghịch thế" là khi có một số lớn hơn đứng trước một số nhỏ hơn. Ví dụ trong dãy $2,1,3,4$ thì cặp chỉ số $(1,3)$ là nghịch thế, vì số $2$ ở vị trí 1, còn số $1$ lại ở sau (vị trí $3$).

Ta có một số tính chất như sau:

Mệnh đề

$I_{\sigma}(a,b) = 1-I_{\sigma}(b,a)$

Mệnh đề

Nếu $\sigma'$ là $\sigma$ sau khi tráo hai số ở vị trí $a,b$, thì $I_{\sigma'}(a,b)=1-I_{\sigma}(a,b)$

Mệnh đề

Nếu $\sigma'$ là $\sigma$ sau khi dịch chuyển vị trí $a < b$ tới một vị trí $a' > b$, hoặc ngược lại, thì $I_{\sigma'}(a',b)=1-I_{\sigma}(a,b)$

Mệnh đề

Nếu $\sigma'$ là $\sigma$ sau khi tráo đổi hai vị trí $a,b$ thì:

- Với mọi chỉ số $c$ nằm giữa $a,b$, ta có $I_{\sigma'}(c,a)+I_{\sigma'}(c,b)=2-I_{\sigma}(c,a)-I_{\sigma}(c,b)$

- Với mọi chỉ số $c$ nằm ngoài (nhỏ hơn/lớn hơn) $a,b$, ta có $I_{\sigma'}(c,a)+I_{\sigma'}(c,b)=I_{\sigma}(c,a)+I_{\sigma}(c,b)$

Theorem hàm ý rằng số bộ nghịch thế sẽ không đổi, hoặc tăng $2$, hoặc giảm $2$. Nói khác đi, tính chẵn lẻ của số bộ nghịch thế không đổi. Do đó, ta phát biểu lại Theorem:

Mệnh đề

Nếu $\sigma'$ là $\sigma$ sau khi tráo đổi hai vị trí $a,b$ thì với mọi chỉ số $c \ne a,b$, ta có $I_{\sigma'}(c,a)+I_{\sigma'}(c,b)\equiv I_{\sigma}(c,a) + I_{\sigma}(c,b) (\text{mod }2)$

Đây là tính chất thông dụng nhất của cách tiếp cận này.

 

Quay lại với bàn toán: ta để ý rằng dãy đã cho ban đầu có số bộ nghịch thế bằng $0$, trong khi dãy đích lại chỉ toàn các bộ nghịch thế. Tổng số bộ nghịch thế trong dãy đích là $2005003(=2002 + 2001 + \ldots + 1)$ bộ, là một số lẻ.

Do đó, có khả năng rằng ta không thể đi đến dãy đích. Ta phải nghiên cứu xem, phép hoán đổi 4 số đã cho sẽ tác động thế nào đến số bộ nghịch thế.

 

Ta xét một dãy $\sigma$ có được sau một số bước hoán đổi, và ta muốn áp dụng phép hoán đổi lên 4 chỉ số $i_1, i_2, i_3, i_4$ tăng dần.

Minh họa dãy $\sigma$ :

\begin{equation}\label{eq_swap_before} --- \sigma(i_1) --- \sigma(i_2) --- \sigma(i_3) --- \sigma(i_4) --- \end{equation}

Minh họa dãy $\sigma'$ thu được sau khi áp dụng phép hoán vị $(i_1,i_2,i_3,i_4)$ lên $\sigma$

\begin{equation}\label{eq_swap_after} --- \sigma(i_4) --- \sigma(i_3) --- \sigma(i_2) --- \sigma(i_1) --- \end{equation}

Dễ thấy những bộ nghịch thế $(a,b)$ với $a,b \ne i_1,i_2,i_3,i_4$ sẽ không đổi. Ta chỉ cần quan tâm những bộ nghịch thế có liên quan tới các chỉ số $i_1,i_2,i_3,i_4$.

TH1: Xét một cặp chỉ số $(a, i_x)$ với $a\ne i_1,i_2,i_3,i_4$ và $x\in\{1,2,3,4\}$.

TH1.1: Nếu $a < i_1$ hoặc $a > i_4$ thì các bộ nghịch thế sẵn có sẽ không đổi theo Theorem:

\begin{equation}\label{eq_sum_4_out} I_{\sigma'}(a,i_1)+I_{\sigma'}(a,i_2) + I_{\sigma'}(a,i_3) + I_{\sigma'}(a,i_4) = I_{\sigma}(a,i_1) + I_{\sigma}(a,i_2) + I_{\sigma}(a,i_3) + I_{\sigma}(a,i_4) \end{equation}

TH1.2: Nếu $a$ nằm giữa $i_1$ và $i_2$, áp dụng Theorem, ta có:

\begin{align}\nonumber I_{\sigma'}(a,i_1)+I_{\sigma'}(a,i_2) + I_{\sigma'}(a,i_3) + I_{\sigma'}(a,i_4) & = 1 - I_{\sigma}(a,i_1) + I_{\sigma}(a,i_2) + I_{\sigma}(a,i_3) + 1 - I_{\sigma}(a,i_4) \\ \label{eq_sum_4_between_1_2} & \equiv  I_{\sigma}(a,i_1) + I_{\sigma}(a,i_2) + I_{\sigma}(a,i_3) + I_{\sigma}(a,i_4) (\text{mod }2)\end{align}

Vì sau hoán vị, theo minh họa \eqref{eq_swap_after}, $\sigma(i_2), \sigma(i_3)$ vẫn ở sau $\sigma(a)$, còn $\sigma(i_4)$ chuyển ra trước $\sigma(a)$, còn $\sigma(i_1)$ chuyển ra sau $\sigma(a)$.

TH1.3: Nếu $a$ nằm giữa $i_2$ và $i_3$, biện luận tương tự như trên, ta có:

\begin{align}\nonumber I_{\sigma'}(a,i_1)+I_{\sigma'}(a,i_2) + I_{\sigma'}(a,i_3) + I_{\sigma'}(a,i_4) & = 1 - I_{\sigma}(a,i_1) + 1 - I_{\sigma}(a,i_2) + 1 - I_{\sigma}(a,i_3) + 1 - I_{\sigma}(a,i_4) \\ \label{eq_sum_4_between_2_3} & \equiv  I_{\sigma}(a,i_1) + I_{\sigma}(a,i_2) + I_{\sigma}(a,i_3) + I_{\sigma}(a,i_4) (\text{mod }2) \end{align}

TH1.4: Nếu $a$ nằm giữa $i_3$ và $i_4$, biện luận tương tự như trên, ta có:

\begin{align}\nonumber I_{\sigma'}(a,i_1)+I_{\sigma'}(a,i_2) + I_{\sigma'}(a,i_3) + I_{\sigma'}(a,i_4) & = 1 - I_{\sigma}(a,i_1) + I_{\sigma}(a,i_2) + I_{\sigma}(a,i_3) + 1 - I_{\sigma}(a,i_4) \\ \label{eq_sum_4_between_3_4} & \equiv  I_{\sigma}(a,i_1) + I_{\sigma}(a,i_2) + I_{\sigma}(a,i_3) + I_{\sigma}(a,i_4) (\text{mod }2) \end{align}

TH2: Xét một cặp chỉ số $(i_x, i_y)$ với $x,y \in \{1,2,3,4\}$ và $x < y$.

Ta thấy ngay phép hoán vị sẽ đảo ngược sự nghịch thế: toàn bộ các cặp nghịch thế thành không nghịch thế, và cặp không nghịch thế thành nghịch thế. Áp dụng Theorem:

\begin{align}\nonumber \sum\limits_{1\le x < y \le 4} I_{\sigma'}(i_x, i_y)& = \sum\limits_{1\le x < y \le 4} (1 - I_{\sigma}(i_x, i_y)) = 6 - \sum\limits_{1\le x < y \le 4} I_{\sigma}(i_x, i_y) \\ \label{eq_sum_4} & \equiv  \sum\limits_{1\le x < y \le 4} I_{\sigma}(i_x, i_y) (\text{mod }2) \end{align}

 

Như vậy, ta đã chứng minh được rằng, phép hoán vị 4 số đã cho sẽ không thay đổi tính chẵn lẻ của số nghịch thế của dãy. Như vậy, dãy ban đầu $(1,2,\ldots,2003)$ có một số chẵn bộ nghịch thế $(=0)$ sẽ không thể đi đến dãy đích $(2003,2002,\ldots,1)$ vì dãy đích có một số lẻ bộ nghịch thế $(=2002 + 2001 + \ldots + 1=2005003)$.

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 16-05-2024 - 22:15

[Hoang Long Le]

Thường những bài như này chúng ta sẽ dựa trên "nghịch thế": một cặp chỉ số $(i,j)$ của dãy $\sigma$ được gọi là nghịch thế nếu và chỉ nếu $i < j$ và $\sigma(i) > \sigma(j)$, hoặc $i > j$ và $\sigma(i) < \sigma(j)$ ($\sigma(a)$ là số tại chỉ số $a$ trong dãy $\sigma$).

 

Thực ra ta chỉ cần chứng minh việc thay đổi chỗ 2 số cho nhau sẽ làm thay đổi tính chẵn lẻ của số cặp nghịch thế (phép thế đơn vị có dấu $-1$). Từ đó suy ra tại mỗi bước, tính chẵn lẻ là không đổi. Quan sát này khiến cho việc đổi $(1,4)$ và $(2,3)$ có thể thay bằng việc chọn ra 2 cặp bất kì rời nhau và hoán vị chúng đôi một.