Đến nội dung

Hình ảnh

Phương pháp TRUY HỒI $\to$ QUY NẠP

- - - - - Phương pháp đếm

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

#1
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Để giải quyết một bài toán tổ hợp nói chung ta phải sử dụng đến các phương pháp đếm. Phương pháp đếm có nhiều loại như: Phương pháp đếm từng phần, phương pháp gộp vào loại ra, hay cao cấp hơn là phương pháp dùng hàm sinh,...
Trong các phương pháp kể trên thì phương pháp dùng hàm sinh là một phương pháp khá đa năng, tuy nhiên nó đòi hỏi phải sử dụng đến một số kiến thức toán cao cấp nhất định. Trong bài viết này tôi sẽ giới thiệu cho các bạn một phương pháp đếm sơ cấp hơn và cũng khá hiệu quả: Phương pháp Truy hồi - Quy nạp.
Để hiểu thêm về phương pháp này ta sẽ tìm hiểu qua một số ví dụ quen thuộc sau đây:

Ví dụ 1: Có bao nhiêu cách chia $m$ cái kẹo cho $n$ đứa trẻ (có thể có đứa không có cái nào!)
Hay hiểu theo một cách khác là phương trình:
$m=k_1+k_2+...+k_n\;\;\;(1)$
Có bao nhiêu nghiệm nguyên không âm?

Lời giải:
Gọi $S(m,n)$ là số nghiệm của (1). Ta có:
$(1)\Leftrightarrow m-k_1=k_2+...+k_n\;\;\;(2)$
Như vậy, tương ứng với mỗi giá trị $k_1;\;(0\le k_1 \le m)$, ta có số nghiệm của (2) là $S(m-k_1,n-1)$
Do đó:
$S(m,n)=\sum\limits_{k=0}^m S(m-k,n-1)$ (Truy hồi)

- Với $n=1$, dễ thấy $S(m,1)=1$
- Với $n=2$, ta có: $S(m,2)=\sum\limits_{k=0}^m S(m-k,1)=\sum\limits_{k=0}^m 1 = m+1$
- Với $n=3$, ta có: $S(m,3)=\sum\limits_{k=0}^m S(m-k,2)=\sum\limits_{k=0}^m (m+1-k) = \dfrac{(m+2)(m+1)}{2}$

- Qua 3 trường hợp trên, ta dự đoán rằng: $\boxed{S(m,n)=C_{m+n-1}^{n-1}}\;\;\;(3)$

- Bây giờ ta sẽ chứng minh (3) bằng quy nạp theo $n$.
- Rõ ràng (3) đúng với $n=1,2,3$. Giả sử (3) đúng với $n$ ta sẽ chứng minh (3) cũng đúng với $(n+1)$. Ta có:
$S(m+1,n)=\sum\limits_{k=0}^m S(m-k,n)=\sum\limits_{k=0}^m C_{m-k+n-1}^{n-1}$ (giả thiết quy nạp)
$S(m+1,n)=\sum\limits_{k=0}^m C_{k+n-1}^{n-1}$ (đảo chiều biến k)
$S(m+1,n)=\sum\limits_{k=0}^m \left(C_{k+n}^n-C_{k-1+n}^n\right)=C_{m+n}^n$
Như vậy (3) đúng với $(n+1)$, theo nguyên lý quy nạp ta có điều phải chứng minh.
Vậy (3) là đáp số của bài toán.

Ví dụ 2: Các bạn có thể tham khảo ở đây
Cho tập $E=\{1,2,...,n\};\;\;\;(n\le 9)$ Mỗi tổ hợp gồm $i;\;\;(1\le i\le n)$ phần tử của $E$ là $\{a_1,...,a_i\}$ được sắp tăng dần $(a_1<...<a_i)$ để tạo thành số $\overline{a_1...a_i}$
Gọi $S(i,n)$ là tổng của tất cả các số đó. Tính $S(i,n)$

Lời giải:

Ta tính tổng $S(i,n)$ bằng cách phân ra các số có tận cùng là $k,\;\;(i\le k\le n)$
Nếu số có tận cùng là $k$ thì $i-1$ chữ số đầu sẽ có các chữ số nhỏ hơn $k$, nghĩa là nó là một tổ hợp $i-1$ phần tử của tập $\{1,...,k-1\}$ được sắp thứ tự tăng dần.
Có $C_{k-1}^{i-1}$ số như vậy.
Do đó ta có:
$\Rightarrow S(i,n)=\sum\limits_{k=i}^n\left(10S(i-1,k-1)+kC_{k-1}^{i-1}\right)$
$\Rightarrow S(i,n)=\sum\limits_{k=i}^n\left(10S(i-1,k-1)+iC_k^i\right)$
$\Rightarrow S(i,n)=iC_{n+1}^{i+1}+10\sum\limits_{k=i}^n S(i-1,k-1)$ (Truy hồi)

- Với $i=1$, ta có $S(1,n)=1+...+n=C_{n+1}^2$
- Với $i=2$, ta có $S(2,n)=2C_{n+1}^3+10\sum\limits_{k=2}^n S(1,k-1)=2C_{n+1}^3+10\sum\limits_{k=2}^n C_k^2$
$\Rightarrow S(2,n)=2C_{n+1}^3+10\sum\limits_{k=2}^n \left(C_{k+1}^3-C_k^3\right)=2C_{n+1}^3+10C_{n+1}^3=12C_{n+1}^3$

- Qua 2 trường hợp trên, ta dự đoán được: $\boxed{S(i,n)=\overline{1...i}.C_{n+1}^{i+1}}\;\;\;(*)$
- Ta sẽ chứng minh (*) bằng quy nạp theo $i$
Rõ ràng (*) đúng với $i=1,2$. Giả sử (*) đúng với $(i-1)$ ta sẽ chứng minh nó cũng đúng với $i$
Ta có:
$S(i,n)=iC_{n+1}^{i+1}+10\sum\limits_{k=i}^n S(i-1,k-1)$
$S(i,n)=iC_{n+1}^{i+1}+10.\overline{1...(i-1)}\sum\limits_{k=i}^n C_k^i$ (theo giả thiết quy nạp)
$S(i,n)=iC_{n+1}^{i+1}+\overline{1...(i-1)0}\sum\limits_{k=i}^n \left( C_{k+1}^{i+1}-C_{k+1}^i \right)$
$S(i,n)=iC_{n+1}^{i+1}+\overline{1...(i-1)0}.C_{n+1}^{i+1}$
$S(i,n)=\overline{1..i}.C_{n+1}^{i+1}$
Vậy (*) cũng đúng với $i$, theo nguyên lý quy nạp ta có điều phải chứng minh.

Kết luận: (*) là đáp số cần tìm!

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 01-11-2011 - 15:53


#2
alex_hoang

alex_hoang

    Thượng úy

  • Hiệp sỹ
  • 1152 Bài viết
Hi sinh buổi trưa để ủng hộ thầy

Bài 1:
Tìm số tập con của tập ${1,2,3...,n}$ sao cho trong mỗi tập con chứ ít nhất $2$ phần tử là $2$ số nguyên liên tiếp

Giải
Gọi $S_n$ là tập hợp các tập con không rỗng của tập ${1,2,3,4...,n}$ mà trong đó mỗi tập con không có $2$ phần tử nào là $2$ số nguyên liên tiếp. Chia các phần tử của $S_n$ thành $2$ nhóm
+)Nhóm không chứa $n$: số tập con như vậy là $\left| {{S_{n - 1}}} \right|$
+)Nhóm chứa ${n}$:${n} hoặc {a_1,a_2,...,a_n,n} (n \ge 1)$Như vậy rõ ràng rằng $a_i \ne n - 1(i=1,2,3,...,n)$ nên số các tập con như vậy là $\left| {{S_{n - 2}}} \right| + 1$
Do vậy $\left| {{S_n}} \right| = \left| {{S_{n - 1}}} \right| + \left| {{S_{n - 2}}} \right| + 1$
Với $\left| {{S_2}} \right| = 2,\left| {{S_3}} \right| = 4$
Như vậy dựa vào công thức truy hồi ta tính được
$\left| {{S_n}} \right| = \dfrac{1}{{\sqrt 5 }}({(\dfrac{{1 + \sqrt 5 }}{2})^{n + 2}} - {(\dfrac{{1 - \sqrt 5 }}{2})^{n + 2}}) - 1$
Mặt khác số tập con bất kì của tập ${1,2,3,4,...,n}$ là ${2^n} - 1$Vậy số tập con mà trong mỗi phần tử có $2$ số nguyênliêntiếp là
${2^n} - \dfrac{1}{{\sqrt 5 }}({(\dfrac{{1 + \sqrt 5 }}{2})^{n + 2}} - {(\dfrac{{1 - \sqrt 5 }}{2})^{n + 2}})$

Bài 2:
Cho số nguyên dương $n \ge 2$ Hãy tìm các hoán vị $(a_1,a_2,...,a_n)$ của $1,2,3,...,n$ sao cho tồn tại
(tồn tại cái gì alex_hoang mau vào bổ xung!)

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:15

alex_hoang


HẸN NGÀY TRỞ LẠI VMF THÂN MẾN

http://www.scribd.co...oi-Ban-Cung-The

#3
Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5534 Bài viết

Ví dụ 1: Có bao nhiêu cách chia $m$ cái kẹo cho $n$ đứa trẻ (có thể có đứa không có cái nào!)
Hay hiểu theo một cách khác là phương trình: $m=k_1+k_2+...+k_n\;\;\;(1)$ Có bao nhiêu nghiệm nguyên không âm?

Em xin thầy hxthanh cho em trình bày phương pháp dùng hàm sinh của bài toán trên.

Xét hàm sinh $$F\left( k \right) = \underbrace {\left( {1 + k + {k^2}...} \right)\left( {1 + k + {k^2}...} \right)...\left( {1 + k + {k^2}...} \right)}_{\text{n tích}}\,\,\,\,\,\,\,,\,\,\left| k \right| < 1$$

Mỗi số hạng trong khai triển $F\left( k \right)$ thành tổng có dạng ${k^{{k_1} + {k_2} + ... + {k_n}}},\,\,\,{k_i} \ge 0,\,\,\forall i$. Như vậy quan sát tổng từ trái qua phải mỗi khi ta gặp lũy thừa của $k$ bằng $m$ thì trong biểu thức khai triển thu gọn của $F\left( k \right)$ hệ số của ${k^m}$ tăng lên một đơn vị. Do đó hệ số của ${k^m}$ trong khai triển của $F\left( k \right)$ thành tổng chính là số nghiệm nguyên không âm của phương trình (1).

Vậy ta tìm hệ số của ${k^m}$ trong khai triển thành tổng của $F\left( k \right)$.

Ta có: $$F\left( k \right) = \dfrac{1}{{{{\left( {1 - k} \right)}^n}}} = {\left( {1 - k} \right)^{ - n}} = \sum\limits_{i \ge 0} {{{\left( { - 1} \right)}^i}C_{ - n}^i{k^i}} $$

Với $$C_{ - n}^i = \dfrac{{ - n\left( { - n - 1} \right)...\left( { - n - i + 1} \right)}}{{i!}} = \dfrac{{{{\left( { - 1} \right)}^i}n\left( {n + 1} \right)...\left( {n + i - 1} \right)}}{{i!}} = {\left( { - 1} \right)^i}C_{n + i - 1}^i$$

Vậy hệ số của ${k^m}$ trong khai triển thành tổng của $F\left( k \right)$ là $C_{n + m - 1}^m$ chính là số nghiệm nguyên không âm của phương trình (1).
-----------------------------------
hxthanh: - Phương pháp dùng hàm sinh rất hữu dụng, tuy nhiên ở bài này em đã sử dụng đến $2$ kiến thức vượt cấp phổ thông là:
- Khai triển chuỗi luỹ thừa
- Hệ số nhị thức Newton mở rộng.
-----------
- Thực ra bài này chỉ cần cách rất THPT như sau:
$m=k_1+k_2+...+k_n \Leftrightarrow (m+n)=(k_1+1)+(k_2+1)+...+(k_n+1)=i_1+i_2+...+i_n$
Như vậy ta đưa được bài toán về:
"Có bao nhiêu cách chia $m+n$ cái kẹo cho $n$ đứa trẻ sao cho đứa nào cũng có kẹo" (Bài toán chia kẹo - Eurler)
Lời giải đơn giản là:
- Xếp $m+n$ cái kẹo thành $1$ hàng, giữa chúng có $m+n-1$ khoảng cách. Đặt vào các khoảng cách đó $n-1$ "cái que" để chia chúng thành $n$ phần. Rõ ràng là có $C_{m+n-1}^{n-1}$ cách để thực hiện việc này. Đó cũng là đáp số của bài toán ban đầu. :)

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 02-12-2011 - 10:44


#4
alex_hoang

alex_hoang

    Thượng úy

  • Hiệp sỹ
  • 1152 Bài viết
Thêm một ví dụ nữa thầy ạ em tích tai diễn đàn ta

Bài 3:
Ta đặt A={1,2,3,4,5,.......,n} , một tập con B của tập A được gọi là " tập hợp đẹp" nếu tập B gồm 3 phần tử và tổng các phần tử của B chia hết cho 3. Hãy xác định số lượng các "tập hợp đẹp" của tập A.


đặt $U_n$ là số tập con $B$ của $A$, ta có $U_3=1,U_4=2$
bây giờ với $n-1$ là có $U_{n-1}$ tập B, rõ ràng $U_n=U_{n-1}+U_{n-1}=2U_{n-1}$, tại vì một tập B là $(1,-1,0)\equiv\mod(3)$
nên xét đến $n$ thì $n \in \{-1,1,0\}\equiv \mod(3)$ nên $n$ có thể thay bất kì số nào cùng số dư với nó cho 3 trong các tập con B của A, rõ ràng có $U_{n-1}$ tập như thế nữa, do đó ta được $U_n=U_{n-1}+U_{n-1}=2U_{n-1}$, có $ U_3=1$ suy ra,$U_n=2^{n-3}$


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:12

alex_hoang


HẸN NGÀY TRỞ LẠI VMF THÂN MẾN

http://www.scribd.co...oi-Ban-Cung-The

#5
Peter Pan

Peter Pan

    Sĩ quan

  • Thành viên
  • 360 Bài viết
@alex_hoang: Lời giải của em ở bài đó hình như sai rồi, em chưa sửa lại ( chưa xét tính bù trừ)
em cũng có một bài cũng hay có thể xài truy hồi như thế này mong mọi người tích cực thảo luận :D

Bài 4
Cho một tam giác đều, trong đó dựng $n^2$ tam giác đều nằng nhau, không chồng lên nhau và phủ kín tam giác đều lớn ở ngoài. Tính số lục giác đều được tạo thành.

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:10

\


#6
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Em cũng có một bài cũng hay có thể xài truy hồi như thế này mong mọi người tích cực thảo luận :D

Bài 4
Cho một tam giác đều, trong đó dựng $n^2$ tam giác đều nằng nhau, không chồng lên nhau và phủ kín tam giác đều lớn ở ngoài. Tính số lục giác đều được tạo thành.


Bài này liên quan đến tính chất của SỐ TAM GIáC

Đáp số của bài này là có $S_n=\dfrac{(n-1)(n-2)}{2}$ lục giác đều.
______________________________________________________

Hãy trình bày lời giải bài toán trên bằng phương pháp truy hồi!

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:11


#7
Didier

Didier

    đẹp zai có một ko hai

  • Thành viên
  • 403 Bài viết
Thầy ơi thầy xem xem có tài liệu Tổ Hợp & Toán Rời Rạc nào dễ hiểu không share cho em với em học phần này ko giỏi lắm mới chỉ dừng lạiở mức độ đọc hiểu nhưng ko tự làm được

Bài viết đã được chỉnh sửa nội dung bởi Didier: 20-11-2011 - 18:33


#8
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Em đọc cuốn này chưa?
Chủ yếu là bản thân em tự rèn luyện thôi, dần dần sẽ tiến bộ :D

#9
batigoal

batigoal

    Hướng dẫn viên $\LaTeX$

  • Thành viên
  • 261 Bài viết
Chủ đề này khá hay mời mọi người tiếp tục duy trì và phát triển nó.
Mình xin đóng góp 1 bài sau cũng dùng truy hồi.

Bài 5
Cho tập $A=\{-1;0;1\}$. Tìm số bộ $(a_1,a_1,...,a_n)$ thỏa:
1.$a_i$ thuộc $A$ với mọi $i=1,2,...,n$
2. $a_i-a_{i+1}$ thuộc $A$ với mọi $i=1,2,...,n-1$

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:08


#10
alex_hoang

alex_hoang

    Thượng úy

  • Hiệp sỹ
  • 1152 Bài viết
Batigoal nổi tiếng của diễn đàn mathscope ghé thăm thì thật là vinh hạnh quá ,kẻ hèn mọn này xin chém thử xem sao

Chủ đề này khá hay mời mọi người tiếp tục duy trì và phát triển nó.
Mình xin đóng góp 1 bài sau cũng dùng truy hồi.

Bài 5
Cho tập $A=\{-1;0;1\}$. Tìm số bộ $(a_1,a_1,...,a_n)$ thỏa:
1.$a_i$ thuộc $A$ với mọi $i=1,2,...,n$
2. $a_i-a_{i-1}$ thuộc $A$ với mọi $i=1,2,...,n-1$

Bài giải:
Trước hết ta gọi $S_n$ là các bộ $n$ số nguyên $(a_1,a_2,...,a_n$ thỏa mãn đề bài
Gọi $a_n,B_n,C_n$ là tập hợp các bộ số có $a_n$ là $-1,0,1$(Do các số $a_n$ đều thộc tập hợp $A$)
Như vậy thì hiển nhiên
\[\left| {{S_n}} \right| = \left| {{A_n}} \right| + \left| {{B_n}} \right| + \left| {{C_n}} \right|\]
Mặt khác thì ta thấy mỗi bộ thuộc $A_n$ và $B_n$ thì ta đều có thể bổ sung số $-1$ vào để được bộ thuộc $A_{n+1}$ vậy nên \[\left| {{A_{n + 1}}} \right| = \left| {{A_n}} \right| + \left| {{B_n}} \right|\]
Tương tự thì ta cũng tìm được
\[\left| {{C_{n + 1}}} \right| = \left| {{C_n}} \right| + \left| {{B_n}} \right|\]

\[\left| {{B_{n + 1}}} \right| = \left| {{A_n}} \right| + \left| {{B_n}} \right| + \left| {{C_n}} \right| = \left| {{S_n}} \right|\]
Từ đó ta có
\[\left| {{S_{n + 1}}} \right| = \left| {{A_{n + 1}}} \right| + \left| {{C_{n + 1}}} \right| + \left| {{B_{n + 1}}} \right| = (\left| {{A_n}} \right| + \left| {{B_n}} \right| + \left| {{C_n}} \right|) + \left| {{B_{n + 1}}} \right| + \left| {{B_n}} \right| = 2\left| {{S_n}} \right| + \left| {{S_{n - 1}}} \right|\]
Mà ta có thể tính được\[\left| {{S_{n + 1}}} \right| = \left| {{A_{n + 1}}} \right| + \left| {{C_{n + 1}}} \right| + \left| {{B_{n + 1}}} \right| = (\left| {{A_n}} \right| + \left| {{B_n}} \right| + \left| {{C_n}} \right|) + \left| {{B_{n + 1}}} \right| + \left| {{B_n}} \right| = 2\left| {{S_n}} \right| + \left| {{S_{n - 1}}} \right|\]
Bằng cách sử dụng phương trình sai phân tuyến tính ta tìm được
\[\left| {{S_n}} \right| = \frac{{{{\left( {1 + \sqrt 2 } \right)}^{n + 1}} + {{\left( {1 - \sqrt 2 } \right)}^{n + 1}}}}{2}\]

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:09

alex_hoang


HẸN NGÀY TRỞ LẠI VMF THÂN MẾN

http://www.scribd.co...oi-Ban-Cung-The

#11
alex_hoang

alex_hoang

    Thượng úy

  • Hiệp sỹ
  • 1152 Bài viết
Thưa thầy Thanh em có gửi một số bài tổ hợp sử dụng công thức truy hồi trong diễn đàn nhưng lan man quá nay em xin phép thầy tập hợp lại và trích dẫn nó ở topic này để topic trở nên phong phú và đa dạng về bài tập hơn


Bài 6:
Trong một cuộc thi đấu thể thao có $m$ huy chương, được phát trong $n$ ngày thi đấu.Ngày thứ nhất người ta phát một huy chương và $\dfrac{{1}}{7}$ số huy chương còn lại.Ngày thứ hai người ta phát hai huy chương và $\dfrac{{1}}{7}$ số huy chương còn lại.Những ngày sau tiếp tục như vậy.Ngày sau cùng còn lại $n$ huy chương để phát.Hỏi có tất cả bao nhiêu huy chương và phát trong bao nhiêu ngày

Gọi ${u_k}$ là số huy chương còn lại trước ngày thứ $k$, suy ra ${u_1} = m$, khi đó ta có:
$${u_{k + 1}} = \dfrac{6}{7}{u_k} - \dfrac{{6k}}{7} \Rightarrow {u_k} = {\left( {\dfrac{6}{7}} \right)^{k - 1}}\left( {m - 36} \right) - 6k + 42$$
$$ \Rightarrow {u_n} = n = {\left( {\dfrac{6}{7}} \right)^{n - 1}}\left( {m - 36} \right) - 6n + 42 \Rightarrow m - 36 = 7\left( {n - 6} \right){\left( {\dfrac{7}{6}} \right)^{n - 1}}$$
Vì $\left( {6,7} \right) = 1$ và ${6^{n - 1}} > n - 6$ nên $n - 6 = 0 \Leftrightarrow n = 6 \Rightarrow m = 36$

Vậy có 36 huy chương và phát trong 6 ngày.



Đề bài:Cho số nguyên dương $n$.Tìm tất cả các tập con của tập $X={1,2,3,...,2n}$ sao cho không tồn tại hai phần tử $x,y \in A$ thỏa mãn :$x+y=2n+1$

(Thụy Sỹ 2006)

Bài toán này bạn Trần Nguyễn Quốc Cường có lời giải rất hay và ngắn gọn nhưng nó cũng có thể giải bằng phương pháp truy hồi :icon6: các bạn suy nghĩ xem


Và bài toán này nữa
Bài 7
Cho $n$ tấm thẻ được đánh số từ $1$ đến $n$.Có bao nhiêu cách chọn ra một số thẻ (ít nhất $1$ tấm) sao cho tất cả các số trên các tấm thẻ đều lớn hơn hoặc bằng số tấm thẻ được chọn


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:07

alex_hoang


HẸN NGÀY TRỞ LẠI VMF THÂN MẾN

http://www.scribd.co...oi-Ban-Cung-The

#12
alex_hoang

alex_hoang

    Thượng úy

  • Hiệp sỹ
  • 1152 Bài viết
Em xin tiếp tục góp thêm một bài nữa
Bài 8
Tìm các số nguyên dương $n$ thỏa mãn các điều kiện
a) $n$ có $1000$ chữ số
b) Tất cả các chữ số của $n$ đều lẻ
c)Hiệu của hai số liên tiếp bất kì của $n$ là $2$

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:05

alex_hoang


HẸN NGÀY TRỞ LẠI VMF THÂN MẾN

http://www.scribd.co...oi-Ban-Cung-The

#13
Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5534 Bài viết

Em xin tiếp tục góp thêm một bài nữa
Bài 8
Tìm các số nguyên dương $n$ thỏa mãn các điều kiện
a) $n$ có $1000$ chữ số
b) Tất cả các chữ số của $n$ đều lẻ
c)Hiệu của hai số liên tiếp bất kì của $n$ là $2$


Trong tập ${S_k}$ các số nguyên dương $n$ có $k$ chữ số thoả (b) và ( c). Gọi ${A_k},{B_k},{C_k},{D_k},{E_k}$ lần lượt là tập các số tận cùng bởi $1,3,5,7,9$.

Từ mỗi số thuộc ${A_k}$ nếu ta bỏ đi chữ số tận cùng thì được một số thuộc ${B_{k - 1}}$. Mặt khác Từ mỗi số thuộc ${B_{k - 1}}$ nếu ta bổ sung thêm số $1$ làm chữ số tận cùng thì nhận được một số thuộc ${A_k}$. Do đó $\left| {{A_k}} \right| = \left| {{B_{k - 1}}} \right|$

Từ mỗi số thuộc ${B_k}$ nếu ta bỏ đi chữ số tận cùng thì được một số thuộc ${A_{k - 1}}$ hoặc ${C_{k - 1}}$, nếu ta bổ sung thêm số $3$ làm chữ số tận cùng thì nhận được một số thuộc ${B_k}$. Do đó $\left| {{B_k}} \right| = \left| {{A_{k - 1}}} \right| + \left| {{C_{k - 1}}} \right|$

Tương tự, cũng có: $$\left| {{C_k}} \right| = \left| {{B_{k - 1}}} \right| + \left| {{D_{k - 1}}} \right|,\,\,\left| {{D_k}} \right| = \left| {{C_{k - 1}}} \right| + \left| {{E_{k - 1}}} \right|,\,\,\left| {{E_k}} \right| = \left| {{D_{k - 1}}} \right|,\,k > 1$$
Từ đó ta có: $$\left| {{S_k}} \right| = \left| {{A_k}} \right| + \left| {{B_k}} \right| + \left| {{C_k}} \right| + \,\left| {{D_k}} \right| + \left| {{E_k}} \right| = \left| {{A_{k - 1}}} \right| + 2\left| {{B_{k - 1}}} \right| + 2\left| {{C_{k - 1}}} \right| + 2\left| {{D_{k - 1}}} \right| + \left| {{E_{k - 1}}} \right|$$
$$ = 2\left| {{A_{k - 2}}} \right| + 3\left| {{B_{k - 2}}} \right| + 4\left| {{C_{k - 2}}} \right| + 3\left| {{D_{k - 2}}} \right| + 2\left| {{E_{k - 2}}} \right|$$
$$ = 3\left| {{A_{k - 3}}} \right| + 6\left| {{B_{k - 3}}} \right| + 6\left| {{C_{k - 3}}} \right| + 6\left| {{D_{k - 3}}} \right| + 3\left| {{E_{k - 3}}} \right|$$
Suy ra $\left| {{S_k}} \right| = 3\left| {{S_{k - 2}}} \right|,k > 3$. Lại có $\left| {{S_2}} \right| = 8 \Rightarrow \left| {{S_{1000}}} \right| = {8.3^{499}}$.

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-11-2011 - 17:05


#14
Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5534 Bài viết
Xin góp 1 bài. Nhờ thầy Thanh đánh số thứ tự bài làm.

Bài 9: [Bulgaria - 1995] Cho số nguyên $n \geqslant 2$. Hãy tìm số các hoán vị $\left( {{a_1},{a_2},...,{a_n}} \right)$ của $1,2,...,n$ sao cho tồn tại duy nhất một chỉ số $i \in \left\{ {1,2,...,n - 1} \right\}$ thoả ${a_i} > {a_{i + 1}}$.

#15
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Bài 9: [Bulgaria - 1995] Cho số nguyên $n \geqslant 2$. Hãy tìm số các hoán vị $\left( {{a_1},{a_2},...,{a_n}} \right)$ của $1,2,...,n$ sao cho tồn tại duy nhất một chỉ số $i \in \left\{ {1,2,...,n - 1} \right\}$ thoả ${a_i} > {a_{i + 1}}$.


Làm thử bài này :D

Ta chia tập các hoán vị của $n$ số nguyên dương đầu tiên thành 3 tập rời nhau sau:

$S_n$ là tập các hoán vị $(a_1,a_2,...,a_n)$ của $n$ số nguyên dương đầu tiên có đúng một điểm trội $(a_i>a_{i+1});\;\;i \in \{1,2,...,n-1\}$.


$\overline{S_n}$ là tập các hoán vị $(a_1,a_2,...,a_n)$ của $n$ số nguyên dương đầu tiên có từ hai điểm trội trở lên.

và tập $P_n=\{(1,2,...,n)\}$ không có điểm trội nào cả

Bây giờ ta sẽ lập Công thức Truy hồi để tính $|S_n|$

Trước tiên, dễ thấy $|S_2|=1$ (có duy nhất một hoán vị thoả mãn là (2,1))

- Xét $n \ge 3$
- Với mỗi bộ phần tử của tập $S_{n-1}$ ta có 2 cách để đặt $n$ vào để tạo thành 1 hoán vị n phần tử có 1 điểm trội: 1 là vị trí cuối cùng , 2 là vị trí điểm trội $(...,a_i,n,a_{i+1},...)$
- Với bộ $(1,2,...,n-1)$ thì ta có $n-1$ cách đặt $n$ vào các vị trí trừ vị trí cuối cùng.

Do đó ta có : $|S_n|=2|S_{n-1}|+n-1\;\;\;(1)$

Từ công thức truy hồi (1), ta tính được:$$|S_n|-2|S_{n-1}|=n-1$$
$$2|S_{n-1}|-2^2|S_{n-2}|=2(n-2)$$
$$...$$
$$2^{n-3}|S_3|-2^{n-2}|S_2|=2^{n-3}.2$$
____________________________________________________________________________
Cộng vế theo vế ta có:$$|S_n|-2^{n-2}|S_2|=\sum\limits_{k=0}^{n-3}\left(2^k(n-1-k)\right)$$
$$\Rightarrow |S_n|=\sum\limits_{k=0}^{n-2}\left(2^k(n-1-k)\right)\;\;\;(*)$$
$$\Rightarrow |S_n|=2^n-n-1$$
____________________________________________________________________________
P/s: Tính tổng (*) - Xin dành cho các bạn như một bài tập ^_^
Giải nhanh các bài còn lại để post tiếp nào! :lol:

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 01-12-2011 - 18:11


#16
Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5534 Bài viết
Xin trích lại lời giải cho bài 9.

Gọi ${S_n}$ là số các hoán vị thoả mãn điều kiện bài toán. Để ý rằng số các hoán vị mà ${a_n} = n$ là ${S_{n - 1}}$. Còn số các hoán vị $\left( {{a_1},{a_2},...,{a_n}} \right)$ với ${a_i} = n\,\,\left( {1 \leqslant i \leqslant n - 1} \right)$ là $C_{n - 1}^{i - 1}$

Do vậy: $${S_n} = {S_{n - 1}} + \sum\limits_{i = 1}^{n - 1} {C_{n - 1}^{i - 1}} = {S_{n - 1}} + {2^{n - 1}} - 1$$
Chú ý ${S_2} = 1$, từ đó ta có: $$\boxed{{S_n} = {2^n} - n - 1}$$

#17
Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5534 Bài viết
Lời giải dùng phương pháp truy hồi cho bài Thụy Sỹ 2006

Gọi ${a_n}$ là số tập con $A$ của $X$ có tính chất $T$ thoả mãn luôn tồn tại hai phần tử $x,y \in A$ sao cho $x + y = 2n + 1$.

Khi đó các tập con $A \subset \left\{ {1,2,...,2n,2n + 1,2n + 2} \right\}$ xảy ra hai trường hợp.

Trường hợp 1: Trong tập $A$ chứa hai phần tử $1$ và $2n+2$, trong trường hợp này số tập $A$ có tính chất $T$ chính bằng số tập con của tập gồm $2n$ phần tử $\left\{ {2,3,4,...,2n,2n + 1} \right\}$ và số tập con của tập này bằng ${2^{2n}}$.

Trường hợp 2: Trong tập $A$ không chứa đầy đủ hai phần tử $1$ và $2n+2$. Khi đó $A$ phải chứa một tập ${A'}$ là tập con của tập $\left\{ {2,3,4,...,2n,2n + 1} \right\}$ sao cho có hai phần tử $x',y' \in A':x' + y' = 2n + 3$. Số tập con ${A'}$ chính bằng số tập con của tập $\left\{ {1,2,...,2n} \right\}$ có tính chất $T$.

Hơn nữa với mỗi tập ${A'}$ ta có được $3$ tập $A$. Do đó ${a_{n + 1}} = 3{a_n} + {2^{2n}} \Rightarrow {a_n} = {4^n} - {3^n}$.

Vậy số tập con thoả yêu cầu bài toán là ${4^n} - {a_n} = \boxed{{3^n}}$.

#18
Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5534 Bài viết
Bài 10: Giả sử ${F_k}$ là tập hợp tất cả các bộ $\left( {{A_1},{A_2},...,{A_k}} \right)$ trong đó ${A_i}\,\left( {i = \overline {1,k} } \right)$ là một tập con của $\left\{ {1,2,...,n} \right\}$. Các tập ${{A_1},{A_2},...,{A_k}}$ có thể trùng nhau. Tính
$${S_n} = \sum\limits_{\left( {{A_1},{A_2},...,{A_k}} \right) \in {F_k}} {\left| {{A_1} \cup {A_2} \cup ... \cup {A_k}} \right|} $$

#19
Mylovemath

Mylovemath

    Thượng sĩ

  • Thành viên
  • 225 Bài viết
Cái kí hiệu chữ E kia đọc là gì thế các anh . :sum :huh:
i LOVE u

""Yêu hay sao mà Nhìn ""

#20
Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5534 Bài viết

Cái kí hiệu chữ E kia đọc là gì thế các anh . :sum :huh:


$\boxed{\sum {} }$ là tổng Sigma bạn à.

Ví dụ: $$\boxed{{x_1} + {x_2} + {x_3} + ... + {x_n} = \sum\limits_{i = 1}^n {{x_i}} }$$




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

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