Đếm số hoán vị bằng dãy truy hồi

Mỗi ngày một bài toán 03

Bài toán. Cho số nguyên dương $n>2$. Xét $(a_1, a_2,\ldots, a_n)$ là một hoán vị của tập hợp $X=\{1,2,\ldots, n\}$  sao cho $2(a_1+a_2+\cdots+a_k)$ chia hết cho $k$ với mọi $k=1,2,\ldots, n$.

a) Chứng minh rằng $a_n\in \{1, n\}$.

b) Tìm số hoán vị trên của $X$.

Giải.

Theo giả thiết ta có 

$$(n-1) \;|\; 2(a_1+a_2+\cdots + a_{n-1}).$$

Vì $(a_1,a_2,\ldots, a_n)$ là một hoán vị của $(1,2,\ldots, n)$ nên

$$a_1 + a_2 + \cdots + a_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$

Do đó

$$(n-1) \;|\; n(n+1) - 2a_n = n(n-1) + 2(n - a_n).$$

Suy ra 

$$(n-1) \;|\; 2(n-a_n).$$  

Mà $0\leq 2(n-a_n)\leq 2(n-1)$ nên $2(n-a_n) \in \{0,n-1,2(n-1)\}$, do đó 

$$a_n \in \left\{1,n, \frac{n+1}{2} \right\}.$$

Ta chứng minh $a_n \neq \frac{n+1}{2}$. Thật vậy nếu $n$ chẵn thì ta có điều phải chứng minh. 

Trong trường hợp $n$ lẻ, ta có

$$a_1 + a_2 + \cdots + a_{n-1} = \frac {n(n+1)}{2} - \frac{n+1}{2} = \dfrac{(n-1)(n+1)}{2}.$$

Khi đó

$$(n-2) \;|\; 2(a_1 + \cdots + a_{n-2}) = (n-2)(n+1) + (n+1) - 2a_{n-1}.$$

Suy ra

$$(n-2) \; | \; (n+1) -  2a_{n-1}.$$

Mà $-(n-1) \leq n+1-2a_{n-1} \leq n-1$ nên $n+1-2a_{n-1} \in \{ -n + 2, 0, n-2\}$.

Từ đó $a_{n-1} \in \left \{ \frac{2n-1}{2}, \frac{n+1}{2}, \frac 3 2 \right \}$, một mâu thuẫn vì $a_{n-1}$ là một số nguyên và $a_{n-1} \neq a_n$.

Tóm lại $a_n \in \{1, n\}$.

b) Ta gọi hoán vị thỏa mãn yêu cầu bài toán là một hoán vị đẹp. Ký hiệu

• $S_n$ là tập hợp các hoán vị đẹp của tập $\{1,2,\ldots, n\}$;
• $A_n$ là tập hợp các hoán vị đẹp của tập $\{1,2,\ldots, n\}$ trong đó $a_n = n$;
• $B_n$ là tập hợp các hoán vị đẹp của tập $\{1,2,\ldots, n\}$ trong đó $a_n = 1$.

Theo ý a), $|S_n| = |A_n| + |B_n|$.

* Đếm $|A_n|$.

Ta thấy rằng một hoán vị đẹp $(a_1,a_2,\ldots, a_{n-1}, n) \in A_n$ khi và chỉ khi $(a_1,a_2,\ldots, a_{n-1}) \in S_{n-1}$. Do đó

$$|A_n| = |S_{n-1}|.$$

* Đếm $|B_n|$

Dễ thấy ánh xạ

$$f: B_n \rightarrow S_{n-1}$$

$$(a_1,\ldots, a_{n-1},1) \mapsto (a_1-1,\ldots, a_{n-1}-1)$$

là một song ánh. Theo đó

$$|B_n| = |S_{n-1}|.$$

Do đó

$$|S_n| = 2|S_{n-1}|, \forall n>3.$$

Vậy $|S_n| = |S_3|.2^{n-3} = 3.2^{n-2},\forall n\geq 3.$

Ghi chú: Thay $n=2023$ ta được một câu hỏi trong đề thi Olympic 30/4 lớp 11 năm 2023.