Xác định số các hoán vị $\left \{a_{1}, a_{2}, ..., a_{2017} \right \}$ của tập $\left \{ 1, 2, ..., 2017 \right \}$ thỏa mãn tính chất: $2(a_{1}+a_{2}+...+a_{k})$ chia hết cho $k,$ với mọi $k=1, 2, 3, ..., 2017.$
Xác định số các hoán vị $\left \{a_{1}, a_{2}, ..., a_{2017} \right \}$ bằng phương pháp song ánh.
#3
Đã gửi 30-06-2017 - 10:04
Đặt $n=2017$. Gọi $S_n$ là số hoán vị thỏa mãn đề. Ta sẽ chứng minh với $n\geq 3$, $S_n=3.2^{n-2}$.
Với $n=3$, dễ thử.
Giả sử $n-1$ đúng. Xét một hoán vị với $n\geq 4$ thỏa mãn. Ta có:
$n-1|2\left ( a_1+a_2+...+a_{n-1} \right )=2(1+2+...+n-a_n)=n(n+1)-2a_n=(n-1)(n+2)-2(a_n-1)\Rightarrow n-1|2 (a_n-1)$
$n-2|2(a_1+a_2+...+a_{n-2})=(n-2)(n+3)+2(3-a_{n-1}-a_n)\Rightarrow n-2|2(a_{n-1}+a_n-3)$
TH1:$n-1$ lẻ suy ra $a_n=1,n$
TH2:$n-1$ chẵn, giả sử $a_n=\frac{n+1}{2}$. Ta có $n-2$ lẻ và $0<\frac{n-3}{2}\leq a_{n-1}+a_n-3\leq \frac{3n-5}{2}<2(n-2)$ suy ra $a_{n-1}+a_n-3=n-2\Rightarrow a_{n-1}=a_n=\frac{n+1}{2}$(vô lý). Vậy $a_n=1,n$
THa:$a_n=n$. Ta thấy các số $a_1,...,a_{n-1}$ là hoán vị của $1,...,n-1$. Theo giả thiết quy nạp, số cách chọn là $S_{n-1}$
THb:$a_n=1$. Ta thấy các số $(a_1-1),...,(a_{n-1}-1$ là hoán vị của $1,...,n-1$. Theo giả thiết quy nạp, số cách chọn là $S_{n-1}$
Vậy $S_n=2S_{n-1}=3.2^{n-2}$, bài toán được chứng minh. Vậy $S_{2017}=3.2^{2015}$
Bài viết đã được chỉnh sửa nội dung bởi redfox: 01-07-2017 - 16:19
- Element hero Neos và Zz Isaac Newton Zz thích
For the love of Canidae
#4
Đã gửi 03-07-2017 - 15:37
Đặt $n=2017$. Gọi $S_n$ là số hoán vị thỏa mãn đề. Ta sẽ chứng minh với $n\geq 3$, $S_n=3.2^{n-2}$.
Với $n=3$, dễ thử.
Giả sử $n-1$ đúng. Xét một hoán vị với $n\geq 4$ thỏa mãn. Ta có:
$n-1|2\left ( a_1+a_2+...+a_{n-1} \right )=2(1+2+...+n-a_n)=n(n+1)-2a_n=(n-1)(n+2)-2(a_n-1)\Rightarrow n-1|2 (a_n-1)$
$n-2|2(a_1+a_2+...+a_{n-2})=(n-2)(n+3)+2(3-a_{n-1}-a_n)\Rightarrow n-2|2(a_{n-1}+a_n-3)$
TH1:$n-1$ lẻ suy ra $a_n=1,n$
TH2:$n-1$ chẵn, giả sử $a_n=\frac{n+1}{2}$. Ta có $n-2$ lẻ và $0<\frac{n-3}{2}\leq a_{n-1}+a_n-3\leq \frac{3n-5}{2}<2(n-2)$ suy ra $a_{n-1}+a_n-3=n-2\Rightarrow a_{n-1}=a_n=\frac{n+1}{2}$(vô lý). Vậy $a_n=1,n$
THa:$a_n=n$. Ta thấy các số $a_1,...,a_{n-1}$ là hoán vị của $1,...,n-1$. Theo giả thiết quy nạp, số cách chọn là $S_{n-1}$
THb:$a_n=1$. Ta thấy các số $(a_1-1),...,(a_{n-1}-1$ là hoán vị của $1,...,n-1$. Theo giả thiết quy nạp, số cách chọn là $S_{n-1}$
Vậy $S_n=2S_{n-1}=3.2^{n-2}$, bài toán được chứng minh. Vậy $S_{2017}=3.2^{2015}$
Cách làm của bạn dùng quy nạp khá là hay đó
Cách làm của mình...
Đặt $n=2017.$ Gọi $S_{n}$ là số hoán vị $\left \{ a_{1}, a_{2}, ..., a_{n} \right \}$ của tập $\left \{ 1, 2, ..., n \right \}$ thỏa mãn tính chất: $2(a_{1}+a_{2}+...+a_{k})$ chia hết cho $k,$ với mọi $k=\overline{1, n}$ $(*)$
Dễ dàng thấy: $\left | S_{1} \right |=1; \left | S_{2} \right |=2; \left | S_{3} \right |=6.$
Trước hết, ta sẽ chứng minh rằng, mỗi hoán vị thỏa $(*)$ phải có $a_{n}=1$ hoặc $a_{n}=n.$
Thật vậy, với mỗi hoán vị $\left \{ a_{1}, a_{2}, ..., a_{n} \right \}$ thỏa $(*)$ ta có:
$2(a_{1}+a_{2}+...+a_{n-1})=2(a_{1}+a_{2}+...+a_{n})-2a_{n}=2(1+2+...+n)-2a_{n}=n(n+1)-2a_{n}=(n+2)(n-1)+(2-2a_{n}).$
Mà $2(a_{1}+a_{2}+...+a_{n-1})$ chia hết cho $(n-1)$ nên $(2-2a_{n})$ chia hết cho $(n-1).$
Suy ra: $a_{n}=1$ hoặc $a_{n}=n$ hoặc $a_{n}=\frac{n+1}{2}$ ( nếu $n$ là số lẻ ).
Nếu $a_{n}=\frac{n+1}{2}$ ( nếu $n$ là số lẻ ), ta có:
$2(a_{1}+a_{2}+...+a_{n-2})=2(a_{1}+a_{2}+...+a_{n})-2a_{n-1}-2a_{n}=2(1+2+...+n)-2a_{n-1}-(n+1)=n(n+1)-(n+1)-2a_{n-1}=(n-2)(n+2)+(3-2a_{n-1}).$
Mà $2(a_{1}+a_{2}+...+a_{n-2})$ chia hết cho $(n-2)$ nên $(3-2a_{n-1})$ chia hết cho $(n-2).$
Do $2a_{n-1}-3\leq 2n-3< 3n-6,$ khi $n\geq 3$ nên $2a_{n-1}-3=n-2$ hoặc $2a_{n-1}-3=2n-4$ ( vô lý vì $2a_{n-1}-3$ là số lẻ ).
Suy ra: $a_{n-1}=\frac{n+1}{2}=a_{n}$ ( mâu thuẫn ).
Đặt $S_{n_{1}}=\left \{ (a_{1}, a_{2}, ..., a_{n})\left.\begin{matrix} \end{matrix}\right|(a_{1}, a_{2},..., a_{n})\in S_{n}, a_{n}=n \right \}.$
$S_{n_{2}}=\left \{ (a_{1}, a_{2}, ..., a_{n})\left.\begin{matrix} \end{matrix}\right|(a_{1}, a_{2},..., a_{n})\in S_{n}, a_{n}=1 \right \}.$
Nếu $a_{n}=n$ thì $(a_{1}, a_{2}, ..., a_{n-1})$ cũng là một hoán vị của $(1, 2, ..., n-1)$ thỏa mãn tính chất $(*).$
Suy ra ánh xạ $f$ sau đây là song ánh.
$f:S_{n_{1}}\rightarrow S_{n-1}$
$(a_{1}, a_{2}, ..., a_{n-1}, n) \mapsto (a_{1}, a_{2}, ..., a_{n-1}).$
Suy ra: $\left | S_{n_{1}} \right |=\left | S_{n-1} \right |$
Nếu $a_{n}=1$ xét $(a_{1}-1, a_{2}-1, ..., a_{n-1}-1)$ là một hoán vị của $(1, 2, ..., n-1).$
Ta có: $2\left [ (a_{1}-1)+(a_{2}-1)+...+(a_{k}-1) \right ]=2(a_{1}+a_{2}+...+a_{k})-2k$ chia hết cho $k$ khi và chỉ khi $2(a_{1}+a_{2}+...+a_{k})$ chia hết cho $k.$
Suy ra ánh xạ $g$ sau đây là một song ánh.
$g: S_{n_{2}}\rightarrow S_{n-1}$
$(a_{1}, a_{2}, ..., a_{n-1}, 1) \mapsto (b_{1}, b_{2}, ..., b_{n-1})=(a_{1}-1, a_{2}-1, ..., a_{n-1}-1).$
Suy ra: $\left | S_{n_{2}} \right |=\left | S_{n-1} \right |.$
Vậy: $\left | S_{n} \right |=\left | S_{n_{1}} \right |+\left | S_{n_{2}} \right |=2\left | S_{n-1} \right |=3.2^{n-2}.$
Vậy: $S_{2017}=3.2^{2015}.$
- redfox và NHoang1608 thích
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh