44.Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có 3 bit 0

liên tiếp

Đặt Sn là số chuổi nhị phân độ dài n , có 3 bit 0 liên tiếp:

một chuổi dài n (n>3) sẽ có một trong các dạng sau:

A1 ( A chứa 3 bit 0 liên tục, số cách là S(n-1))

B10 (B chứa 3 bít 0 liên tục, số cách là S(n-2))

C100 (C chứa 3 bít 0 liên tục, số cách là S(n-3)

D000 (D tùy ý dài n-3, số cách 2^(n-3)

ta có công thức truy hồi: Sn=S(n-1)+S(n-2)+S(n-3)+2^(n-3)

khởi tạo: S1=S2=0; S3=1.

45. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n không

có 3 bit 0 liên tiếp.

Đặt Sn là số chuổi nhị phân độ dài n , ko có 3 bit 0 liên tiếp:

một chuổi dài n thõa mãn điều kiện sẽ có dạng: A1 B10 B100

trong đó A,B,C có độ dài n-1,n-2,n-3 và thỏa mãn ko có 3 bit ko liên tiếp.

nên ta có hệ thức:

Sn=Sn-1 + Sn-2 + Sn-3 ( khởi tạo: S1=2,S2=4,S3=7) 46. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có chứa

chuỗi con 01

Sn là số chuổi nhị phân có chứa chuổi con 01 (*)

thì số chuổi nhị phân ko chứa chuổi con 01 là 2^n-Sn. chuổi thỏa mãn (*) có 1 trong 2 dạng:

Ax (A thỏa mãn (*) , x = 0 hoặc 1 )

B01 (B kô thỏa mãn (*)) =>Sn=2 Sn-1 + (2^(n-2)-Sn-2)

Page 1

=>Sn=2 Sn-1 - Sn-2 + 2^(n-2)

(khởi tạo: S1=0;S2=1)

Thực ra Sn có thể tính dễ dàng ko truy hồi như sau:

chuổi ko thỏa mãn (*) chỉ có thể có dạng: 111...111000...000 số chuổi thế này = n+1 =>Sn=2^n-(n+1)

47.Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số cách đi lên n bậc thang nếu có

thể đi 1,2 hoặc 3 bước một lần.

muốn bước lên tới bậc n(n>3) có 3 cách:

bước tới bước n-1 rồi bước 1 bậc lên n

bước tới n-2 rồi bước 2 bậc tới n

bước tới n-3 rồi bước 3 bậc tới n

vậy ta xậy dựng được: Sn = Sn-1 + Sn-2 + Sn-3

khởi tạo: S1=1; S2=2; S3=3; /*-----------------------------------------------------------------------------------------------------------*/

48.Tìm hệ thức truy hồi và điều kiện khởi tạođể tính số chuỗi nhị phân độ dài n có một số

chẵn bit 0.

Sn _ số chuổi có số chẳng bit 0

Kn _ số chuổi có số lẽ bít 0 Sn+Kn=2^k

một chuổi dài n có chẳng bit ko đc thành lập bằng 2 cách

* số chẳn bít 0 dài n-1 thêm 1

* số lẽ bít 0 dài n-1 thêm 0

vậy Sn=S(n-1)+K(n-1)

tương tự ta có Kn=S(n-1)+K(n-1) =>Sn=Kn =>Sn=2S(n-1)

khởi tạo : S1=1 ( số 1 )

/*-----------------------------------------------------------------------------------------------------------*/

Page 2

49.Tìm hệ thức truy hồi mà Rn thoả mãn, trong đó Rn là số miền của mặt phẳng bị phân

chia bởi n đường thẳng nếu không có hai đường nào song song và không có 3 đường nào

cùng đi qua một điểm

trên mặt phẳng có n (với n>1) đường thẳng đôi một cắt nhau và ko có 3 đường đồng quy. ta

thấy rằng cứ mỗi đường thẳng bị n-1 đường còn lại chia làm n phần. bởi vậy nếu ta bỏ đi một

đường bất kì thì khi mất n phần này , 2 mặt miền 2 bên lập tức họp lại làm một, điều đó nghĩa

là nếu bỏ đi 1 đường thẳng thì số miền bị mất đi là n:

tức là Rn=n+R(n-1), R1=2.

=> công thức Rn=n(n+1)/2+1 /*-----------------------------------------------------------------------------------------------------------*/

50.Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi ký tự gồm A,B,C có độ dài

n chứa hai kí tự liên tiếp giống nhau.

Gọi Sn là số chuổi thỏa mãn : có chưa 2 kí tự liên tiếp giống nhau (▲)

thì số chuổi ko thỏa mãn (▲) là 3^n-Sn

chuổi thỏa mãn có 1 trong 2 dạng:

* Mx ( M thỏa (▲), x có 3 cách)

* Nxx (Nx ko thỏa (▲)) => Sn=3 Sn-1 + (3^(n-1) - Sn-1) = 2 Sn-1 +3^(n-1)

khởi tạo: S1=0, S2=3

có thể giải ko truy hồi như sau:

đầu tiên tìm số chuổi ko có 2 kí tự liên tiếp bằng nhau:

chọn kí tự đầu tiên có 3 cách, kí tự tiếp theo có 2 cách ( trừ kí tự trước nó )

vậy tất cả có : 3.2^(n-1) cách => Sn=3^n-3.2^(n-1) /*-----------------------------------------------------------------------------------------------------------*/

51.Có bao nhiêu byte có 3 bit 0 liên tục.

1 byte co 8 bit

vay 3 bit liên tục vậy 8 vị trí coi còn 6 vị trí vậy có 6! Cách sắp xếp

/*-----------------------------------------------------------------------------------------------------------*/

52.Cho dãy S={Sn}, Sn là số chuỗi n bit không chứa mẫu 00.

a)Tìm hệ thức truy hồi và các điều kiện khởi tạo cho dãy {Sn}

Page 3

b)Chứng tỏ Sn=f(n+1), n=1,2,... với f là dãy Fibonacci.

a)

chuổi dài n thỏa mãn ko chứa 00 thì có một trong 2 dạng

* A1 ( A ko chứa mẫu 00)

* B10 ( B ko chứa mẩu 00)

vậy Sn=S(n-1)+S(n-2) S1=2 (0;1) , S2=3 (01;10;11)

b)

quy nạp:

S1=f(2); S2=f(3) đúng.

giả sử đúng đến n-1 tức là Sk=f(k+1), mọi k=1..n-1 =>Sn=S(n-1)+S(n-2)=f(n)+f(n-1)=f(n+1)

vậy Sn=f(n+1) mọi n=1,2,3,.. /*-----------------------------------------------------------------------------------------------------------*/

53.Tìm hệ thức truy hồi và điều kiện khởi tạo cho số cách đóng cặp ngoặc đơn trong biểu

thức a1*a2*...*an,n>=2.

# nếu chỉ có một thì một cách đóng cho biểu thức dài n = a1*a2*...*an

gọi công thức tính sô cách đóng cặp ngoặc là Sn

n>2: một cách đóng sẽ có 1 trong 2 dạng

* Aan, với cặp ngoặc trong A, A dài n-1, S(n-1) cách

* Aan), dấu mở ngoặc ở A , n-1 cách. => Sn=S(n-1)+n-1 S2=1; s3=3 s4=3+3=6

vậy Sn=(n-1)+(n-2)+..+3+2+1=n(n-1)/2

(hoặc một cách đống ngoặc chính là một tổ hợp chập 2 của n phần tử, đáp sô là nC2=n(n-1)/2)

/*-----------------------------------------------------------------------------------------------------------*/

54.Gọi a(n) là số các chữ số 0 có trong các số tự nhiên từ 0 đến (10^n)-1.

a)Chứng tỏ rằng a(n) thoả mãn hệ thức truy hồi a(n)=a(n-1)+9*(n-1)*10^(n-2)

b)Biết giá trị đầu a(1)=1, giải hệ thức truy hồi trên. a)

Gọi Kn (n>0) là số các chử số 0 có trong các số tự nhiên từ 10^(n-1) đến 10^n-1 ( tức có đúng

Page 4

n chử số, chử số đầu tiên bên trái khác 0 )

ta sẽ đi chứng minh Kn=9(n-1).10^(n-2)

một số có n chử số sẽ có dạng Ax, trong đó A có n-1 chử số và x=0..9

Kn là số các số 0 trong các số dạng Ax

số các số 0 trong Ax bằng 10 lần số các số 0 trong A cộng thêm các số 0 trong x.

số các số 0 trong A thì bằng 10 lần số các số K_(n-1) ( vì Ax, x có 10 cách chọn)

số các số 0 ở dạng A0 thì bằng số các số dạng A, số đầu khác 0 nên số cách chọn là 9.10^(n-2)

vậy rốt cuộc ta có công thức:

Kn = 10.K_(n-1)+9.10^(n-2), từ đây dễ dàng quy nạp được Kn = 9(n-1).10^(n-2) ( vì 10.9(n- 2).10^(n-3) + 9.10^(n-2) = 9(n-1).10^(n-3) )

Mặt khác An=A_(n-1)+Kn ( chia từ 1 đến 10^n-1 thành 2 đoạn, từ 1 đến 10^(n-1)-1 và 10^(n-

1) đến 10^n-1. )

vậy ta có hệ thức truy hồi: An=A_(n-1) + 9(n-1).10^(n-2)

b) ta cói: An=9(n-1).10^(n-2) + 9(n-2).10^(n-3) +...+ 9.1.10^0+A0 ( A0=1 )

x^n-1=(x-1) (x^(n-1) + x^(n-2) +...+ x^2 + x + 1) (x^n-1)/(x-1)=(x^(n-1) + x^(n-2) +...+ x^2 + x + 1)

đạo hàm 2 vế

(n.x^(n-1).(x-1)-(x^n-1))/(x-1)^2=(n-1... + (n-2).x^(n-3) +...+ 2x + 1 thay x=10 ta có: (n.10^(n-1).9-(10^n-1))/9^2 = (n-1).10^(n-2) + (n-2).10^(n-3) +..+ 2.10 + 1 => An = (n.10^(n-1).9-(10^n-1))/9+1 = n.10^(n-1) - (10^n-1)/9 + 1 /*-----------------------------------------------------------------------------------------------------------*/

55.Gọi an là số dãy bit đọ dài n không có 2 bit 0 kề nhau.

a)Tìm hệ thức truy hồi cho an

b)Biết giá trị đầu a1=2,a2=3, giải hệ thức truy hồi trên.

một dãy độ dài n ko có 2 bit 0 kề nhau thì có 1 trong 2 dạng

* A10 ( A có n-2 bit và ko có 2 bit 0 kề nhau )

* B1 ( B có n-1 bít và ko có 2 bit 0 kề nhau )

vậy suy ra an=a(n-1)+a(n-2) a1=2; a2=3

dãy này bắt đầu từ a1=2 là dãy fibonaci

Page 5

giải truy hồi bằng cách xét nghiệm của phương trình đặc trưng x^2=x+1

x1=(1+√5)/2 ; x2=(1-√5)/2 an=c1.x1^n+c2.x2^n thay n=1,2 vào tìm c1,c2 /*-----------------------------------------------------------------------------------------------------------*/

56.Gọi an là số dãy bit độ dài n có 2 bit 0 kề nhau.

a)Tìm hệ thức truy hồi cho an

b)Biết giá trị đầu a0=0 và a1=0, tính số dãy bit độ dài 7 có 2 bit 0 kề nhau.

a)

một số có 2 bít 0 kề nhau thì có 1 trong 3 dạng

* A00 (A bất kì dài n-2 , số trường hợp là 2^(n-2))

* B10 (B chứa 2 bít 0 liền nhau dài n-2 , số trường hợp là a(n-2))

* C1 (C chứa 2 bít 0 liền nhau dài n-1, số trường hợp là a(n-1))

vậy an=a(n-1)+a(n-2)+2^(n-2)

b) a0=0,a1=0 =>a2=0+0+2^0=1 =>a3=1+0+2^1=3 =>a4=3+1+2^2=8 =>a5=8+3+2^3=19 =>a6=19+8+2^4=43 =>a7=43+19+2^5=94

/*-----------------------------------------------------------------------------------------------------------*/

1.Trong mặt phẳng Oxy lấy ngẫu nhiên 5 điểm tọa độ nguyên. Chứng tỏ rằng có ít nhất một

trung điểm của các đoạn nối chúng có tọa độ nguyên.

5 điểm nên có ít nhất 3 điểm có tung độ cùng tính chất chẳn lẻ ( chia 2 nhóm: tung độ chẳn và

lẽ, có ít nhất 1 nhóm chứa không ít hơn 3 điểm, 3 điểm đó thỏa mãn )

trong 3 điểm đó có ít nhất 2 điểm có hoành độ cùng tính chất chẳn lẽ.

vậy ta có 2 điểm mà tung độ và hoành độ cùng tính chất chẳn lẽ, trung điểm 2 điểm này tất

nhiên có tọa độ nguyên!

Page 6

/*-----------------------------------------------------------------------------------------------------------*/

2.Trong mặt phẳng cho 6 điểm phân biệt nối nhau từng đôi một bởi các đoạn thẳng màu xanh

hoặc đỏ. Chứng tỏ rằng có 3 điểm nối nhau bởi các đoạn thẳng cùng màu.

xét 1 điểm A bất kì trong 6 điểm, từ điểm này có 5 đoạn thẳng , nên phải có ít nhất 3 đoạn

thẳng cùng màu AB,AC,AD. giả sử 3 đoạn này có màu đỏ chẳng hạn.

khi đó

*nếu 1 trong 3 đoạn BC,CD,DB có màu đỏ thì ta có tam giác cùng màu đỏ ( với 2 trong 3 đoạn kia)

*nếu cả 3 đoạn BC,CD,DB đều xanh thì ta có tam giác màu xanh

/*-----------------------------------------------------------------------------------------------------------*/

3.Trong mặt phẳng cho 17 điểm phân biệt nối nhau từng đôi một bởi các đoạn thẳng màu

xanh, hoặc đỏ, hoặc vàng.Chứng tỏ rằng có 3 điểm nối nhau bởi các đoạn thẳng cùng màu.

lấy 1 điểm A từ 17 điểm, từ A có 16 đoạn thẳng tô bằng 3 màu nên có ít nhất 6 đoạn cùng

màu. giả sử màu đỏ. 6 điểm ở đầu kia nếu có 2 điểm nối bằng màu đỏ nữa thì rỏ ràng tạo

thành tam giác màu đỏ. còn không thì 6 điểm này được nối với nhau bằng 2 màu còn lại ( xanh,

vàng ) theo bài 2 thì tồn tại 3 điểm nối với nhau cùng màu. vậy bài 3 được chứng minh /*-----------------------------------------------------------------------------------------------------------*/

4.Một thùng chứa 10 quả bóng màu xanh và 10 quả bóng màu đỏ. Phải lấy ngẫu nhiên ít nhất

bao nhiêu quả bóng để bảo đảm có 3 quả bóng cùng màu.đáp số: 5 quả.

chứng minh: nếu lấy 5 quả thì tồn tại 3 quả cùng màu tất nhiên

nếu lấy 4 quả thì trường hợp 2 xanh 2 đỏ không thỏa mãn, vậy phải lấy ít nhất 5 quả, lấy

quả không thoai

5.Cho X={0..10}. Chứng tỏ rằng nếu S là một tập con gồm 7 phần tử của X thì có 2

phần tử của S có tổng bằng 10.

chia {0..10} thành 6 tập {0,10} {1,9} {2,8} {3,7} {4,6} {5}

vậy nếu lấy 7 phần tử thì có ít nhất 1 tập đc lấy cả 2 phần tử

vì nếu mỗi tập lấy ko quá 1 thì tất cả không quá 6 phần tử (

Page 7

2 phần tử cùng tập này rỏ ràng có tổng = 10

/*-----------------------------------------------------------------------------------------------------------*/

6.Một bữa tiệc có ít nhất hai người. Chứng minh rằng có ít nhất 2 người có cùng số

người quen.

giả sử có n người (n>=2)

*nếu có người ko quen ai, thì ko thể có người quen n-1 người quen

do vậy số người quen từ 0 đến n-2 có n-1 số mà có n người vậy có 2 người cùng số người quen

*nếu ko có ai ko quen ai cả: thì số người quen chỉ có thể từ 1 đến n-1

tương tự, có n-1 số mà có n người vậy có 2 người cùng số người quen.

/*-----------------------------------------------------------------------------------------------------------*/

7.Xét một trận đấu n người, mỗi người đấu với mỗi người khác và mỗi người thắng ít nhất

một lần. Chứng tỏ rằng có ít nhất 2 người có cùng số lần thắng.

tương tự bài trên số trận thắng chỉ có thể từ 1 đến n-1 , mà có n người thi đấu, nên có 2

người có cùng số trận thắng như nhau

/*-----------------------------------------------------------------------------------------------------------*/

8.Nếu 10 điểm được chọn ngẫu nhiên bên trong một tam giác đều có độ dài cạnh 3 đơn vị,

chứng tỏ rằng có ít nhất 1 cặp điểm bên trong đường tròn đơn vị.

chia tam giác làm 9 phần bằng các đoạn thẳng song song và cách các cạnh 1 và 2

các tam giác như vậy có cạnh bằng 1

có 10 điểm nên có ít nhất 2 điểm thuộc 1 tam giác nào đó, tất nhiên khoảng cách của chúng bé

hơn 1

( chú ý rằng khoảng cách 2 điểm trong tam giác bé hơn hoặc bằng max{3 cạnh} )

Page 8

/*-----------------------------------------------------------------------------------------------------------*/

12.Chứng tỏ rằng số hữu tỉ là một số thập phân vô hạn tuần hoàn.

số hữu tỉ thì hửu hạn hoặc vô hạn tuần hoàn

xét trường hợp vô hạn, dương ( số âm có dạng tương tự ) : m/n=x+m'/n (m'

ta xét phép chia. m' chia cho n cần thêm số 0 ở sau. chia được số dư, thêm 0 chia tiếp ... nhận

thấy rằng số các số dư là hửu hạn (1->n-1, bằng 0 là chia hết , dừng)

nên sau n bước ít nhất phép chia lặp lại và ta có số thập phân vô hạn tuần hoàn chu kì không quá n.

/*-----------------------------------------------------------------------------------------------------------*/

13.Chứng tỏ rằng trong n+1 số nguyên có ít nhất hai số đồng dư n.

có n+1 số trong khi chỉ có n số dư từ 0 đến n-1 nên có 2 số có số dư bằng nhau ( đồng dư )

/*-----------------------------------------------------------------------------------------------------------*/

14.Cần ít nhất bao nhiêu cặp số nguyên (a,b) để chắc chắn có hai cặp (a1,b1) và (a2,b2) mà a1=a2(mod5) và b1=b2(mod5).

ít nhất 26 cặp.

thật vậy 25 cặp sau (a,b), a=0..4,b=0..4 không có 2 cặp nào mà a1=a2,a1=b2(mod5) vì nếu vậy

thì a1=a2,b1=b2 (đồng dư mà =0..4 thì bằng nhau )=> mâu thuẩn

giờ chứng minh nếu 26 cặp thì thỏa mãn:

xếp 26 cặp này vào 25 nhóm mà khi chia cho 5 các phần tử có số dư là (a,b), a,b=0..4 thì có ít

nhất 2 cặp cùng nhóm, 2 cặp này tất nhiên thỏa mãn.

/*-----------------------------------------------------------------------------------------------------------*/

16.Chứng tỏ rằng trong dãy n số nguyên thì có một hay nhiều số liên tiếp có tổng chia hết n.

xét n tổng a1+a2+a3+...+an a1+a2+..+a(n-1) ... a1+a2 a1

có ít nhất 2 tổng cùng số dư khi chia cho n

hiệu của chúng chia hết cho n

hiệu đó là tổng của các số liên tiếp

Page 9

/*-----------------------------------------------------------------------------------------------------------*/

17.Có bao nhiêu cách sắp n người ngồi vào bàn tròn xoay.

nếu chỉ tính vị trí tương đối giửa các người thì cố định người thứ nhất, và có (n-1)! các sắp xếp

các người còn lại

đáp số: (n-1)!