Đến nội dung

Hình ảnh

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.

- - - - -

  • Please log in to reply
Chủ đề này có 3 trả lời

#1
Zz Isaac Newton Zz

Zz Isaac Newton Zz

    Sĩ quan

  • Điều hành viên OLYMPIC
  • 392 Bài viết

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.$



#2
Drago

Drago

    Sĩ quan

  • Thành viên
  • 462 Bài viết

Đọc cái đề này chẳng có định hướng gì về cách giải :((


  • JUV yêu thích

$\mathbb{VTL}$


#3
redfox

redfox

    Trung sĩ

  • Thành viên
  • 100 Bài viết

Đặ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


#4
Zz Isaac Newton Zz

Zz Isaac Newton Zz

    Sĩ quan

  • Điều hành viên OLYMPIC
  • 392 Bài viết

Đặ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 đó  :D 

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}.$






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh