Tài liệu Bồi dưỡng học sinh giỏi môn toán thpt chuyên đề phương pháp thiết lập hệ thức truy hồi trong các bài toán đếm

.DOC

1407

144

PHƯƠNG PHÁP THIẾT LẬP HỆ THỨC TRUY HỒI
TRONG CÁC BÀI TOÁN ĐẾM
I.Cơ sở của phương pháp
Trong nhiều trường hợp, việc đếm trực tiếp các đối tượng là khó khăn và phức
tạp. Nếu ta thiết lập được mối quan hệ truy hồi giữa số lượng đối tượng cần đếm
trong nhóm
n
đối tượng với số lượng đối tượng cần đếm trong các nhóm ít hơn
n
đối tượng thì ta có thể đưa về đếm số đối tượng trong nhóm mới với số đối
tượng ít hơn. Nói cách khác, thay vì đếm trực tiếp
( )S n
, ta thiết lập hệ thức liên
hệ giữa
( )S n
với
( 1)S n 
,
( 2)S n 
…, từ đó dùng kiến thức về dãy số để tìm
được
( )S n
.
II.Các ví dụ
Ví dụ 1. Cho số nguyên dương
n
. Có bao nhiêu số tự nhiên chia hết cho 3, có
n

chữ số và các chữ số đều thuộc
{3,4,5,6}?
Lời giải:
. Gọi
n
x
là số các số có
n
chữ số lập từ
{3,4,5,6}
và chia hết cho 3,

n
y
là số các số có
n
chữ số lập từ
{3,4,5,6}
và không chia hết cho 3.
. Xét 1 số có
n
chữ số thoả mãn bài toán là
1 2
...
n
x a a a
TH1: Nếu
1 2 1
... 3
n
a a a

M
thì
3 3
n
x aM M
, do đó có 2 cách chọn
n
a
. Như vậy
trường hợp này có 2
1n
x

cách chọn
x
.
TH2:
1 2 1
...
n
a a a

không chia hết cho 3. Khi đó ta chỉ chọn được 1 số
n
a

thuộc
{3,4,5,6}
để
1 2
... 3
n
x a a a M
. Như vậy trường hợp này có

1n
y

cách chọn
x
.
Như vậy ta có:
1 1
2.
n n n
x x y
 
 

Tương tự ta thu được:
1 1
2. 3.
n n n
y x y
 
 
Trang 1
Biến đổi ta thu được
1 1
5 4 0.
n n n
x x x
 
  
Giải phương trình sai phân này với chú ý rằng
1 2
2; 6x x 
ta tìm được

4 2
3
n
n
x


Ví dụ 2 . Cho số nguyên
2n 
. Hãy tìm số các hoán vị
 
1 2
, ,...,
n
a a a
của
 
1,2,...,n
sao cho tồn tại duy nhất một chỉ số
{1,2,..., 1}i n 
thoả mãn
1i i
a a


.
Lời giải:
Gọi
n
S
là số các hoán vị thoả mãn điều kiện bài toán.
.
n
a n 
số các hoán vị có dạng
 
1 2 1
, ,..., ,
n
a a a n

là
1n
S

.
1n
a n

 
số các hoán vị có dạng
 
1 2 2
, ,..., , ,
n n
a a a n a

là
2
1
n
n
C


.
i
a n 
số các hoán vị
 
1 2
, ,...,
n
a a a
thoả mãn là
1
1
i
n
C


với
1; 1i n  
.
Do vậy ta có
1
1 1
1 1 1
1
2 1
n
i n
n n n n
i
S S C S

 
  

    

Lại có
2
1S 
nên
2 1.
n
n
S n  
Ví dụ 3 . Cho tập
{1;2;...; }S n
với
n
là số nguyên lớn hơn 2. Tìm số tập con của
tập
S
sao cho trong mỗi tập con đều có ít nhất hai phần tử là hai số nguyên liên
tiếp.
Lời giải:
Gọi
n
S
là tập hợp các tập con khác

của tập
{1;2;...; }n
mà trong mỗi tập con
không có hai phần tử nào là hai số nguyên liên tiếp. Chia các phần tử của
n
S

thành hai nhóm:
. Nhóm không chứa phần tử

n
: Số các tập con như vậy là
1n
S

;
. Nhóm chứa phần tử

n
:
{ }n
hoặc
1 2
{ ; ;...; ; } (1 1)
k
a a a n k n  
Trang 2
Rõ ràng
1( 1,2,..., )
i
a n i k  
nên số các tập con như vậy là
2
1
n
S


Do vậy
1 2
1
n n n
S S S
 
  
Với chú ý
2 3
2, 4S S 
, ta có

2 2
1 1 5 1 5
1
2 2
5
n n
n
S
 
 
   
 
 
  
   
 
   
 
Mặt khác, số tập con khác

của tập
{1;2;...; }n
là
2 1
n

. Vậy số tập con thoả
mãn đề bài là

2 2
1 1 5 1 5
2
2 2
5
n n
n
 
 
   
 
 
 
   
 
   
 
Ví dụ 4 . Cho số nguyên
1n 
.
Tìm số các bộ số nguyên
 
1 2
, ,...,
n
a a a
thoả mãn
1
i
a 
với
1,2,...,i n 
và
1
1
i i
a a

 

1,2,..., 1.i n  

Lời giải:
.Trong tập
n
S
các bộ số nguyên thoả mãn bài toán, gọi
, ,
n n n
A B C
lần lượt là tập
hợp các bộ có
n
a
bằng
1,0,1
tương ứng. Ta có
n n n n
S A B C  
.
.Mặt khác, dễ thấy từ mỗi bộ thuộc
n
A
hoặc
n
B
, ta có thể bổ sung
1
1
n
a

 
để
được một bộ thuộc
1n
A

nên
1n n n
A A B

 
.
.Tương tự ta có
1n n n
C C B

 
và
1n n n n n
B A B C S

   
Từ đó ta có:

1 1 1 1n n n n
S A B C
   
  

 
1n n n n n
A B C B B

    

1
2
n n
S S

 
Kết hợp với
2 3
7, 17S S 
ta tính được
   
1 1
1 2 1 2
2
n n
n
S
 
  

.
Trang 3
Ví dụ 5 . Cho số nguyên dương
n
. Có bao nhiêu số tự nhiên có
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 cạnh nhau?
Lời giải:
Kí hiệu
n
X
là tập tất cả các số tự nhiên có
n
chữ số thoả mãn đề bài,
,
n n
A B
là
các tập con của
n
X
theo thứ tự gồm 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ó
n
X
=
,
n n n n n n n
A B A B X A B      
Lấy một phần tử của
1n
X

bỏ đi chữ số tận cùng ta được một phần tử của
n
X
.
Nếu chữ số tận cùng nhỏ hơn 7 (thuộc
n
A
) thì chỉ có 1 cách thêm vào chữ số cuối
để được 1 phần tử của
1n
A

và có đúng 3 cách thêm vào chữ số cuối để được 1
phần tử của
1n
B

.
Nếu chữ số tận cùng lớn hơn 6 (thuộc
n
B
) thì có 5 cách thêm vào chữ số cuối để
được 1 phần tử của
1n
A

và có đúng 3 cách thêm vào chữ số cuối để được 1 phần tử
của
1n
B

.
Từ các lập luận trên ta có:

1
1
5 (1)
3 3 (2)
n n n
n n n
A A B
B A B



 


 


Từ (1) và (2) suy ra
 
1 1
4 8 4 4
n n n n n n n
A B A B A B B
 
     

   
1 1
4 12 ( 2)
n n n n
A B A B n
 
    
Kí hiệu
n n
x X
, ta có
2 1
12 , *
n n n
x x x n
 
   �
. Từ đó ta có:

 
 
 
 
2 1 1
2 1 2 1
2 1 1
2 1 2 1
6 2 6
6 ( 2) 6
2 6 2
2 (6) 2
n
n n n n
n n
n
n n n n
n n
x x x x
x x x x
x x x x
x x x x
  
 
  
 


   
   
 

 
  
  





1 2 1 2 1
1
[( 2 ).6 ( 6 ).( 2) ]
8
n n
n
x x x x x

     
Dễ thấy
1
8x 
, ta tìm
2
x
. Xét
2
; , {2,3,4,5,6,7,8,9}u X u ab a b   
Trang 4
. Nếu
{2,3,4,5,6}a 
thì có 4 cách chọn
b
. Nếu
{7,8,9}a 
thì có 8 cách chọn
b
Vậy
2
5.4 3.8 44x   
. Do đó
1 1
1
[15.6 ( 2) ].
2
n n
n
x
 
  

Ví dụ 6 .(IMO 2011). Giả sử
0n 
là một số nguyên. Cho một cái cân đĩa và
n

quả cân có khối lượng lần lượt là
0 1 2 1
2 ,2 ,2 ,...,2 .
n
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 đặt ra?
Lời giải:
Gọi
n
s
là số cách để thực hiện việc đặt cân theo đúng mục đích đặt ra.
Xét cách đặt
1n 
quả cân có khối lượng
0 1 2
2 ,2 ,2 ,...,2 .
n
Do
0 1 2 1
2 2 2 ... 2 2 1 2
n n n
      
nên trong mọi cách đặt cân thoả mãn bài
toán thì quả cân có khối 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 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à
n
s
.
Nếu quả cân
2
n
được đặt ở bước thứ
( 1,2,..., )i i n
. Khi đó có
n
cách chọn
i

và trong trường hợp này quả cân
1
2
n
có 2 cách đặt ( đĩa bên phải hay bên trái đều
thoả mãn ), do đó số cách đặt
1n 
quả cân trong trường hợp này là
2 .
n
n s
. Vậy ta
có hệ thức truy hồi:
 
1
2 . 2 1
n n n n
s n s s n s

   
Ta có
1
1s 
nên
   
2 1 2 3 ...3.1.
n
s n n  
Ví dụ 7 .(VMO 2009). Cho số nguyên dương
n
. Kí hiệu T là tập hợp gồm
2n
số
nguyên dương đầu tiên. Hỏi có tất cả bao nhiêu tập con
S
của T có tính chất:
trong
S
không tồn tại các số
,a b
mà
{1; }?a b n 
Trang 5

Tài liệu liên quan

Tài liệu vừa đăng

Tài liệu xem nhiều nhất