Đếm bằng truy hồi - CLB Toán Trường Chuyên Lương Thế Vinh

Chào mừng quý vị đến với website của ...

Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tài liệu của Thư viện về máy tính của mình.
Nếu chưa đăng ký, hãy nhấn vào chữ ĐK thành viên ở phía bên trái, hoặc xem phim hướng dẫn tại đây
Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay phía bên trái.

Gốc > CÁC CHUYÊN ĐỀ ÔN HSG > TỔ HỢP >

Tạo bài viết mới Đếm bằng truy hồi

SỬ DỤNG PHƯƠNG PHÁP TRUY HỒI

ĐỂ GIẢI MỘT SỐ DẠNG TOÁN TỔ HỢP

TRẦN VĂN THƯƠNG

(GV THPT Phú Mỹ, Bà Rịa Vũng Tàu)

Bài toán tổ hợp là một loại toán khó và đã có nhiều phương pháp để giải chúng như phương pháp song ánh, phương pháp hàm sinh,…; bài viết này trình bày phương pháp truy hồi để giải một số bài toán đếm. Nội dung phương pháp này là thiết lập hệ thức truy hồi giữa phép đếm cần tính $\88dpi {{s}_{n}}$ với $\88dpi {{s}_{n-1}},{{s}_{n-2}},...$ từ đó xác định $\88dpi {{s}_{n}}$ . Trong bài viết ta kí hiệu $\88dpi \left| X \right|$ là số phần tử của tập $\88dpi X$ .

Thí dụ 1( Romania 2003) Cho số nguyên dương $\88dpi n$ . Có bao nhiêu số tự nhiên có $\88dpi n$ chữ số được lập từ các số thuộc tập $\88dpi \left\{ 2;3;7;9 \right\}$ và chia hết cho 3?.

Lời giải

Gọi $\88dpi {{A}_{n}},{{B}_{n}}$ là tập tất cả các số tự nhiên có $\88dpi n$ chữ số lần lượt chia hết cho 3 và không chia hết cho 3 được lập từ các số $\88dpi \left\{ 2;3;7;9 \right\}$ .

Xét một phần tử thuộc $\88dpi {{A}_{n}}$ thì có 2 cách thêm vào chữ số cuối để được một phần tử của $\88dpi {{A}_{n+1}}$ và có 2 cách thêm vào chữ số cuối để được một phần tử của $\88dpi {{B}_{n+1}}$ .

Xét một phần tử thuộc $\88dpi {{B}_{n}}$ thì có 1 cách thêm vào chữ số cuối để được một phần tử của $\88dpi {{A}_{n+1}}$ và có đúng 3 cách thêm vào chữ số tận cùng để được một phần tử của $\88dpi {{B}_{n+1}}$ .

Vậy $\88dpi \left\{ \begin{matrix} \left| {{A}_{n+1}} \right|=2\left| {{A}_{n}} \right|+\left| {{B}_{n}} \right|\text{ }\left( 1 \right) \\ \left| {{B}_{n+1}} \right|=2\left| {{A}_{n}} \right|+3\left| {{B}_{n}} \right|\text{ }\left( 2 \right) \\ \end{matrix} \right.$

Đặt $\88dpi {{a}_{n}}=\left| {{A}_{n}} \right|,{{b}_{n}}=\left| {{B}_{n}} \right|$ thì từ $\88dpi \left( 1 \right)$ suy ra $\88dpi {{b}_{n}}={{a}_{n+1}}-2{{a}_{n}}$ thay vào $\88dpi \left( 2 \right)$ ta được $\88dpi {{a}_{n+2}}-2{{a}_{n+1}}=2{{a}_{n}}+3\left( _{n+1}-2{{a}_{n}} \right)$

$\88dpi \Leftrightarrow {{a}_{n+2}}-5{{a}_{n+1}}+4{{a}_{n}}=0$ $\88dpi \Leftrightarrow {{a}_{n+2}}-{{a}_{n+1}}=4\left( {{a}_{n+1}}-{{a}_{n}} \right)\text{ }\left( * \right)$

Từ $\88dpi \left( * \right)$ suy ra $\88dpi {{a}_{n+2}}-{{a}_{n+1}}={{4}^{n}}\left( {{a}_{2}}-{{a}_{1}} \right)={{4}^{n+1}}$ ( do $\88dpi {{a}_{1}}=2,{{a}_{2}}=6$ ).

$\88dpi \Rightarrow {{a}_{n+2}}={{a}_{n+1}}+{{4}^{n+1}}$ $\88dpi ={{a}_{n}}+{{4}^{n}}+{{4}^{n+1}}=...={{a}_{1}}+4+...+{{4}^{n+1}}$ $\88dpi =2+\frac{4\left( {{4}^{n+1}}-1 \right)}{3}=\frac{{{4}^{n+2}}+2}{3}$ .

$\88dpi \Rightarrow {{a}_{n}}=\frac{{{4}^{n}}+2}{3},n\in {{\mathbb{N}}^{*}}$ . Vậy có $\88dpi \frac{{{4}^{n}}+2}{3}$ số tự nhiên thỏa mãn yêu cầu bài toán.

Thí dụ 2. Từ các số thuộc tập $\88dpi E=\left\{ 1;2;3;4;5;6;7;8;9 \right\}$ có thể lập được bao nhiêu số tự nhiên có $\88dpi n$ chữ số mà

trong mỗi số đó đều chứa một số lẻ chữ số 1 và một số chẵn chữ số 2 ( $\88dpi n$ là số nguyên dương cho trước).

Lời giải

Kí hiệu $\88dpi {{X}_{n}}$ là tập tất cả các số tự nhiên có $\88dpi n$ chữ số được lập từ các số của tập $\88dpi E$ và $\88dpi {{A}_{n}},{{B}_{n}},{{C}_{n}},{{D}_{n}}$ lần lượt là tập tất cả các số tự nhiên có $\88dpi n$ chữ số được lập từ các số của tập $\88dpi E$ mà trong mỗi số đó lần lượt chứa ( lẻ các chữ số 1, chẵn các chữ số 2);( lẻ các chữ số 1, lẻ các chữ số 2); ( chẵn các chữ số 1, lẻ các chữ số 2);( chẵn các chữ số 1, chẵn các chữ số 2).

Dễ thấy $\88dpi {{A}_{n}},{{B}_{n}},{{C}_{n}},{{D}_{n}}$ đôi một rời nhau và $\88dpi {{X}_{n}}={{A}_{n}}\cup {{B}_{n}}\cup {{C}_{n}}\cup {{D}_{n}}$ do đó $\88dpi \left| {{X}_{n}} \right|=\left| {{A}_{n}} \right|+\left| {{B}_{n}} \right|+\left| {{C}_{n}} \right|+\left| {{D}_{n}} \right|$ .Ta có $\88dpi \left| {{X}_{n}} \right|={{9}^{n}}$ .

Dễ thấy $\88dpi \left| {{A}_{n+1}} \right|=7\left| {{A}_{n}} \right|+\left| {{B}_{n}} \right|+\left| {{D}_{n}} \right|\text{ }\left( * \right)$ .

Xét một phần tử thuộc $\88dpi {{A}_{n}}$ , ta thực hiện phép biến đổi: giữ nguyên các chữ số khác 1 và 2, các chữ số 1( nếu có) đổi thành 2 và các chữ số 2( nếu có) đổi thành 1 ta được một phần tử của $\88dpi {{C}_{n}}$ , nếu lấy một phần tử thuộc $\88dpi {{C}_{n}}$ và cũng thực hiện phép biến đổi trên ta được một phần tử của $\88dpi {{A}_{n}}$ . Phép biến đổi này là một song ánh từ tập $\88dpi {{A}_{n}}$ vào tập $\88dpi {{C}_{n}}$ nên $\88dpi \left| {{A}_{n}} \right|=\left| {{C}_{n}} \right|$ , do đó từ $\88dpi \left( * \right)$ suy ra $\88dpi \left| {{A}_{n+1}} \right|=5\left| {{A}_{n}} \right|+\left( \left| {{A}_{n}} \right|+\left| {{B}_{n}} \right|+\left| {{C}_{n}} \right|+\left| {{D}_{n}} \right| \right)$ $\88dpi =5\left| {{A}_{n}} \right|+\left| {{X}_{n}} \right|=5\left| {{A}_{n}} \right|+{{9}^{n}}$

Kí hiệu

$\88dpi {{a}_{n}}=\left| {{A}_{n}} \right|\Rightarrow {{a}_{n+1}}=5{{a}_{n}}+{{9}^{n}}$ $\88dpi \Leftrightarrow {{a}_{n+1}}-\frac{1}{4}{{.9}^{n+1}}=5\left( {{a}_{n}}-\frac{1}{4}{{.9}^{n}} \right)\text{ }\left( ** \right)$

Từ $\88dpi \left( ** \right)$ ta có được $\88dpi {{a}_{n+1}}-\frac{1}{4}{{.9}^{n+1}}={{\text{5}}^{n}}\left( {{a}_{1}}-\frac{1}{4}.9 \right)=-\frac{{{5}^{n+1}}}{4}$

$\88dpi \Leftrightarrow {{a}_{n+1}}=\frac{{{9}^{n+1}}-{{5}^{n+1}}}{4}$ ( do $\88dpi {{a}_{1}}=1$ ).Vậy $\88dpi {{a}_{n}}=\frac{{{9}^{n}}-{{5}^{n}}}{4}$ .

Thí dụ 3.(BRVT-2010) Cho số nguyên dương $\88dpi n$ . Có bao nhiêu số tự nhiên có $\88dpi n$ chữ số, trong mỗi số đó các chữ số đều lớn hơn 1 và không có hai chữ số khác nhau cùng nhỏ hơn 7 đứng liền nhau.

Lời giải

Kí hiệu $\88dpi {{X}_{n}}$ là tập tất cả các số tự nhiên có $\88dpi n$ chữ số thỏa mãn đề bài, $\88dpi {{A}_{n}},{{B}_{n}}$ là các tập con của $\88dpi {{X}_{n}}$ theo thứ tự các số có tận cùng nhỏ hơn 7; các số có tận cùng lớn hơn 6.

Ta có $\88dpi {{X}_{n}}={{A}_{n}}\cup {{B}_{n}},{{A}_{n}}\cap {{B}_{n}}=\varnothing \Rightarrow \left| {{X}_{n}} \right|=\left| {{A}_{n}} \right|+\left| {{B}_{n}} \right|$ .

Lấy một phần tử thuộc $\88dpi {{X}_{n+1}}$ bỏ đi chữ số tận cùng ta được một phần tử của $\88dpi {{X}_{n}}$ , ngược lại lấy một phần tử của $\88dpi {{X}_{n}}$ .

Nếu tận cùng nhỏ hơn 7 ( thuộc $\88dpi {{A}_{n}}$ ) thì chỉ có một cách thêm vào chữ số cuối để được một phần tử của $\88dpi {{A}_{n+1}}$ và có đúng 3 cách thêm vào chữ số cuối để được một phần tử của $\88dpi {{B}_{n+1}}$ .

Nếu tận cùng lớn hơn 6 ( thuộc $\88dpi {{B}_{n}}$ ) thì có 5 cách thêm vào chữ số cuối để được một phần tử của $\88dpi {{A}_{n+1}}$ và đúng 3 cách thêm vào chữ số cuối để được một phần tử của $\88dpi {{B}_{n+1}}$ .

Từ các lập luận trên ta có $\88dpi \left\{ \begin{matrix} \left| {{A}_{n+1}} \right|=\left| {{A}_{n}} \right|+5\left| {{B}_{n}} \right|\text{ }\left( 1 \right) \\ \left| {{B}_{n+1}} \right|=3\left| {{A}_{n}} \right|+3\left| {{B}_{n}} \right|\text{ }\left( 2 \right) \\ \end{matrix} \right.$ .

Từ $\88dpi \left( 1 \right)$ và $\88dpi \left( 2 \right)$ suy ra $\88dpi \left| {{A}_{n+1}} \right|+\left| {{B}_{n+1}} \right|=4\left| {{A}_{n}} \right|+8\left| {{B}_{n}} \right|=4\left( \left| {{A}_{n}} \right|+\left| {{B}_{n}} \right| \right)+4\left| {{B}_{n}} \right|$ $\88dpi =4\left( \left| {{A}_{n}} \right|+\left| {{B}_{n}} \right| \right)+4\left( \left| {{A}_{n-1}} \right|+\left| {{B}_{n-1}} \right| \right)\text{ }\left( n\ge 2 \right)$

Kí hiệu $\88dpi {{x}_{n}}=\left| {{X}_{n}} \right|$ ta có $\88dpi {{x}_{n+2}}=4{{x}_{n+1}}+12{{x}_{n}},n\in {{\mathbb{N}}^{*}}$ .

Ta có $\88dpi \left\{ \begin{matrix} {{x}_{n+2}}-6{{x}_{n+1}}=-2\left( {{x}_{n+1}}-6{{x}_{n}} \right) \\ {{x}_{n+2}}+2{{x}_{n+1}}=6\left( {{x}_{n+1}}+2{{x}_{n}} \right) \\ \end{matrix} \right.$

$\88dpi \Rightarrow \left\{ \begin{matrix} {{x}_{n+2}}-6{{x}_{n+1}}={{\left( -2 \right)}^{n}}\left( {{x}_{2}}-6{{x}_{1}} \right) \\ {{x}_{n+2}}+2{{x}_{n+1}}={{6}^{n}}\left( {{x}_{2}}+2{{x}_{1}} \right) \\ \end{matrix} \right.$ $\88dpi \Rightarrow {{x}_{n+1}}=\frac{1}{8}\left[ \left( {{x}_{2}}+2{{x}_{1}} \right){{6}^{n}}-\left( {{x}_{2}}-6{{x}_{1}} \right){{\left( -2 \right)}^{n}} \right]$ .

Dễ thấy $\88dpi {{x}_{1}}=8$ , ta tìm $\88dpi {{x}_{2}}$ . Xét $\88dpi n\in {{X}_{2}}\Rightarrow n=\overline{ab};a,b\in \left\{ 2,6,4,5,6,7,8,9 \right\}$ .

Nếu $\88dpi a\in \left\{ 2;3;4;5;6 \right\}$ thì có 4 cách chọn $\88dpi b$ .

Nếu $\88dpi a\in \left\{ 7;8;9 \right\}$ thì có 8 cách chọn $\88dpi b$ .

Vậy $\88dpi {{x}_{2}}=5.4+3.8=44$ ,do đó $\88dpi {{x}_{n}}=\frac{1}{2}\left[ {{15.6}^{n-1}}+{{\left( -2 \right)}^{n-1}} \right]$ .

Thí dụ 4. Có $\88dpi n$ người ngồi thành một hàng ngang vào $\88dpi n$ chiếc ghế. Hỏi có bao nhiêu cách lập hàng mới cho $\88dpi n$ người đó mà trong mỗi cách lập hàng mới: mỗi người hoặc giữ nguyên vị trí của mình, hoặc đổi chỗ cho người liền bên trái, hoặc đổi chỗ cho người liền bên phải.

Lời giải

Đánh số thứ tự vị trí các ghế từ trái qua phải là $\88dpi 1,2,...,n$

Gọi $\88dpi {{s}_{n}}$ là số cách lập hàng mới cho $\88dpi n$ người thỏa mãn đề bài.

Dễ thấy $\88dpi {{s}_{1}}=1,{{s}_{2}}=2$ .

Với $\88dpi n\ge 3$

Xét một cách lập hàng mới thỏa mãn điều kiện. Có hai loại hàng được lập:

Loại 1: Người ở vị trí số 1 giữ nguyên vị trí. Rõ ràng số hàng được lập loại này là $\88dpi {{s}_{n-1}}$ cách.

Loại 2: Người ở vị trí số 1 đổi chỗ, khi đó người ở vị trí số 1 chỉ có thể xếp vào vị trí số 2 và người ở vị trí 2 phải chuyển sang vị trí 1. Số hàng loại này là $\88dpi {{s}_{n-2}}$ .

Từ đó ta có $\88dpi {{s}_{n}}={{s}_{n-1}}+{{s}_{n-2}};n\ge 3$ .

Vậy $\88dpi {{s}_{1}}=1,{{s}_{2}}=2,{{s}_{n+2}}={{s}_{n+1}}+{{s}_{n}},n\in {{\mathbb{N}}^{*}}$ .

Từ đây dễ dàng tìm được $\88dpi {{s}_{n}}=\frac{1}{\sqrt{5}}\left[ {{\left( \frac{1+\sqrt{5}}{2} \right)}^{n+1}}-{{\left( \frac{1-\sqrt{5}}{2} \right)}^{n+1}} \right]$ .

Nhắn tin cho tác giả

Nguyễn Tất Thu @ 11:28 01/04/2014
Số lượt xem: 9897

Số lượt thích: 7 người (Phạm Thanh Liêm, TRƯƠNG THỊ BÉ, Kim Phong Phạm Vũ , ...)

hí dụ 5.( IMO-2011) Giả sử $n> 0$ là một số nguyên. Cho một cái cân đĩa và $n$ quả cân có trọng lượng

${{2}^{0}},{{2}^{1}},...,{{2}^{n-1}}$ . Ta muốn đặt lên cái cân mỗi một trong $n$ quả cân, lần lượt từng quả một, theo cách để đảm bảo đĩa cân bên phải không bao giờ nặng hơn đĩa cân bên trái . Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi đặt nó lên đĩa bên phải, hoặc đĩa bên trái, cho đến khi tất cả các quả cân đều được đặt lên đĩa. Hỏi có bao nhiêu cách để thực hiện việc đặt cân theo đúng mục đích đề ra?

Lời giải

Gọi ${{s}_{n}}$ là số cách thực hiện việc đặt $n$ quả cân lên đĩa thỏa mãn yêu cầu đề ra.

Xét cách đặt $n+1$ quả cân có trọng lượng ${{2}^{0}},{{2}^{1}},...,{{2}^{n}}$ .

Do ${{2}^{0}}+{{2}^{1}}+...+{{2}^{n-1}}={{2}^{n}}-1< {{2}^{n}}$ nên trong mọi cách đặt cân thỏa mãn thì quả cân có trọng lượng ${{2}^{n}}$ luôn được đặt ở đĩa cân bên trái.

Nếu quả cân ${{2}^{n}}$ được chọn để đặt cuối cùng ( chỉ có một cách đặt, vì quả ${{2}^{n}}$ chỉ đặt lên đĩa bên trái ) và số cách đặt $n$ quả cân còn lại là ${{s}_{n}}$ .

Nếu quả cân ${{2}^{n}}$ được đặt ở bước thứ $i$ ( $i=1,2,..,n$ ). Do có $n$ cách chọn $i$ , và trong trường hợp này quả cân có trọng lượng ${{2}^{n-1}}$ có 2 cách đặt ( đặt lên đĩa bên phải hay đĩa bên trái đều thỏa mãn) , do đó số cách đặt $n+1$ quả cân trong trường hợp này là $2n{{s}_{n}}$ . Vậy ta có hệ thức truy hồi ${{s}_{n+1}}=2n{{s}_{n}}+{{s}_{n}}=\left( 2n+1 \right){{s}_{n}}$ .

Ta có ${{s}_{1}}=1$ nên ${{s}_{n}}=\left( 2n-1 \right)\left( 2n-3 \right)....3.1$ .

Thí dụ 6. Cho số nguyên dương $n\ge 2$ . Xét tập $A=\left\{ 1;2;3;4;...;{{2}^{n}} \right\}$ . Tìm số các tập con $B$ của tập $A$ mà mỗi tập con đó có tính chất: Nếu $x,y$ là hai phần tử khác nhau của $A$ và có tổng là một lũy thừa của 2 thì đúng một trong hai phần tử $x,y$ này thuộc $B$ .

Lời giải

Ta gọi một tập thỏa yêu cầu bài toán là một tập tốt.

Với mỗi số nguyên $n\ge 2$ , gọi ${{F}_{n}}$ là tập hợp gồm tất cả các tập tốt thỏa mãn yêu cầu bài toán.

Chẳng hạn với $n=2$ ta có $A=\left\{ 1;2;3;4 \right\}$ , trong $A$ chỉ có hai số $1$ và 3 thỏa $1+3={{2}^{2}}$ nên ${{F}_{2}}=\left\{ \left\{ 1 \right\},\left\{ 3 \right\},\left\{ 1;2\right\},\left\{ 1;4 \right\};\left\{ 1;2;4 \right\};\left\{ 2;3\right\};\left\{ 3;4 \right\};\left\{ 2;3;4 \right\} \right\}$ .

Kí hiệu ${{s}_{n}}=\left| {{F}_{n}} \right|$ , ta có ${{s}_{2}}=8$ .

Xét một tập tốt ${{B}_{n+1}}\in {{F}_{n+1}}$ , khi đó ${{B}_{n+1}}={{B}_{n}}\cup {{C}_{n}}$ với ${{B}_{n}}$ là một tập tốt của ${{F}_{n}}$ và ${{C}_{n}}$ là một tập con nào đó của tập $\left\{ {{2}^{n}}+1;{{2}^{n}}+2;...;{{2}^{n+1}} \right\}$ .

Ta đếm số tập tốt không chứa phần tử ${{2}^{n+1}}$ của ${{F}_{n+1}}$ bằng cách đếm số khả năng thêm mỗi phần tử của tập $\left\{ {{2}^{n}}+1;{{2}^{n}}+2;...;{{2}^{n+1}}-1 \right\}$ vào ${{B}_{n}}$ . Ta viết các phần tử này dưới dạng ${{2}^{n+1}}-a;a\in \left\{ 1;2;{{...2}^{n}}-1 \right\}$ .

Nếu $a\in {{B}_{n}}$ thì không thể thêm phần tử ${{2}^{n+1}}-a$ vào ${{B}_{n}}$ ( do ${{B}_{n+1}}$ là một tập tốt).

Nếu $a\notin {{B}_{n}}$ thì chắc chắn phải thêm phần tử ${{2}^{n+1}}-a$ vào ${{B}_{n}}$ ( do ${{B}_{n+1}}$ là một tập tốt).

Do đó mỗi phần tử của $\left\{ {{2}^{n}}+1;{{2}^{n}}+2;...;{{2}^{n+1}}-1 \right\}$ chỉ có một khả năng duy nhất để thêm vào một tập nào đó của ${{F}_{n}}$ . Từ đây suy ra số tập tốt của ${{F}_{n+1}}$ không chứa ${{2}^{n+1}}$ là ${{s}_{n}}$ .

Dễ thấy ${{B}_{n+1}}\cup \left\{ {{2}^{n+1}} \right\}$ là một tập tốt thuộc ${{F}_{n+1}}$ trong đó ${{B}_{n+1}}$ là một tập tốt của ${{F}_{n+1}}$ không chứa phần tử ${{2}^{n+1}}$ , do đó số tập tốt có chứa phần tử ${{2}^{n+1}}$ của ${{F}_{n+1}}$ cũng là ${{s}_{n}}$ .

Vậy ${{s}_{n+1}}={{s}_{n}}+{{s}_{n}}=2{{s}_{n}}$ ; kết hợp với ${{s}_{2}}=8$ ta có ${{s}_{n}}={{2}^{n+1}}$ .

Cuối cùng là một số bài tập để các bạn luyện tập.

1. Có bao nhiêu xâu nhị phân có độ dài $n$ trong đó không có hai bít 1 đứng cạnh nhau.

2. (APMO-1997) Giả sử $F$ là tập hợp tất cả các bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ trong đó ${{A}_{i}}\left( i=1,2,..,k \right)$ là một tập con của $\left\{ 1;2;...;1998 \right\}$ . Hãy tính ${{S}_{k}}=\sum\limits_{\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}}\right)\in F}{\left| {{A}_{1}}\cup {{A}_{2}}\cup ...\cup {{A}_{k}}\right|}$ .

3. Có bao nhiêu số tự nhiên $n$ thỏa mãn các điều kiện:

a) $n$ có 2012 chữ số.

b) Tất cả các chữ số của $n$ đều lẻ.

c) Hiệu hai số liên tiếp bất kì của $n$ luôn bằng 2.

4. ( JapanMO 2007) Có 15 tấm thẻ được đánh số từ 1 đến 15. Có bao nhiêu cách chọn ra một số tấm thẻ ( ít nhất 1 tấm) sao cho tất cả các số ghi trên các tấm thẻ này đều lớn hơn hoặc bằng số tấm thẻ được chọn.

5.( IMO -1979) Giả sử $A$ và $E$ là hai đỉnh đối diện của một bát giác đều. Một con ếch bắt đầu nhảy từ $A$ . Tại mỗi đỉnh của bát giác ( trừ đỉnh $E$ ), mỗi cú nhảy con ếch chỉ có thể nhảy tới hai đỉnh kề với nó. Khi con ếch nhảy vào đỉnh $E$ thì nó bị mắc kẹt ở đó. Cho trước số nguyên dương . Hỏi với cú nhảy, có bao nhiêu cách để con ếch nhảy vào đỉnh ?

6.( VMO- 2009) Cho số nguyên dương . Kí hiệu là tập hợp số nguyên dương đầu tiên. Hỏi có tất cả bao nhiêu tập con của có tính chất: Trong không tồn tại các số mà .