Tài liệu Vận dụng phép đếm nâng cao vào giải một số bài toán thi học sinh giỏi (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————o0o————— NGUYỄN MẠNH ĐỨC VẬN DỤNG PHÉP ĐẾM NÂNG CAO VÀO GIẢI MỘT SỐ BÀI TOÁN THI HỌC SINH GIỎI LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————o0o————— NGUYỄN MẠNH ĐỨC VẬN DỤNG PHÉP ĐẾM NÂNG CAO VÀO GIẢI MỘT SỐ BÀI TOÁN THI HỌC SINH GIỎI Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS TRỊNH THANH HẢI Thái Nguyên - 2017 2 Mục lục Mở đầu 1 Một số kiến thức chuẩn bị 1.1 Nguyên lý cộng . . . . . . . . . 1.1.1 Định nghĩa . . . . . . . 1.1.2 Ví dụ . . . . . . . . . . 1.2 Nguyên lý nhân . . . . . . . . . 1.2.1 Định nghĩa . . . . . . . 1.2.2 Ví dụ . . . . . . . . . . 1.3 Nguyên lý bù trừ, thêm bớt . . 1.3.1 Định nghĩa . . . . . . . 1.3.2 Ví dụ . . . . . . . . . . 1.4 Hàm sinh . . . . . . . . . . . . 1.4.1 Định nghĩa . . . . . . . 1.4.2 Các định lý và mệnh đề 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Vận dụng phương pháp đếm vào giải toán 2.1 Vận dụng phương pháp truy hồi . . . . . . 2.1.1 Ý tưởng . . . . . . . . . . . . . . . 2.1.2 Một số ví dụ . . . . . . . . . . . . . 2.2 Vận dụng phương pháp song ánh . . . . . 2.2.1 Ý tưởng . . . . . . . . . . . . . . . 2.2.2 Một số ví dụ . . . . . . . . . . . . . 2.3 Vận dụng phương pháp đa thức và số phức 2.3.1 Ý tưởng . . . . . . . . . . . . . . . 2.3.2 Ví dụ . . . . . . . . . . . . . . . . 2.4 Vận dụng phương pháp sử dụng hàm sinh 2.4.1 Ý tưởng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 6 7 7 7 8 9 9 10 13 13 13 . . . . . . . . . . . 16 16 16 16 23 23 24 30 30 30 36 36 3 2.4.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . 37 Kết luận 42 Tài liệu tham khảo 43 4 Mở đầu Trong chương trình toán ở trường THPT nói chung, nội dung dành cho học sinh giỏi nói riêng, các “bài toán đếm” luôn thu hút được sự quan tâm của học sinh bởi tính thực tiễn đa dạng, phong phú của nó và dạng bài tập này cũng thường có mặt trong các đề thi học sinh giỏi hàng năm các cấp. Tuy nhiên việc giải các bài toán dạng này thường là khó đối với nhiều học sinh, lý do chính là học sinh chưa nắm được và biết cách vận dụng các phép đếm vào từng bài toán cụ thể. Cũng đã có một số tác giả đã đưa ra một vài dạng bài tập liên quan đến hướng nghiên cứu của luận văn như: Văn Phú Quốc [7], Nguyễn Văn Nho [8]. . . Tuy nhiên các tài liệu này chưa phân nhóm, đưa ra một cách tường minh, rõ ràng các ý tưởng, phương pháp vận dụng phép đếm vào giải các bài toán. Với mục đích tìm hiểu, sưu tầm một hệ thống các bài toán mà lời giải của nó có vận dụng các phép đếm để sử dụng các bài tập này vào việc ôn tập, bồi dưỡng cho học sinh khá, giỏi ở trường THPT, chúng tôi chọn đề tài: “Vận dụng phép đếm nâng cao vào giải một số bài toán thi học sinh giỏi”. Nhiệm vụ cụ thể của luận văn là: (1). Hệ thống một số tính chất cơ bản trong chương trình toán phổ thông để khởi đầu cho việc tìm hiểu các phép đếm nâng cao. (2). Giới thiệu một số phép đếm nâng cao và minh họa việc vận dụng chúng vào giải một số bài tập, đề thi học sinh giỏi. Trong quá trình thực hiện đề tài, luận văn đã tham khảo trích dẫn một số bài tập trong các tài liệu tham khảo đồng thời cũng cố gắng đưa ra lời giải chi tiết hơn cho một số ví dụ mà trong các tài liệu tham khảo mới chỉ đưa ra hướng giải hoặc lời giải vắn tắt. Vì trong SGK, chương trình toán THPT không dạy những phép đếm này một cách tường minh; nên để phân biệt chúng tôi gọi tạm là 5 “Phép đếm nâng cao”. Để hoàn chỉnh luận văn, tôi luôn nhận được sự hướng dẫn, chỉ bảo tận tình của PGS.TS. Trịnh Thanh Hải (Đại học Khoa học – Đại học Thái Nguyên), các thầy cô khoa Toán - Tin trường Đại học Khoa học – Đại học Thái Nguyên và các thầy cô giảng dạy lớp cao học toán K9A. Tôi xin chân thành bày tỏ lòng biết ơn sâu sắc đến các thầy cô và xin gửi lời tri ân nhất của tôi đến thầy cô. Tôi xin gửi lời cảm ơn tới Lãnh đạo trường Đại học Khoa học – Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán – Tin, PGS.TS. Nguyễn Thị Thu Thủy cùng toàn thể các thầy cô trong trường đã hướng dẫn và tạo mọi điều kiện cho tôi trong suốt quá trình học tập và thực hiện luận văn. 6 Chương 1 Một số kiến thức chuẩn bị Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thỏa mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp. Chủ đề này đã được nghiên cứu từ thế kỉ XVII, khi những vấn đề về tổ hợp được nêu ra trong những công trình nghiên cứu các trò chơi may rủi. Liệt kê, đếm các đối tượng có những tính chất nào đó là một phần quan trọng của lý thuyết tổ hợp. Đếm các đối tượng để giải nhiều bài toán khác nhau. 1.1 Nguyên lý cộng Đây là nguyên lý cơ bản của tổ hợp, được vận dụng rộng rãi vào giải quyết các bài toán đếm. Nếu A và B là hai tập hợp không giao nhau thì |A ∪ B| = |A| + |B|. Các tập hợp được xét ở đây là những tập hợp có hữu hạn các phần tử và ký hiệu |A| là số các phần tử của tập hợp A. 1.1.1 Định nghĩa Cho Ai , i = 1, n là các tập rời nhau. Khi đó   n n [  [   |Ai |.  Ai  =   i=1 i=1 Một trường hợp riêng của nguyên lý cộng: Nếu A là một tính chất cho trên tập X |A| = |X| − |Ac | 7 thì |A| = |X| − |Ā|. 1.1.2 Ví dụ Ví dụ 1.1.1 Một đoàn vận động viên gồm hai môn bắn súng và bơi được cử đi thi đấu ở nước ngoài. Nam có 10 người. Số vận động viên thi bắn súng (kể cả nam và và nữ) là 14. Số nữ vận động viên thi bơi bằng số nam vận động viên thi bắn súng. Hỏi đoàn có bao nhiêu người? Lời giải. Chia đoàn thành 2 lớp: nam và nữ. Lớp nữ lại được chia 2: thi bắn súng và thi bơi. Thay số nữ thi bơi bằng số nam thi bắn súng (2 số này bằng nhau theo đầu bài), ta được số nữ bằng tổng số cầu thủ thi bắn súng. Từ đó, theo nguyên lý cộng, toàn đoàn có 10 + 14 = 24 người. Ví dụ 1.1.2 Có bao nhiêu xâu gồm 4 chữ số thập phân có đúng 3 ký tự là 9? Lời giải. Xâu có thể chứa ký tự khác 9 ở vị trí thứ nhất hoặc ký tự khác 9 ở vị trí thứ hai hoặc ký tự khác 9 ở vị trí thứ ba hoặc ký tự khác 9 ở vị trí thứ tư ta có thể sử dụng quy tắc cộng. Đối với mỗi trường hợp, có 9 khả năng chọn ký tự khác với 9 (bất kể chữ số khác 9 nào trong 9 chữ số 0, 1, . . . , 8). Vậy đáp số là: 9 + 9 + 9 + 9 = 36. 1.2 1.2.1 Nguyên lý nhân Định nghĩa Định nghĩa 1.2.1 Tích Descartes của hai tập hợp A, B ký hiệu bởi A × B là tập hợp tất cả các cặp thứ tự (a, b) với a ∈ A, b ∈ B. Định nghĩa 1.2.2 Nếu A và B là hai tập hợp hữu hạn thì A × B cũng hữu hạn và ta có |A × B| = |A|.|B|. Định nghĩa về tích Descartes và nguyên lý nhân trên đây có thể mở rộng cho nhiều tập hợp. Nguyên lý nhân có thể phát biểu một cách khác như sau: 8 Nếu một quá trình có thể được thực hiện qua hai công đọan: công đọan 1 có n1 cách thực hiện, công đọan 2 (sau khi thực hiện công đoạn 1) có n2 cách thực hiện. Khi đó có n1 .n2 cách thực hiện quá trình đó. Tổng quát: cho n tập hợp Ai , i = 1, n, n ≥ 2. Khi đó:   n n Y  Y   |Ai |.  Ai  =   i=1 1.2.2 i=1 Ví dụ Ví dụ 1.2.3 Hỏi có bao nhiêu lá cờ gồm 3 vạch mầu, mầu của mỗi vạch lấy từ 3 mầu xanh, đỏ, trắng sao cho: a) Không có hai vạch liên tiếp nào cùng mầu; b) Không có hai vạch nào cùng mầu. Lời giải. Đánh số các vạch của lá cờ bởi 1, 2, 3 từ trên xuống. a) Mầu của vạch 1 có 3 cách chọn. Sau khi mầu của vạch 1 đã chọn, mầu của vạch 2 có 2 cách chọn không được chọn lại mầu của vạch 1). Sau khi mầu của vạch 1, 2 đã chọn, mầu của vạch 3 có 2 cách chọn (không được chọn lại mầu của vạch 2). Theo nguyên lý nhân, số lá cờ cần đếm là: 3.2.2 = 12. b) Mầu của vạch 1 có 3 cách chọn. Sau khi mầu của vạch 1 đã chọn, mầu của vạch 2 có 2 cách chọn (không được chọn lại mầu của vạch 1). Sau khi mầu của vạch 1, 2 đã chọn, mầu của vạch 3 có 1 cách chọn (không được chọn lại mầu của vạch 1 và 2). Theo nguyên lý nhân, số lá cờ cần đếm là: 3.2.1 = 6. Ví dụ 1.2.4 Cho n là một số nguyên dương. Xét A = P1α1 .P2α2 . . . Pnαn với P1 , P2 , . . . , Pn là các số nguyên tố phân biệt. Hỏi A có bao nhiêu ước số dương phân biệt? Lời giải. Ký hiệu Ai = {1, 2, 3, . . . , αi }, i = 1, n . Mỗi ước số a của A có dạng: a = P1β1 .P2β2 . . . Pnβn trong đó βi ∈ Ai , do đó số ước số của A là số phần tử của tích Đề các A1 × A2 × · · · × An . Áp dụng nguyên lý nhân ta có số các ước của A là: A = |A1 |.|A2 | . . . |An | = (α1 + 1)(α2 + 1) . . . (αn + 1). 9 1.3 Nguyên lý bù trừ, thêm bớt 1.3.1 Định nghĩa Cho X là một tập hữu hạn và A ⊂ X. Gọi Ā = X/A. Khi đó ta có: |Ā| = |X| − |A|. Nhận xét 1.3.1 Cho A1 , A2 là hai tập hữu hạn, khi đó |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |. Từ đó với ba tập hợp hữu hạn A1 , A2 , A3 , ta có: |A1 ∪ A2 ∪ A3 | = |A1 | + |A2 | + |A3 | − |A1 ∩ A2 | − |A2 ∩ A3 | − |A3 ∩ A1 | + |A1 ∩ A2 ∩ A3 | và bằng quy nạp, với k tập hữu hạn A1 , A2 , . . . Ak ta có: |A1 ∪ A2 ∪ . . . ∪ Ak | = N1 − N2 + N3 − ... + (−1)k−1 Nk trong đó Nm (1 ≤ m ≤ k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là X Nm = |Ai1 ∩ Ai2 ∩ . . . ∩ Aim |. 1≤i1 . |A| ≥ (2n − 2)! n.2(2n − 1) − 2 2 12 Ví dụ 1.3.6 (VMO 2005B). Tìm kết quả học tập ở một lớp học, người ta thấy: 2 - Hơn số học sinh đạt điểm giỏi ở môn Toán cũng đồng thời đạt điểm 3 giỏi ở môn Vật lý; 2 - Hơn số học sinh đạt điểm giỏi ở môn Vật lý cũng đồng thời đạt 3 điểm giỏi ở môn Văn; 2 - Hơn số học sinh đạt điểm giỏi ở môn Văn cũng đồng thời đạt điểm 3 giỏi ở môn Lịch sử; 2 - Hơn số học sinh đạt điểm giỏi ở môn Lịch sử cũng đồng thời đạt 3 điểm giỏi ở môn Toán; Chứng minh rằng trong lớp học nói trên có ít nhất một học sinh đạt điểm giỏi ở cả bốn môn Toán, Vật lý, Văn, Lịch sử. Lời giải. Gọi T, L, V, S tương ứng là tập hợp các học sinh đạt điểm giỏi ở môn Toán, Vật lý, Văn, Lịch sử. Ký hiệu T1 = T ∩ L; L1 = L ∩ S; V1 = V ∩ S. Theo giả thiết bài toán ta có: 2 |T1 | > |T |; 3 2 |L1 | > |L|; 3 2 |V1 | > |V |. 3 Ta sẽ chứng minh: |T ∩ L ∩ V ∩ S| > 0. Không mất tính tổng quát, ta giả sử T là tập có nhiều phần tử nhất. Ta có |T1 ∩ L1 | = |T1 | + |L1 | − |T1 ∪ L1 |. (1.1) Vì T1 ∪ L1 ⊂ L nên |T1 ∪ L1 | ≤ |L|. Do đó từ (1.1) ta được: 2 2 1 1 2 |T1 ∩ L1 | > |T | + |L| − |L| = |T | − |L| ≥ |T | (do |T | ≥ |L|). 3 3 3 3 3 (1.2) Lại có |T1 ∩ L1 ∩ V1 | = |T1 ∩ L1 | + |V1 | − |(T1 ∩ L1 ) ∪ V1 |. Vì L1 ⊂ V nên T1 ∩ L1 ⊂ V. Do |(T1 ∩ L1 ) ∪ V1 | ≤ |V |. (1.3) 13 Vì vậy từ (1.2) và (1.3) ta được: 1 2 1 1 |T1 ∩ L1 ∩ V1 | ≥ |T | + |V | − |V | = (|T | − |V |) ≥ 0. 3 3 3 3 (1.4) Hiển nhiên: T ∩ L ∩ S ∩ V = T 1 ∩ L1 ∩ V 1 . (1.5) Từ (1.4) và (1.5) ta có điều phải chứng minh là |T ∩ L ∩ V ∩ S| > 0. Vậy trong lớp học nói trên có ít nhất một học sinh đạt điểm giỏi ở cả bốn môn Toán, Vật lý, Văn, Lịch sử. 1.4 Hàm sinh Do hàm sinh và vấn đề liên quan đến hàm sinh là vô cùng phong phú, theo hướng nghiên cứu của đề tài, luận văn quan tâm đến hàm sinh đa thức và lũy thừa. 1.4.1 Định nghĩa Định nghĩa 1.4.1 Hàm sinh (GeneratingFunctions) của dãy số thực {an } là hàm số được xác định bởi G(x) = a0 + a1 x + a2 x2 + · · · + an xn + · · · . Định nghĩa 1.4.2 Cho dãy số thực {an }. Hàm số cho bởi công thức ∞ X xn G(x) = an n! n=0 được gọi là hàm sinh dạng mũ của dãy {an }. 1.4.2 Các định lý và mệnh đề Định lý 1.4.3 Định lý về khai triển Taylor Cho hàm số f (x) có đạo hàm đến cấp n + 1 trong một khoảng chứa x0 và x. Khi đó ta có khai triển f (x) = f (x0 )+ . f 0 (x0 ) f 00 (x0 ) f (n+1) (x0 ) (x−x0 )+ (x−x0 )2 +· · · .+ (x−x0 )(n+1) +Rn (x) 1! 2! (n + 1)! 14 Với Rn (x) là phần dư bậc n. Đặc biệt khi x0 = 0 ta có: f 0 (0) f 00 (0) 2 f (n+1) (0) (n+1) f (x) = f (0) + x+ x + ··· . + (x) 1! 2! (n + 1)! Mệnh đề 1.4.4 Cho hàm sinh G(x) = (1 + x + x2 + · · · )n . k (i) Đặt ak là hệ số của xk trong khai triển của G(x) thì ak = Ck+n−1 . (ii) (1 − xm )n = 1 − Cn1 xm + Cn1 x2m − · · · + (−1)m xmn . Mệnh đề 1.4.5 Cho hai hàm sinh của hai dãy {an }, {bn } lần lượt là: A(x) = a0 + a1 x + a2 x2 + · · · , B(x) = b0 + b1 x + b2 x2 + · · · . Đặt G(x) = A(x)B(x) + a0 b0 + (a0 b1 + a1 b0 )x + (a0 b2 + a1 b1 + a2 b0 )x2 + · · · Khi đó hệ số của xk trong khai triển của G(x) là a0 bk + a1 bk−1 + a2 bk−2 + · · · + ak−2 b2 + ak−1 b1 + ak b0 . Mệnh đề 1.4.6 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 rời nhau thì hàm sinh cho cách chọn các phần tử từ tập A ∪ B là A(x)B(x). Định lý 1.4.7 Định lý RUF (Root of Unity Filter). Cho số nguyên 2π 2π dương n, định nghĩa ε = cos + i sin . n n 2 Xét đa thức F (x) = a0 + a1 x + a2 x + · · · . Bậc n. Khi đó a0 + an + a2n + · · · =  1 F (1) + F (ε) + F (ε2 ) + · · · + F (εn−1 ) . n Định lý 1.4.8 Cho p là số nguyên tố, đặt ε = cos 2π 2π + i sin . p p Khi đó nếu a0 + a1 ε + a2 ε2 + · · · ap−1 εp−1 = 0 15 thì a0 = a1 = a2 = . . . = ap−1 . 16 Chương 2 Vận dụng phương pháp đếm vào giải toán 2.1 2.1.1 Vận dụng phương pháp truy hồi Ý tưởng Đối với nhiều bài toán đếm xuất hiện trong các kỳ thi Quốc gia, Quốc tế. . . thì việc đếm trực tiếp các đối tượng vô cùng khó khăn. Nếu ta xây dựng được mối quan hệ truy hồi giữa số lượng các đố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ì có thể đưa về đếm số đối tượng trong nhóm với số đối tượng nhỏ và việc đếm số trong nhóm đối tượng này đơn giản hơn. Định nghĩa 2.1.1 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 dãy. 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. 2.1.2 Một số ví dụ Ví dụ 2.1.2 Cho số nguyên dương n và S = {1, 2, . . . , n}. Tìm số các tập con (kể cả tập rỗng) của S mà không chứa hai số nguyên dương liên tiếp. Lời giải: Gọi xn là số phải tìm. Dễ thấy x1 = 2, x2 = 3, x3 = 5. Chẳng hạn với n = 3 có 5 tập con thỏa là ∅; {1}; {2}; {3}; {1; 3}. Gọi Tn là họ các tập con có tính chất đã nêu. Mỗi tập A ∈ Tn+2 gồm hai loại: loại 1 gồm các tập chứa n + 2; loại 2 gồm các tập không chứa n + 2. Nếu A là tập loại 1 thì A không chứa n + 1. Do đó nếu bỏ đi 17 khỏi A phần tử n + 2 ta được một tập con của Tn . Ngược lại với mỗi tập con B của Tn thì tập A = B ∪ {n + 2} là tập loại 1 của Tn+2 . Thế thì số tập loại 1 là xn . Mỗi tập loại 2 rõ ràng là một tập con của Tn+1 và ngược lại. Do đó số tập loại 2 là xn+1 . Dẫn đến việc ta có mối quan hệ sau: xn+2 = xn+1 + xn . (2.1) (2.1) chính là công thức truy hồi, cho chúng ta xác định được số lượng các phần tử theo công thức truy hồi đó. Mặt khác, đối với dãy Fibonacci {Fn } ta có: Fn+2 = Fn+1 + Fn . Vì x1 = F3 = 2, x2 = F4 = 3, x3 = F5 = 5 ta suy ra: xn = Fn+2 . Vậy xn = Fn+2 = √ ! √ !n+2 1− 5 1+ 5 − 2 2 √ . 5 Ví dụ 2.1.3 (Việt nam MO 2015). Cho số nguyên dương k. Tìm các số tự nhiên n không vượt quá 10k thỏa mãn đồng thời: (i) n chia hết cho 3. (ii) Các chữ số của n biểu diễn trong hệ thập phân thuộc tập {2; 0; 1; 5}. Lời giải: Vì 10k không chia hết cho 3 nên ta chỉ cần xét các số từ 0 đến 99 . . . 9 (k chữ số 9). Do đó, các số cần tìm có dạng: a1 a2 . . . ak (ai ∈ {2; 0; 1; 5}) để các số này chia hết cho 3 thì khi và chỉ khi a1 + a2 + ...ak chia hết cho 3. Điều này gợi cho ta ý tưởng phân hoạch với i = 0, 1, 2 có: ( ) n X A(n; i) = (a1 ; a2 ; ...an )|aj ∈ {2; 0; 1; 5}; aj ≡ i(mod3) . j=1 18 Khi đó, đặt an = |A(n; 0)|; bn = |A(n; 1)|; cn = |A(n; 2)|. Thì số các số cần tìm chính là: an . Dễ dàng kiểm tra được: a1 = 1; b1 = 1; c1 = 2. Xét phần tử (a1 ; a2 ; . . . ; an+1 ) ∈ A(n + 1; 0) có: an+1 = 0 → (a1 ; a2 ; . . . ; an ) ∈ A(n; 0) an+1 ∈ {2; 5} → (a1 ; a2 ; . . . ; an ) ∈ A(n; 1) an+1 = 1 → (a1 ; a2 ; . . . ; an ) ∈ A(n; 2). Suy ra: an+1 = an + 2bn + cn . (2.2) Hoàn toàn tương tự với dãy bn = |A(n; 1)|; cn = |A(n; 2)|. Ta suy ra: bn+1 = an + bn + 2cn (2.3) cn+1 = 2an + bn + cn . (2.4) và Từ đây ta tính được: a2 = 5; b2 = 6; c2 = 5; a3 = 22; b3 = 21; c3 = 21. Cộng các vế của (2.2); (2.3) và (2.4) ta suy ra: an+1 + bn+1 + cn+1 = 4(an + bn + cn ) → an + bn + cn = 4n . Lấy (2.2) trừ (2.3); (2.3) trừ (2.4); (2.4) trừ (2.2) ta thu được: an+1 − bn+1 = bn − cn ; bn+1 − cn+1 = cn − an ; cn+1 − an+1 = an − bn → an+3 − bn+3 = bn+2 − cn+2 = cn+1 − an+1 = an − bn . Tương tự ta cũng có: bn+3 − cn+3 = bn − cn ; cn+3 − an+3 = cn − an . 19 Sử dụng các giá trị ban đầu ta suy ra: k ≡ 0( mod 3) → bk = ck = ak − 1 k ≡ 1( mod 3) → ak = bk = ck − 1 k ≡ 2( mod 3) → ak = ck = bk − 1 từ đây kết hợp đẳng thức ak + bk + ck = 4k ta có: 4k − 1 + Nếu k không chia hết cho 3 thì: ak = . 3 4k + 2 + Nếu k chia hết cho 3 thì: ak = . 3 Ví dụ 2.1.4 (BRVT 2010). 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 liền kề nhau. Lời giải: Kí hiệu Xn là tập các số tự nhiên có n chữ số thỏa mãn đề bài. An ; Bn là các tập con của Xn 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ó Xn = An ∪ Bn ; An ∩ Bn = ∅ → |Xn | = |An | + |Bn |. Lấy một phần tử thuộc Xn+1 bỏ đi chữ số tận cùng ta được một phần tử của Xn ; ngược lại lấy một phần tử của Xn ta có hai trường hợp: + Nếu tận cùng nhỏ hơn 7 (thuộc An ) thì chỉ có 1 cách thêm vào chữ số cuối để được một phần tử của An+1 và có đúng 3 cách thêm vào chữ số cuối để được một phần tử của Bn+1 . + Nếu tận cùng lớn hơn 6 (thuộc Bn ) thì có 5 cách thêm vào chữ số cuối để được một phần tử của An+1 và đúng 3 cách thêm vào chữ số cuối để được một phần tử của Bn+1 . Từ các lập luận trên ta suy ra:  |A | = |A | + 5|B | n+1 n n |Bn+1 | = 3|An | + 3|Bn |