Tóm tắt luận văn thạc sĩ khoa học: Bài toán đếm nâng cao trong tổ hợp và ứng dụng

Chia sẻ: Lang Nguyen | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

413
lượt xem 72
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt luận văn thạc sĩ khoa học: Bài toán đếm nâng cao trong tổ hợp và ứng dụng nhằm nghiên cứu về các cầu hình tổ hợp từ cơ bản đến nâng cao, nguyên lý bù trừ, lý thuyết hàm sinh, công thức truy hồi...từ đó đưa ra được hệ thống các phương pháp và ứng dụng điển hình của bài toán đếm nâng cao trong tổ hợp.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận văn thạc sĩ khoa học: Bài toán đếm nâng cao trong tổ hợp và ứng dụng

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG TRƯƠNG NH T LÝ BÀI TOÁN Đ M NÂNG CAO TRONG T H P VÀ NG D NG Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ C P Mã s : 60.46.40 TÓM T T LU N VĂN TH C SĨ KHOA H C Đà N ng – Năm 2011
2 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TSKH. TR N QU C CHI N Ph n bi n 1: Ph n bi n 2: Lu n văn ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p Th c sĩ Khoa h c, h p t i Đ i h c Đà N ng vào 22 ngày tháng 10 năm 2011 Có th tìm hi u lu n văn t i: - Trung tâm Thông tin – H c li u, Đ i h c Đà N ng - Thư vi n trư ng Đ i h c Sư ph m, Đ i h c Đà N ng
3 M Đ U 1. LÝ DO CH N Đ TÀI T h p có v trí ñ c bi t trong toán h c không ch như là nh ng ñ i tư ng ñ nghiên c u mà còn ñóng vai trò như m t công c ñ c l c c a các mô hình r i r c c a gi i tích, ñ i s , ... Các bài toán t h p ngày càng chi m m t v trí quan tr ng trong các kỳ thi olympic, vô ñ ch toán ... Toán t h p là m t d ng toán khó, ñòi h i tư duy lôgic, tư duy thu t toán cao, tính hình tư ng t t, phù h p v i m c ñích tuy n ch n h c sinh có kh năng và năng khi u toán h c. Hơn n a, n i dung các bài toán ki u này ngày càng g n v i th c t cu c s ng chúng ta, và ñi u ñó hoàn toàn phù h p v i xu hư ng c a toán h c hi n ñ i. Chính vì nh ng lý do trên, chúng tôi ñã nghiên c u và ch n ñ tài “Bài toán ñ m nâng cao trong t h p và ng d ng” nh m h th ng các phương pháp gi i ñ ng th i nâng cao hơn n a nh n th c và ng d ng c a nó trong h c t p, nghiên c u và công tác sau này. 2. M C ĐÍCH NGHIÊN C U Nghiên c u lý thuy t v lý thuy t t h p và t ñó nh m h th ng các phương pháp gi i bài toán ñ m và ng d ng c a nó vào nghiên c u, h c t p cũng như trong th c ti n. Đ tài cũng ñư c làm tài li u tham kh o cho h c sinh, sinh viên ñ i h c và cao ñ ng, h c viên cao h c, thi h c sinh gi i c p qu c gia, qu c t và nh ng ai quan tâm ñ n lý thuy t t h p. 3. NHI M V NGHIÊN C U Nhi m v c a ñ tài này là nghiên c u v các c u hình t h p t cơ b n ñ n nâng cao, nguyên lý bù tr , lý thuy t v hàm sinh, công th c truy h i... T ñó ñưa ra ñư c h th ng các phương pháp và ng d ng ñi n hình c a bài toán ñ m nâng cao trong t h p. 4. Đ I TƯ NG VÀ PH M VI NGHIÊN C U • Lý thuy t v các c u hình t h p cơ b n và m r ng và các ki n th c liên quan ñ n bài toán ñ m. • Phương pháp gi i bài toán ñ m và các bài toán áp d ng. • ng d ng c a bài toán ñ m t h p. 5. PHƯƠNG PHÁP NGHIÊN C U S d ng phương pháp nghiên c u tài li u liên quan ñ n lu n văn ñ thu th p thông tin, t ñó phân tích, h th ng và phân lo i các phương pháp gi i cũng như m t s ng d ng ñi n hình liên quan ñ n bài toán ñ m trong t h p.
4 6. Ý NGHĨA KHOA H C VÀ TH C TI N C A Đ TÀI Đ tài h th ng ki n th c v các nguyên lý ñ m, các c u hình t h p, lý thuy t hàm sinh, h th c truy h i và các ki n th c liên quan ñ n bài toán ñ m t h p. T ñó hình thành các phương pháp t cơ b n ñ n nâng cao và m t s ng d ng liên quan ñ n bài toán ñ m. Qua ñó b sung thêm cho các em h c sinh, sinh viên v các phương pháp gi i các bài toán ñ m t h p t cơ b n ñ n khó và r t khó, ñ c bi t là trư c các kì thi h c sinh gi i t c p t nh, c p qu c gia ñ n thi Olympic qu c t và các kỳ thi khác. Đ tài còn có th làm ngu n tham kh o cho nh ng ai quan tâm ñ n lý thuy t t h p mà c th là phương pháp gi i và ng d ng c a bài toán ñ m t h p. 7. C U TRÚC C A LU N VĂN Lu n văn ñư c c u trúc b i 3 chương: Chương 1: T ng quan v t h p Chương 2: M t s phương pháp ñ m nâng cao Chương 3: M t s ng d ng Chương 1 T NG QUAN V T H P 1.1. SƠ LƯ C V L CH S T H P Có th nói tư duy t h p ra ñ i r t s m. Vào th i nhà Chu Trung Qu c ngư i ta ñã bi t ñ n nh ng hình vuông th n bí. Th i c Hi l p, th k th 4 trư c Công nguyên, nhà tri t h c Kxenokrat ñã bi t cách tính s các t khác nhau l p t b ng ch cái cho trư c. Tuy nhiên có th nói r ng, lý thuy t t h p ñư c hình thành như m t ngành toán h c m i vào th k 17 b ng m t lo t công trình nghiên c u c a các nhà toán h c xu t s c như Pascal, Fermat, Euler, Leibnitz … Các bài toán t h p có ñ c trưng bùng n t h p v i s c u hình t h p kh ng l . Vì v y trong th i gian dài, khi mà các ngành toán h c như Phép tính vi phân, Phép tính tích phân, phương trình vi phân… phát tri n như vũ bão, thì dư ng như nó n m ngoài s phát tri n và ng d ng c a toán h c. Tình th thay ñ i t khi xu t hi n máy tính và s phát tri n c a toán h c h u h n. Nhi u v n ñ t h p ñã ñư c gi i quy t trên máy tính và phát tri n r t m nh m . 1.2. CÁC D NG BÀI TOÁN T H P D ng 1: Bài toán t n t i D ng 2: Bài toán ñ m D ng 3: Bài toán li t kê D ng 4: Bài toán t i ưu t h p
5 1.3. CÁC C U HÌNH T H P CƠ B N VÀ M R NG 1.3.1. Hai nguyên lý ñ m cơ b n 1.3.1.1. Nguyên lý c ng 1.3.1.2. Nguyên lý nhân 1.3.2. Các c u hình t h p 1.3.2.1. Hoán v không l p 1.3.2.2. Hoán v l p 1.3.2.3. Ch nh h p không l p 1.3.2.4. Ch nh h p l p Đ nh nghĩa 1.4: Ch nh h p l p ch p k c a n ph n t khác nhau là m t b có th t g m k thành ph n l y t n ph n t ñã cho, các ph n t có th ñư c l p l i. Đ nh lí 1.2: S lư ng các ch nh h p l p ch p k c a n ph n t ñư c kí hi u và xác ñ nh b i công th c sau: A k = AR(n, k) = nk. n 1.3.2.5. T h p không l p 1.3.2.6. T h p l p Đ nh nghĩa 1.6: T h p l p ch p k c a n ph n t khác nhau là m t nhóm không phân bi t th t g m k ph n t trích t n ph n t ñã cho, trong ñó các ph n t có th ñ c l p l i. Đ nh lý 1.3: Gi s X có n ph n t khác nhau. Khi ñó s t h p l p ch p k c a n ph n t c a X, ñư c ký hi u và xác ñ nh b i công th c sau: CR(n, k) = C(k + n - 1, n - 1) = C(k + n - 1, k). Ví d 1.56. B t phương trình x1 + x2 + x3 ≤ 11 (1) có m y nghi m nguyên không âm ? L i gi i: S nghi m c a b t phương trình (1) chính b ng s nghi m nguyên c a phương trình: x1 + x2 + x3 + x4 = 11 v i x i ≥ 0, i = 1, 2, 3, 4. M i nghi m c a phương trình ng v i m t cách ch n 11 ph n t t m t t p có 4 lo i, sao cho có x1 ph n t lo i 1, x2 ph n t lo i 2, x3 ph n t lo i 3, x4 ph n t lo i 4 ñư c ch n. Vì v y s nghi m b ng s t h p l p ch p 11 t t p có 4 ph n t . Theo ñ nh lý 1.3 s ñó b ng: C(4 + 11 - 1, 11) = C(14, 11) = 364. 1.3.3. Phân ho ch th t t h p và phân ho ch không th t 1.3.3.1. Phân ho ch th t t h p Đ nh nghĩa 1.7: Cho X là t p g m n ph n t khác nhau, r ≤ n và S ⊂ X có r ph n t . M t phân ho ch {S1, S2 , ..., Sk } có th t c a S g i là m t phân ho ch th t t h p ch p r c a X. N u r = n thì g i là phân ho ch th t c a X. Cho các s nguyên dương n1, n 2 , ..., n k th a n1 + n 2 + ... + n k = r. S các phân ho ch th t t h p ch p r c a X d ng {S1, S2 , ..., Sk } có
6 S1 = n1, S2 = n 2 , ..., Sk = n k , ñư c kí hi u là C(n; n1,n 2 , ...,n k ) . M t c u hình t h p ki u này ñư c xây d ng qua các bư c như sau: Bư c 1: Ch n n1 ph n t t X cho S1 , có C( n, n1 ) kh năng. Bư c 2: Ch n n 2 ph n t t X\S1 cho S2 , có C( n − n1,n 2 ) kh năng. … Bư c k: Ch n n k ph n t t X\ (S1 ∪ S2 ∪ ... ∪ Sk −1 ) cho Sk , có C( n − n1 − n 2 − ... − n k −1, n k ) kh năng. Theo nguyên lý nhân suy ra: C(n; n1,n 2 , ...,n k ) = C( n,n1 ).C( n − n1,n 2 )..…C( n − n1 − n 2 − ... − n k −1, n k ) n! = = P(n; n1 , n 2 , ..., n k ,n − r). n1 !n 2 !.....n k !(n − r)! V y ta có ñ nh lí sau: Đ nh lý 1.4: S lư ng các phân ho ch th t t h p ch p r c a X có n ph n t b ng n! C(n;n1,n 2 ,..., n k ) = = P(n;n1 , n 2 ,...n k ,n − r); C(n;n1,n 2 ,..., n k ) n1 !n 2 !...n k !(n − r)! ñư c g i là h s ña th c. Ví d 1.57. 17 sinh viên ñi d h i b ng 5 xe khác nhau theo th t có s ch ng i tương ng là 4, 3, 3, 4, 1. Hãy xác ñ nh s cách ch 17 sinh viên b ng 5 xe, trong ñó có 2 sinh viên ph i ñi b ng phương ti n khác. L i gi i: M i cách ch là m t phân ho ch th t t h p ch p 15 c a 17 v i s ph n t trong m i t p con tương ng là 4, 3, 3, 4, 1. Vì v y s cách ch là: 17! C(17;4,3,3, 4,1) = = 8576568000. 4!3!3!4!1! 1.3.3.2. Phân ho ch không th t Đ nh nghĩa 1.8: Cho X là t p g m n ph n t khác nhau, các s nguyên dương n1,n 2 ,..., n k và p1, p 2 ,..., p k th a n1p1 + n 2 p 2 + ... + n k p k = n. M t h th ng các t p con c a X v i p1 t p l c lư ng n1 , p 2 t p l c lư ng n 2 , …, p k t p l c lư ng n k g i là phân ho ch không th t c a X. Đ nh lý 1.5: S phân ho ch không th t c a X v i p1 t p l c lư ng n1 , p 2 t p l c lư ng n 2 , …, p k t p l c lư ng n k là: C(n; n1, ..., n1, n 2 , ..., n 2 , ..., n k , ..., n k ) n! = p1 !p 2 !...p k ! p1 !(n1 !) p1 p 2 !(n 2 !)p2 ... p k !(n k !) pk Trong t s C(n; n1, ..., n1, n 2 , ..., n 2 , ..., n k , ..., n k ) s n1 l p l i p1 l n, n 2 l p l i p 2 l n, …, n k l p l i p k l n. Ví d 1.60. Phân ph i n qu c u phân bi t vào m h p phân bi t sao cho: H p 1 ch a n1 v t, h p 2 ch a n 2 v t, …, h p m ch a n m v t: n1 + n 2 + ... + n m = n
7 H i có bao nhiêu cách phân ph i khác nhau, không k th t c u trong m i h p. L i gi i: Có th phân ph i b ng m bư c như sau: Bư c 1: Ch n n1 ph n t t n c u cho h p 1, có C( n,n1 ) cách Bư c 2: Ch n n 2 ph n t t n - n1 cho h p 2, có C( n − n1,n 2 ) cách … Bư c m: Ch n n m ph n t t n − n1 − n 2 − ... − n m−1 cho h p m, có C( n − n1 − n 2 − ... − n m−1, n m ) kh năng. Theo nguyên lý nhân suy ra s cách phân ph i là: n! C( n,n1 ) .C( n − n1,n 2 ) .C( n − n1 − n 2 − ... − n m−1, n m ) = . n1 !n 2 !...n m ! Chương 2 M TS PHƯƠNG PHÁP Đ M NÂNG CAO 2.1. NGUYÊN LÝ BÙ TR V i n t p h u h n A1, A2, ..., An ta có ñ nh lý t ng quát sau: Đ nh lý 2.1: V i n t p h p A1, ..., An b t kỳ ta có công th c n |A1∪ ... ∪ An| = ∑ Ai - ∑ | A i ∩ A j | + ...+ (-1)n-1|A1∩A2∩...∩An| (1) i=1 1≤i< j≤n Hay ta có th phát bi u cách khác như sau: | A1 ∪ A2 ∪ ... ∪ An| = N1 − N2 + N3 − ... + (−1)n-1Nn trong ñó Nm (1 ≤ m ≤ n) là t ng ph n t c a t t c các giao m t p l y t n t p ñã cho, nghĩa là: Nm = ∑ | Ai1 ∩ Ai2 ∩ ... ∩ Aim | 1≤i1
8 8! 8! 8! 1 1 1 8! – ( 8!− + − ... − ) = 8! ( − + ... + ) 2! 3! 8! 2! 3! 8! Ví d 2.8. Trong t p S = {1, 2, ..., 280} có m y s không chia h t cho 2, 3, 5, 7. L i gi i: Ta ñ m xem trong t p S có bao nhiêu s chia h t cho ít nh t m t trong các s 2, 3, 5, 7. Kí hi u A1 = {k ∈ S: k chia h t cho 2}, A2 = {k ∈ S: k chia h t cho 3}, A3 = {k ∈ S: k chia h t cho 5}, A4 = {k ∈ S: k chia h t cho 7}. Khi ñó A1 ∪ A 2 ∪ A3 ∪ A 4 là t p các s chia h t cho ít nh t m t trong các s 2, 3, 5, 7.  280   280   280   280  Ta có: | A1 |=  = 140; | A 2 |=  = 93; | A3 |=  = 56; | A 4 |=  = 40 ;  2    3    5    7    280   280   280  | A1 ∩ A 2 |=  = 46; | A1 ∩ A3 |=  = 28; | A1 ∩ A 4 |=  = 20;  2.3    2.5    2.7    280   280   280  | A 2 ∩ A 3 |=  = 18; | A 2 ∩ A 4 |=  = 13; | A3 ∩ A 4 |=  = 8;  15   21    35   280   280  | A1 ∩ A 2 ∩ A3 |=  = 9; | A1 ∩ A 2 ∩ A 4 |=  = 6;  30    42   280   280  | A1 ∩ A3 ∩ A 4 |=   = 4; | A 2 ∩ A 3 ∩ A 4 |=  105  = 2;  70     280  | A1 ∩ A 2 ∩ A3 ∩ A 4 |=  = 1.  210   Do ñó theo nguyên lý bù tr ta có | A1 ∪ A 2 ∪ A3 ∪ A 4 | = 216. V y trong t p S có 280 – 216 = 64 s không chia h t cho 2, 3, 5, 7. 2.2. PHƯƠNG PHÁP SONG ÁNH 2.2.1. Đ nh nghĩa 2.1 Cho ánh x f: A → B. • Ánh x f ñư c g i là m t ñơn ánh n u v i hai ph n t b t kì a1, a2 ∈ A mà a1 ≠ a2 thì f(a1) ≠ f(a2), t c là f(a1) = f(a2) ⇔ a1 = a2. • Ánh x f ñư c g i là m t toàn ánh n u v i m i b∈ B ñ u t n t i a ∈ A ñ cho f(a) = b. • Ánh x f ñư c g i là m t song ánh (tương ng 1-1) n u v i m i b∈ B, t n t i và duy nh t a∈ A ñ f(a) = b. Nói cách khác f là song ánh khi và ch khi nó v a là ñơn ánh v a là toàn ánh. 2.2.2. Đ nh lý 2.2 Cho A và B là hai t p h u h n. Khi ñó: • N u có m t ñơn ánh f: A → B thì |A| ≤ |B|. • N u có m t toàn ánh f: A → B thì |A| ≥ |B|. • N u có m t song ánh f: A → B thì |A| = |B|.
9 Phương pháp song ánh d a vào m t ý tư ng r t ñơn gi n: N u t n t i m t song ánh t A vào B thì |A| = |B|. Do ñó, mu n ch ng minh hai t p h p có cùng s ph n t , ch c n xây d ng m t song ánh gi a chúng. Hơn n a, ta có th ñ m ñư c s ph n t c a m t t p h p A (kí hi u |A|), ta có th xây d ng song ánh t A vào m t t p h p B mà ta ñã bi t cách ñ m s ph n t . B i B có cùng s ph n t v i A nhưng có c u trúc ñư c mô t khác A nên ta có th ñ m ñư c s ph n t c a B d dàng hơn vi c ñ m s ph n t c a A. Ví d 2.14 (APMO 1998). Gi s Fk là t p h p t t c các b (A1, A2, ..., Ak), trong ñó Ai (i = 1, 2, ..., k) là m t t p con c a t p E = {1, 2, ..., 1998}. Kí hi u |A| là s ph n t c a t p A. Hãy tính: Sk = ∑ | A1 ∪ A 2 ∪ ... ∪ A k | (1) (A1 ,A 2 ,...,A k )∈Fk L i gi i: L i gi i th nh t ta có th dùng phương pháp quy n p khá t nhiên v m t ý tư ng, tuy r t c ng k nh và ñòi h i nhi u kĩ năng tính toán. L i gi i th hai cũng tính Sk thông qua vi c tính T(i, k) là s các b : (A1, A2, ..., Ak) ∈ F, sao cho A1 ∪ A 2 ∪ ... ∪ A k = i tuy nhiên v i m t cách nhìn khác như sau: V i i ph n t n1, n2, ..., ni thu c {1, 2, ..., n} ta ñ m xem có bao nhiêu b (A1, A2, ..., Ak) th a mãn ñi u ki n A1 ∪ A 2 ∪ ... ∪ A k = {n1, n2, ..., ni} (2), t ñó tính ñư c T(i, k) và Sk. Ta cho các ph n t n1, n2, ..., ni “ñăng ký” có m t trong các t p h p Ai theo qui t c: n u, ch ng h n n1 ñăng kí có m t trong A1, A2 và không có m t trong các t p còn l i thì phi u ñăng kí c a n1 ñư c ghi là (1, 1, 0, 0, ..., 0), còn n u n1 ch có m t trong Ak thì ghi phi u là (0, 0, ..., 1). Phi u ñăng kí là h p l n u có ít nh t m t s 1 (n u không, ph n t tương ng s không có m t trong A1 ∪ A 2 ∪ ... ∪ A k ). V i i phi u ñăng kí c a n1, n2, ..., ni ta l p ñư c 1 b (A1, A2, ..., Ak). D th y r ng v i hai b phi u ñăng kí khác nhau, ta có hai b t p h p (A1, A2, ..., Ak) khác nhau và như v y s b (A1, A2, ..., Ak) th a mãn (2) b ng s b phi u ñăng kí h p l . Vì phi u ñăng kí c a np, p = 1, 2, ..., i g m k s 0 ho c 1 và ph i có ít nh t m t s 1 nên np có 2k – 1 cách ghi phi u ñăng kí (do tr ra xâu (0, 0, ..., 0) và như v y theo nguyên lý nhân có t t c (2k – 1)i b phi u ñăng kí h p l khác nhau. Cu i cùng, chú ý r ng có Cin cách ch n i ph n t n1, n2, ..., ni t n ph n t nên ta có: n n T(i, k) = Cin (2k − 1) suy ra: Sk = i ∑ iT(i, k) = ∑ iCin (2k − 1)i = n(2k – 1).2k(n-1). i =0 i =0 (nh khai tri n (1 + x) và l y ñ o hàm, cho x = 2k – 1 và nhân hai v v i 2k – 1). n Ví d 2.15 (Vô ñ ch Liên Xô). Có m t nhóm ngư i mà trong ñó, m i c p không quen nhau có ñúng hai ngư i quen chung, còn m i c p quen nhau thì không có ngư i quen chung. Ch ng minh r ng s ngư i quen c a m i ngư i là như nhau.
10 L i gi i: N u a quen b và t p các ngư i quen c a a và b (không k a, b) l n lư t là A và B. M i ngư i a’ thu c A s quen v i duy nh t m t ngư i thu c B (do a’ và b không quen nhau, hơn n a h ñã có m t ngư i quen chung là a). Tương t , m i ngư i thu c B cũng quen v i duy nh t m t ngư i thu c A. V y t n t i m t song ánh ñi t A t i B, t c a và b có s ngư i quen b ng nhau. N u a không quen b thì t n t i c quen c a và b. Do ñó, s ngư i quen c a a và b b ng nhau do cùng b ng s ngư i quen c a c (suy ra t trên). 2.3. H TH C TRUY H I 2.3.1. Khái ni m m ñ u và mô hình hóa b ng h th c truy h i Đ nh nghĩa 2.2: H th c truy h i (hay công th c truy h i) ñ i v i dãy s {an} là công th c bi u di n an qua m t hay nhi u s h ng ñi trư c c a nó, c th là a0, a1, a2, …, an-1 v i n ≥ n0 nguyên dương nào ñó. Dãy s ñư c g i là l i gi i hay nghi m c a h th c truy h i n u các s h ng c a nó th a mãn h th c truy h i này. Các giá tr gán cho m t s h u h n các s h ng ñ u c a dãy g i là các ñi u ki n ban ñ u hay ñi u ki n biên c a h th c truy h i. Ví d 2.18. H th c truy h i cho dãy s Fibonacci là Fn = Fn-1 + Fn-2 v i n ≥ 3 và F1 = F2 = 1. 2.3.2. Gi i h th c truy h i 2.3.2.1. Gi i h th c truy h i b ng phương pháp l p Ta có th dùng m t trong hai phương án sau: Ho c ta ñi thay th liên ti p công th c truy h i vào chính nó, m i l n thay như v y b c n s gi m ít nh t 1 ñơn v , cho ñ n khi ñ t giá tr ban ñ u. Ho c là ta xu t phát t ñi u ki n ñ u ta s tính m t s s h ng ñ u và nh n ra qui lu t, sau ñó d ñoán s h ng t ng quát và dùng phương pháp ch ng minh qui n p ñ ch ng minh tính ñúng ñ n c a công th c v a d ñoán ñó. Ví d 2.22 (Bài toán tháp Hà N i) ‘‘Có ba c c 1, 2, 3. c c 1 có n ñĩa x p ch ng lên nhau sao cho ñĩa n m dư i l n hơn ñĩa n m trên. Hãy chuy n t t c các ñĩa t c c 1 sang c c 3 có th dùng c c 2 làm c c trung gian v i ñi u ki n m i l n ch ñư c chuy n 1 ñĩa t c c này sang c c khác và luôn ñ m b o ñĩa n m dư i l n hơn ñĩa n m trên’’. Bài toán ñ t ra là: Tìm s l n di chuy n ñĩa ít nh t c n th c hi n ñ gi i xong bài toán trên. L i gi i: Phương pháp di chuy n như sau: G i sn là s l n di chuy n ñĩa ít nh t c n th c hi n. • Chuy n n-1 ñĩa t c c 1 sang c c 2 (l y c c 3 làm trung gian) ta có sn-1 phép chuy n. • Chuy n ñĩa l n nh t c c 1 sang c c s 3: ta có 1 phép chuy n.
11 • Chuy n n-1 ñĩa c c s 2 v c c s 3 (l y c c 1 làm trung gian) ta có sn-1 phép chuy n. Do v y, ñ chuy n n chi c ñĩa t c c s 1 sang c c s 3, ta c n ít nh t sn-1 + 1 + sn-1 = 2.sn-1 + 1 phép chuy n. V y ta có công th c truy h i c a dãy s s0, s1, s2, … là: sn = 2.sn-1 + 1 và s1 = 1 (s2 = 3, s3 = 7). Ta có: sn = 2sn-1 + 1 = 2(2sn-2+1) + 1 = 22.sn-2 + 2 + 1= 22(2sn-3 +1)+2+1 = 23sn-3 + 22 + 2 + 1= ….. = 2n-1.s1 + 2n-2 + 2n-3 + … + 2 + 1 1 − 2n −1 = 2n-1 + 2n-2 + 2n-3 + … + 2 + 1 = 2. n + 1 = −2 + 2n + 1 = 2 – 1. 1− 2 Ví d 2.23. (Olympic Bungari, 1995) Cho s nguyên n ≥ 2. Hãy tìm s các hoán v (a1, a2, ..., an) c a 1, 2, …, n sao cho t n t i duy nh t m t ch s i ∈ {1, 2, …, n-1} th a mãn ai > ai+1. L i gi i: G i Sn là s các hoán v th a mãn ñi u ki n bài toán. Đ ý r ng s các hoán v mà an = n là Sn-1 (B i vì Sn-1 là s các hoán v (a1, a2, ..., an-1) c a 1, 2, …, n-1 sao cho t n t i duy nh t m t ch s i ∈ {1, 2, …, n - 2} th a mãn ai > ai+1). Còn s các hoán v (a1, a2, ..., an) th a mãn ñi u ki n bài toán v i ai = n (1 ≤ i ≤ n-1) là Cin−−1. 1 n −1 n Do ñó: Sn = Sn-1 + ∑ Cin−−1 1 = Sn-1 +2 n-1 – 1. (Do ∑ Cin−−11 = 2n −1 ). i=1 i=1 Hi n nhiên: S2 = 1, tương t ví d 2.22 ta s có: Sn = 2n - n - 1. 2.3.2.2. Gi i h th c truy h i tuy n tính h s h ng Đ nh nghĩa 2.3: H th c truy h i tuy n tính b c k là h th c truy h i có d ng: an = c1(n). an-1 + c2(n). an-2 + ... + ck(n). an-k + f(n) (T) trong ñó c1(n), c2(n), ..., ck(n) và f(n) là các hàm theo n và ck(n) ≠ 0 v i ∀n • V i h th c truy h i (T) thì h th c truy h i sau an = c1(n). an-1 + c2(n). an-2 + ... + ck(n). an-k (T0) ñư c g i là h th c truy h i tuy n tính thu n nh t b c k ng v i (T). • N u ci(n) = ci , i = 1, 2, ..., k , ñ u là các h ng s , ck(n) ≠ 0 thì (T) ñư c g i là h th c truy h i tuy n tính h s h ng b c k và (T0) tương ng ñư c g i là h th c truy h i tuy n tính thu n nh t h s h ng b c k. • Đi u ki n ban ñ u (ñi u ki n biên) c a (T) là gi thi t m t s ph n t ñ u c a dãy có giá tr cho trư c: a0 = C0, a1 = C1, a2 = C2, ... ∗ Phương trình ñ c trưng c a h th c truy h i (T0) có h s h ng: rk − c1rk-1 − c2rk-2 − ... − ck-1r – ck = 0 (1) Phương trình (1) ñư c g i là phương trình ñ c trưng c a h th c truy h i (T0), nghi m c a nó g i là nghi m ñ c trưng c a h th c truy h i. Nghi m c a phương trình ñ c trưng dùng ñ bi u di n công th c t t c các nghi m (nghi m t ng quát) c a h th c truy h i (T0).
12 ∗ Các ñ nh lý sau ta xét các h th c truy h i (T) và (T0) trên v i h s h ng: Đ nh lý 2.3: N u a1, a2, ..., am là các nghi m c a (T0) thì a = c1a1 + c2a2 + ... + cmam (v i c1, c2, ..., cm là các h ng s tùy ý) cũng là nghi m c a h th c truy h i (T0). Đ nh lý 2.4: N u r là nghi m b i m (m ≥ 1) c a phương trình ñ c trưng (1) thì rn, nrn, n2rn, …, nm-1rn là các nghi m c a (T0), và khi ñó (c0+c1n+c2n2 +…+ cm-1nm-1) .rn, (c0, c1, ..., cm-1 là các h ng s tùy ý) cũng là nghi m c a (T0). H qu 2.1: N u r1, r2, …, rq tương ng là các nghi m b i m1, m2, …, mq (mi ≥ 1, i = 1, 2, …, q) c a phương trình ñ c trưng (1), thì nghi m t ng quát c a (T0) có d ng: an = a1(n) + a2(n) + ... + aq(n), trong ñó: ai(n) = (Ci,0 + nCi,1 + n2Ci,2 +…+ n mi −1.Ci,mi −1 ). rin , ∀i = 1, 2,...,q V i Ci,j , j = 0, 1, 2, …, mi-1 , là các h ng s b t kỳ. H qu 2.2: Cho c1, c2, ..., ck là các s th c. Gi s r ng phương trình ñ c trưng rk − c1rk-1 − c2rk-2 − ... − ck-1r – ck = 0 có k nghi m phân bi t r1, r2, ..., rk (có th ph c). Khi ñó dãy {an} là nghi m c a h th c truy h i (T0) thì nghi m ñó có d ng an = α1r1n + α2r2n + ... + αkrkn , trong ñó α1, α2, ..., αk là các h ng s . Đ nh lý 2.5: Nghi m t ng quát c a (T) có d ng an = hn + gn Trong ñó gn là m t nghi m riêng nào ñó c a (T) và hn là nghi m t ng quát c a h th c truy h i tuy n tính thu n nh t (T0) ng v i (T). Đ nh lý 2.6: [4, tr.62] Cho h th c truy h i tuy n tính không thu n nh t h s h ng b c k: an + C1.an-1 + C2.an-2 + ... + Ck.an-k = f(n) (T) trong ñó f(n) = Ps(n) (là ña th c b c s c a n) Phương trình ñ c trưng c a (T) là: rk + C1rk-1 + C2rk-2 + ... + Ck-1r + Ck = 0 (1) • N u phương trình ñ c trưng (1) không có nghi m r = 1 thì nghi m riêng c a (T) có d ng a * = Qs(n). n • N u phương trình ñ c trưng (1) có nghi m b i m là r = 1 thì nghi m riêng c a (T) có d ng a * = nm.Qs(n). n Đ nh lý 2.7: (M r ng c a ñ nh lý 2.6) Cho h th c truy h i tuy n tính không thu n nh t h s h ng b c k: an + C1.an-1 + C2.an-2 + ... + Ck.an-k = f(n) (T) trong ñó f(n) = Ps(n). β (là ña th c b c s c a n, và β là m t h ng s ) n Phương trình ñ c trưng c a (T) là: rk + C1rk-1 + C2rk-2 + ... + Ck-1r + Ck = 0 (1) • N u β không ph i là nghi m c a phương trình ñ c trưng (1) thì nghi m riêng c a (T) có d ng a * = Qs(n). β n (trong ñó Qs(n) là ña th c có b c s). n • N u β là nghi m b i m (m ≥ 1) c a phương trình ñ c trưng (1) thì nghi m riêng c a (T) có d ng a * = nm.Qs(n). β n (trong ñó Qs(n) là ña th c có b c s). n
13 Đ nh lý 2.8: (Nguyên lý ch ng ch t nghi m) Cho h th c truy h i tuy n tính không thu n nh t h s h ng b c k: an = C1.an-1 + C2.an-2 + ... + Ck.an-k + f(n) (T) N u thành ph n không thu n nh t f(n) c a (T) có d ng f(n) = p1(n) + p2(n) + ... + pm(n) thì nghi m riêng c a (T) có d ng gn = f1(n) + f2(n) + ... + fm(n), trong ñó fi(n), i = 1, m là nghi m riêng c a h th c truy h i không thu n nh t tương ng: an = C1.an-1 + C2.an-2 + ... + Ck.an-k + fi(n), i = 1, m . Ví d 2.33. Gi i công th c truy h i an = 4an-1 – 4an-2 + n2n + 3n + 4 , n ≥ 2 (T) L i gi i: • Phương trình thu n nh t tương ng có nghi m t ng quát là hn = c1.2n + c2.n2n • Ta có thành ph n không thu n nh t là f(n) = n2n + 3n + 4 do ñó ñ tìm nghi m riêng gn c a (T) ta l n lư t ñi tìm nghi m riêng c a 3 h th c truy h i sau: an = 4an-1 – 4an-2 + 4 ; an = 4an-1 – 4an-2 + 3n ; an = 4an-1 – 4an-2 + n2n * V i h th c an = 4an-1 – 4an-2 + 4 (T1) Ta có thành ph n không thu n nh t là f1(n) = 4 = 4.1n và do 1 không là nghi m c a phương trình ñ c trưng nên nghi m riêng c a (T1) có d ng c.1n, thay vào (T1) ta ñư c c = 4. V y nghi m riêng c a (T1) là 4. * V i h th c an = 4an-1 – 4an-2 + 3n (T2) n n Ta có thành ph n không thu n nh t là f2(n) = 3 = 1.3 và 3 không là nghi m c a phương trình ñ c trưng nên nghi m riêng c a (T2) có d ng c.3n, thay vào (T2) ta ñư c c = 9. V y nghi m riêng c a (T2) là 9.3n. * V i h th c an = 4an-1 – 4an-2 + n2n (T3) n Ta có thành ph n không thu n nh t là f3(n) = n.2 và 2 là nghi m b i 2 c a phương trình ñ c trưng nên nghi m riêng c a (T3) có d ng n2(c1n + c2)2n, thay vào (T3) ta có: n2(c1n + c2)2n = 4 ( n − 1) [c1(n - 1) + c2]2n-1 - 4 ( n − 2 ) [c1(n - 2) + c2]2n-2 + n2n 2 2 chia c hai v cho 2n-2 sau ñó khai tri n và cân b ng h s (c a ña th c n n) ta ñư c: 1 1 1 1 c1 = , c2 = . V y nghi m riêng c a (T3) là n2( n + )2n. 6 2 6 2 T ba trư ng h p trên suy ra nghi m riêng c a h th c truy h i (T) là 1 1 gn = 4 + 9.3n + n2( n + )2n. 6 2 1 1 V y nghi m t ng quát c a (T) là: an = c1.2n + c2.n2n +4 + 9.3n + n2( n + )2n. 6 2
14 2.4. PHƯƠNG PHÁP Đ M B NG HÀM SINH Có r t nhi u bài toán t h p như bài toán phân ho ch t p h p, bài toán ñ m, tìm dãy s trong các ñ thi h c sinh gi i qu c gia, qu c t là các bài toán r t khó. Hàm sinh là m t công c hi u l c ñ gi i quy t d ng bài t p này. Khái ni m hàm sinh khá ñơn gi n, d hi u nhưng l i có ng d ng r t hay vào vi c gi i các d ng bài toán trên. 2.4.1. Đ nh nghĩa 2.4 Cho dãy s {an}. Chu i lũy th a hình th c vô h n F(x) = ∑ a n x n g i là hàm sinh n ≥0 thư ng sinh b i dãy s {an}. Kí hi u: {an} ↔ F(x) hay {an} ↔ F. 2.4.2. Công th c khai tri n Taylor Gi s f(x) là hàm s liên t c, có ñ o hàm m i c p trên kho ng (a, b); x0∈ (a, b). Khi f (n) (x 0 ) n ñó ta có công th c khai tri n Taylor: f(x) = ∑ x . n ≥0 n! 2.4.3. Công th c nh th c Newton m r ng • V i α là m t s th c và k là s nguyên không âm. Lúc ñó h s nh th c Newton  α(α − 1)...(α − k + 1)  , k>0 m r ng Cα ñư c ñ nh nghĩa như sau: Cα =  k k k! 1, k = 0  ∞ α • Cho x là s th c v i |x| < 1 và α là m t s th c. Lúc ñó: (1 + x) = ∑ Cα x k . k k =0 α(α − 1) 2 α(α − 1)...(α − n + 1) n T c là: (1 + x)α = 1 + αx + x + ... + x + ... 2 n! 2.4.4. Tính ch t c a hàm sinh Cho {an} ↔ F(x) , {bn} ↔ G(x) khi ñó ta có các tính ch t sau: (1) {an ± bn} ↔ F(x) ± G(x) (2) {kan} ↔ kF(x) , ∀ k∈ R (3) {(n+1)an+1} ↔ F’(x) (4) {an-an-1} ↔ (1-x)F(x) (5) {nan} ↔ xF’(x) F(x) − a 0 − a1x − a 2 x 2 − a 3x 3 − ... − a h −1x h −1 (6) {an+h} ↔ , h∈N xh (7) {k.an ± h.bn} ↔ k.F(x) + h.G(x) F(x) (8) {a0+a1+a2+...+an} ↔ 1− x n (9) {cn} = { ∑ a i b j } = { ∑ a k bn−k } ↔ F(x).G(x) i + j=n k =0
15 2.4.5. M t s khai tri n ñ i s thư ng dùng trong vi c s d ng hàm sinh 1 (1) = 1 + x + x 2 + ... + x k + ... 1− x 1 (2) = 1 – x + x2 – x3 + … 1+ x 1 (3) = 1 + ax + a2x2 + a3x3 + …+ anxn +… 1 − ax (4) (1 + x)n = 1 + C1 x + Cn x 2 + ... + Cn x n n 2 n ∞ 1 n(n + 1) 2 n(n + 1)(n + 2) 3 (5) = ∑ Cn −1 −1x k = 1 + nx + n +k x + x + ... (1 − x) n k =0 2 3! (6) xk 1− x ( ) = x k 1 + x + x 2 + ... = x k + x k +1 + x k +2 + ... 1 − x k +1 (7) = 1 + x + x 2 + ... + x k 1− x 1 (8) = 1 + x 2 + x 4 + x 6 + ... 1− x 2 x (9) = x(1 + x 2 + x 4 + x 6 + ...) = x + x 3 + x 5 + x 7 + ... 1− x 2 1 (10) = 1 + 2x + 3x 2 + ... + (n+1)xn +... (1 − x) 2 1+ x (11) = 1 + 3x + 5x 2 + ... + (2n + 1)x n + ... (1 − x) 2 x + x2 (12) = x + 4x 2 + 9x 3 + ... + n 2 x n + ... (1 − x) 3 x 2 x3 xn n (13) e x = 1 + x + + + ... + x + ... 2! 3! n! x 2 x3 xn n (14) − ln(1 − x) = x + + + ... + x + ... 2 3 n ∞ (15) (1 + ax) = ∑ Cn a k x k n k n =0 2.4.6. Phương pháp ñ m b ng hàm sinh Hàm sinh có th ñư c áp d ng trong các bài toán ñ m. Nói riêng, các bài toán ch n các ph n t t m t t p h p thông thư ng s d n ñ n các hàm sinh. Khi hàm sinh ñư c áp d ng theo cách này, h s c a xn chính là s cách ch n n ph n t . 2.4.6.1. Ch n các ph n t khác nhau Hàm sinh cho dãy các h s nh th c ñư c suy ra tr c ti p t ñ nh lý nh th c {Cik } ↔ C0 + C1 x + ... + Ck x k = (1 + x) k k k k
16 Như v y h s c a xn trong (1 + x)k là Cn b ng s cách ch n n ph n t phân k bi t t m t t p h p g m k ph n t không phân bi t th t . Ví d , h s c a x2 là C2 , n k+1 s cách ch n 2 ph n t t t p h p k ph n t . Tương t , h s c a x là s cách ch n k + 1 ph n t t t p h p k ph n t và như th , b ng 0. 2.4.6.2. Xây d ng hàm sinh ñ gi i bài toán ñ m Hàm sinh cho s cách ch n n ph n t t t p h p k ph n t là (1 + x)k. Đây chính là công th c hàm sinh mà ta ñã nh n ñư c b ng cách s d ng ñ nh lý nh th c. Chúng ta có th m r ng ñi u này qua ñ nh lý sau ñây: Đ nh lý 2.8. (Quy t c xo n) G i A(x) là hàm sinh cho cách ch n các ph n t t t p h p A và B(x) là hàm sinh cho cách ch n các ph n t t t p h p B. N u A và B là r i nhau thì hàm sinh cho cách ch n các ph n t t A ∪ B là A(x).B(x). 2.4.6.3. Ch n các ph n t có l p 1 Hàm sinh c a cách ch n các ph n t t t p h p n ph n t có l p là . (1 − x) n Như v y theo công th c Taylor s cách ch n k ph n t có l p t n ph n t b ng Ck +k −1. n M t cách ti p c n khác, ta l p lu n như sau: 1 V i k > 0, ta có {Cn +k −1, n = 0, 1, 2, ...} ↔ F(x) = n (1 − x) k k 1  1  2 3 k Th y v y, ta có =  = ( 1 + x + x + x + ... ) (1 − x) k 1− x  N u ta khai tri n bi u th c trên b ng cách th c hi n nhân phá ngo c, thì s l n xu t hi n s h ng xn s b ng s nghi m nguyên không âm c a phương trình: x1 + x2 + ..... + xk = n. Ta ñã bi t s nghi m c a phương trình này b ng: Cn +k −1 . Như n n v y h s c a x chính b ng s cách ch n n v t t t p có k lo i ñ v t. Nh n xét 2.7: Ví d trên ñã áp d ng qui t c xo n g i ý cho ta phương pháp gi i nhi u bài toán ñ m. Ch ng h n v i hàm sinh: F(x) = (1 + x + x2 + x3 + x4 + x5)(1 + x + x2)(1 + x + x2 + x3 ) Gi s x x1 , x x 2 , x x3 tương ng là các s h ng l y t các th a s th nh t, th hai và ba c a v ph i, suy ra 0 ≤ x1 ≤ 5, 0 ≤ x2 ≤ 2, 0 ≤ x3 ≤ 3. Khi khai tri n v ph i các th a s này s cho ta s h ng xn, v i n = x1 + x2 + x3. Như th h s c a xn trong F(x) s là s nghi m nguyên không âm c a phương trình x1 + x2 + x3 = n th a mãn: 0 ≤ x1 ≤ 5, 0 ≤ x2 ≤ 2, 0 ≤ x3 ≤ 3. Như v y h s này cũng cho ta s cách ch n n v t t t p có 3 lo i v t, g m 5 v t lo i 1, 2 v t lo i 2 và 3 v t lo i 3.
17 Ví d 2.41. Bây gi ta xét m t bài toán ñ m r t khó ch u. Có bao nhiêu nhiêu cách s p m t gi n trái cây tho mãn các ñi u ki n ràng bu c sau: • S táo ph i ch n • Ch có th có nhi u nh t 4 qu cam • S chu i ph i chia h t cho 5 • Ch có th có nhi u nh t 1 qu ñào Ch ng h n, ta có 7 cách s p gi trái cây có 6 trái: Táo 6 4 4 2 2 0 0 Chu i 0 0 0 0 0 5 5 Cam 0 2 1 4 3 1 0 Đào 0 0 1 0 1 0 1 L i gi i: Các ñi u ki n ràng bu c này quá ph c t p và có c m giác như vi c ñi tìm l i gi i là vô v ng. Nhưng ta hãy xem hàm sinh s x lý bài toán này th nào. Trư c h t, ta ñi tìm hàm sinh cho s cách ch n táo. Có 1 cách ch n 0 qu táo, có 0 cách ch n 1 qu táo (vì s táo ph i ch n), có 1 cách ch n 2 qu táo, có 0 cách ch n 3 qu táo … 1 Như th ta có hàm sinh cho s cách ch n táo là A(x) = 1 + x2 + x4 + … = . 1 − x2 1 Tương t , hàm sinh cho s cách ch n chu i là B(x) = 1 + x5 + x10 + … = . 1 − x5 Bây gi , ta có th ch n 0 qu cam b ng 1 cách, 1 qu cam b ng 1 cách, … Nhưng ta 2 3 4 1 − x5 không th ch n hơn 4 qu cam, vì th ta có C(x) = 1 + x + x + x + x = . 1− x 1 − x2 Và tương t , hàm sinh cho s cách ch n ñào là D(x) = 1 + x = . 1− x Theo quy t c xo n, hàm sinh cho cách ch n t c 4 lo i trái cây b ng 1 1 1 − x5 1 − x 2 1 A(x).B(x).C(x).D(x) = . . . = = 1 + 2x + 3x 2 + 4x 3 + ... 1 − x 1 − x 1 − x 1 − x (1 − x) 2 5 2 1 G n như t t c ñư c gi n ư c v i nhau! Ch còn l i mà ta ñã tìm ñư c chu i (1 − x)2 lu th a t trư c ñó. Như th s cách s p gi trái cây g m n trái cây ñơn gi n b ng n + 1. Đi u này phù h p v i k t qu mà ta ñã tìm ra trư c ñó, vì có 7 cách s p cho gi 6 trái cây. Th t là thú v ! Ví d 2.42. Tìm hàm sinh cho s nghi m nguyên dương l c a phương trình x1 + x2 + x3 +...+ xk = n L i gi i: Hàm sinh c n tìm là: k ( )  x 1 + x 2 + x 4 + x 6 + ...  =  x  = xk k 3 5 7 k f(x) = (x + x + x + x + ...) =  2 .   1− x  (1 − x 2 )k
18 Chương 3 M TS NG D NG 3.1. M T S NG D NG C A H TH C TRUY H I 3.1.1. ng d ng bài toán tìm s h ng t ng quát c a h th c truy h i vào gi i m t s bài toán v dãy s và t h p Bài toán 3.2 (Olympic toán sinh viên toàn qu c – 2004). b Cho dãy s (bn) xác ñ nh b i h th c sau: b0 = 0, bn = n −1 + (−1)n , n ≥ 1 . 2004 2 Tính lim b n . n →+∞ 1 1 L i gi i: Phương trình ñ c trưng r - =0 ⇔ r= 2004 2004 n  1  Nghi m t ng quát c a h th c truy h i thu n nh t tương ng là b n = C 1.  .  2004  f(n) = (-1)n nên ch n b* = C2.(-1)n. Thay vào h th c truy h i ñ bài ta ñư c: n 2004 2004 C2 = ⇒ b* = n .(-1)n. 2005 2005 n  1  2004 . ( −1) . n ⇒ Công th c t ng quát c a dãy s c n tìm là bn = C1.  +  2004  2005 2004 2004 Đ cho b0 = 0 ⇒ 0 = C 1 + ⇒ C1 = − 2005 2005 V y công th c t ng quát c a dãy s c n tìm là: bn = − 2004  1  . n + 2004 . ( −1) = − n ( −2004 ) − 1 . n  n −1 2005  2004  2005 2005.( 2004 ) 2 2  ( −1) n 2004n − 1   ( −1)n (2004)n − 1 =  2004 2 . Suy ra lim b n = lim  2  =  lim    n →+∞  2005. 2004 n −1  n −1 n →+∞  ( )    n →+∞ 2005.( 2004 )   2005   Bài toán 3.7. (IMO 1967) Trong m t cu c thi ñ u th thao có m huy chương, ñư c 1 phát trong n ngày thi ñ u. Ngày th nh t, ngư i ta phát m t huy chương và s huy 7 1 chương còn l i. Ngày th hai, ngư i ta phát hai huy chương và huy chương còn 7 l i. Nh ng ngày còn l i ñư c ti p t c và tương t như v y. Ngày sau cùng còn l i n huy chương ñ phát. H i có t t c có bao nhiêu huy chương và ñã phát trong bao nhiêu ngày. L i gi i: G i ak là s huy chương còn l i trư c ngày th k, suy ra a1 = m và ta có:
19 1 1 ak+1 = ak – k - (ak – k) = 6 a k - 6k (Do ngày th k phát ñi k huy chương và huy 7 7 7 7 k −1 chương còn l i). Gi i h th c truy h i này ta ñư c: a k =   6   (m − 36) − 6k + 42 . 7 n −1 n −1 Theo gi thi t ta có an = n =   (m − 36) − 6n + 42 ⇒ m − 36 = 7(n − 6)   6 7     7 6 Vì m – 36 ∈ và (6, 7) = 1, 6 > n – 6 nên n – 6 = 0 ⇔ n = 6 ⇒ m = 36. n-1 V y có 36 huy chương ñư c phát trong 6 ngày. 3.1.2. ng d ng gi i h th c truy h i là m t h bi u th c tuy n tính thu n nh t c pm t a1 = α, b1 = β  Xét h : a n +1 = pa n + qb n , v i α , β , p, q, r, s là các h ng s th c. b = ra + sb  n +1 n n Gi i h trên là ñi xác ñ nh s h ng t ng quát c a các dãy s (an) và (bn) th a mãn h th c truy h i ñó. B ng cách bi n ñ i ñưa v gi i h th c truy h i tuy n tính thu n nh t c p hai. Mu n v y ta thay n b i n + 1 vào phương trình th hai c a h trên ta có: a n +2 = pa n +1 + qb n +1 = pa n +1 + q(ra n + sb n ) = pa n +1 + qra n + s(a n +1 − pa n ) Suy ra a n +2 = (p + s)a n +1 + (qr − ps)a n M t khác t h trên ta l i có a 2 = pa1 + qb1 = pα + qβ V y ta có h th c truy h i tuy n tính thu n nh t c p hai là a n +2 = (p + s)a n +1 + (qr − ps)a n , a1 = α, a 2 = pα + qβ Mà ta ñã bi t cách gi i. T ñó ta tìm ñư c an , th vào h trên và thu ñư c bn. 3.1.3. ng d ng tìm s h ng c a m t s dãy s ñ c bi t 3.1.3.1. D ng 1 px + q Cho dãy s ( x n ) xác ñ nh b i x n +1 = n , trong ñó: x0 = a cho trư c và p, q, r, s rx n + s là các h ng s . Tìm s h ng t ng quát x n . Gi s yn và zn là nghi m c a h :  y n +1 = py n + qz n  , y0 = a, z0 = 1. z n +1 = ry n + sz n y y a Khi ñó x n = n là nghi m c a h th c truy h i ñã cho. Th t v y, x 0 = 0 = = a zn z0 1 y p n +q y py + qz n zn px + q ñúng. Ta l i có: x n +1 = n +1 = n = = n ñúng. z n +1 ry n + sz n r yn +s rx n + s zn
20 3.1.3.2. D ng 2 u n −1.u n Cho dãy s (un ) xác ñ nh b i u1 = α, u 2 = β và u n +1 = (1) au n −1 + bu n Tìm s h ng t ng quát u n . 1 au + bu n 1 1 1 Bi n ñ i (1) ⇒ = n −1 ⇔ = a. + b. u n +1 u n −1.u n u n +1 un u n −1 1 Đ t vn = ta có: v n +1 − av n − bv n −1 = 0 (Đây là h th c truy h i tuy n tính thu n un nh t h s h ng). 3.1.3.3. D ng 3 Cho dãy s (un) xác ñ nh như sau: u n = a.u n −1 + bu 2 −1 + c , ∀n ≥ 2 n (2) và u1 = α, a2 − b = 1. Tìm s h ng t ng quát u n . Ta có: (2) ⇔ (un – aun-1)2 = b u 2 −1 + c ⇔ u 2 − 2au n u n −1 + u 2 −1 − c = 0 n n n (3) Thay n b i n – 1 ta có: u 2 −2 − 2au n −1u n −2 + u n −1 − c = 0 n 2 (4) T (3) và (4) ta có un và un-2 là 2 nghi m c a phương trình: t 2 − 2au n −1.t + u n −1 − c = 0 . 2 Áp d ng ñ nh lý Viet, ta có: un + un-2 = 2a.un-1. T ñó suy ra un. 3.1.3.4. D ng 4 u n −1 Tìm dãy s (un) xác ñ nh như sau: u n = , ∀n ≥ 2 (5) a + c.u n −1 + b 2 V i ñi u ki n: u1 = α , α > 0, a > 0, a2 − b = 1 1 a b 1 Ta có (5) ⇔ = + c+ 2 và ñ t x n = ta ñư c: u n u n −1 u n −1 un x n = a.x n −1 + b.x n −1 + c ñây là bài toán d ng 3, nên ta tìm ñư c xn, t ñó suy ra un. 2 3.2. M T S NG D NG C A PHƯƠNG PHÁP SONG ÁNH Dùng song ánh ñ thi t l p h th c truy h i, d a trên ý tư ng: N u t n t i m t song ánh t t p A ñ n t p B thì s ph n t c a A và B s b ng nhau. T ñó ng d ng vào gi i m t s bài toán như: Tính t ng t h p, ch ng minh ñ ng th c t h p ... là các d ng toán ñ c trưng c a phương pháp song ánh. Ph n này chúng ta ñi tìm hi u các bài toán thu c các d ng ñ c trưng ñó. 3.2.1. Dùng song ánh xây d ng h th c truy h i và ch ng minh hai t p b ng nhau áp d ng vào gi i m t s bài toán t h p Bài toán 3.15. Cho s nguyên dương n, tìm s t p con khác r ng c a t p S = {1, 2, ..., n} sao cho trong m i t p con không ch a hai s nguyên liên ti p nào. L i gi i: Đ t Sn = {M ⊂ S | M không ch a 2 s nguyên liên ti p nào}