ĐẠ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 4
1 Một số kiến thức chuẩn bị
1.3 Nguyên lý bù trừ, thêm bớt
6 1.1 Nguyên lý cộng . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Nguyên lý nhân . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . 8 . . . . . . . . . . . . . . . . 9 9 1.3.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 1.3.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 13 . . . . . . . . . . . . . . 13 1.4.2 Các định lý và mệnh đề
2 Vận dụng phương pháp đếm vào giải toán
16 2.1 Vận dụng phương pháp truy hồi . . . . . . . . . . . . . . 16 2.1.1 Ý tưởng . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . 16 2.2 Vận dụng phương pháp song ánh . . . . . . . . . . . . . 23 2.2.1 Ý tưởng . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . 24 2.3 Vận dụng phương pháp đa thức và số phức . . . . . . . . 30 2.3.1 Ý tưởng . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4 Vận dụng phương pháp sử dụng hàm sinh . . . . . . . . 36 2.4.1 Ý tưởng . . . . . . . . . . . . . . . . . . . . . . . 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
n (cid:91)
n (cid:91)
Cho Ai, i = 1, n là các tập rời nhau. Khi đó
i=1
i=1
= |Ai|. Ai (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
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| − | ¯A|.
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 Nguyên lý nhân
1.2.1 Đị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 (cid:89)
n (cid:89)
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 đó:
i=1
i=1
= Ai |Ai|. (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
1.2.2 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.
1 .P α2
2
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.
1 .P β2
2
. . . P βn n
Ví dụ 1.2.4 Cho n là một số nguyên dương. Xét A = P α1 . . . P αn 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 = P β1 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 ¯A = X/A. Khi đó ta có:
| ¯A| = |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−1Nk
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à
1≤i1 (cid:88) Nm = |Ai1 ∩ Ai2 ∩ . . . ∩ Aim|. Bây giờ ta đồng nhất tập Am (1 ≤ m ≤ k) với tính chất Am cho trên
tập hữu hạn U nào đó và đếm xem có bao nhiêu phần tử của U sao
cho không thỏa mãn bất kỳ một tính chất Am nào. Gọi ¯N là số cần
đếm, N là số phần tử của U . Ta có: ¯N = N − |A1 ∪ A2 ∪ . . . ∪ Ak| = N − N1 + N2 − · · · + (−1)kNk n
(cid:91) trong đó Nm là tổng các phần tử của U thỏa mãn m tính chất lấy từ
k tính chất đã cho. Công thức này được gọi là nguyên lý bù trừ. Nó
cho phép tính ¯N qua các Nm trong trường hợp các số này dễ tính toán
hơn.
Tổng quát: cho n tập hợp Ai, i = 1, n (n ≥ 2). Khi đó: k
(cid:92) m=1 i=1 1≤i1≤i2<···≤ik≤n (cid:88) = . Ai Aim (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) 10 1.3.2 Ví dụ Ví dụ 1.3.2 Một chuyến bay có 67 hành khách. Trong đó có 47 người
sử dụng tốt tiếng Anh, 35 người sử dụng tốt tiếng Đức, 20 người sử
dụng tốt tiếng Pháp. Hơn nữa có 23 người sử dụng tốt hai thứ tiếng
Anh và Đức, 12 người sử dụng tốt hai tiếng Anh và Pháp, 11 người sử
dụng tốt hai tiếng Đức và Pháp. Và có 5 người sử dụng tốt cả ba thứ
tiếng. Tìm số hành khách không sử dụng được bất kì ngoại ngữ nào?
Lời giải. Gọi A, B, C lần lượt là các hành khách sử dụng tốt ngoại
ngữ là tiếng Anh, tiếng Đức, tiếng Pháp. Số các hành khách biết ít
nhất một ngoại ngữ là: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C| = 47 + 35 + 20 − 23 − 12 − 1 + 5 = 61. Vậy số hành khách không sử dụng được bất kì ngoại ngữ nào là:
67 − 61 = 6. Ví dụ 1.3.3 Xét tập hợp X = {1; 2; 3; . . . ; 2009}.
Đặt A = {x ∈ X : x ≡ 1 mod (29)}.
a) Tính |A|.
b) Tìm số tập con B ∈ X sao cho B ∩ A (cid:54)= ∅.
Lời giải. a) Xét x ∈ X, ta có: x ≡ 1 mod (29) ⇒ x = 1 + 29t. Ta có: 1 ≤ x ≤ 2009 ⇒ 0 ≤ t ≤ 69 Vậy |A| = 70.
b) Gọi P (X) là tập bao gồm tất cả các tập con của X, M là tập các tập
con B của X sao cho B ∩ A (cid:54)= ∅. Khi đó: P (X)\M là tập các tập con
B của X mà B ∩ A (cid:54)= ∅ hay B = X\A. Suy ra P (X)\M = P (X\A).
Do đó, M = |P (X)| − |P (X\A)| = 22009 − 22009−70 = 22009 − 21939. Ví dụ 1.3.4 Trong một đề thi chọn đội tuyển quốc gia có ba câu: một
câu về số học, một câu về đại số và một câu về hình học. Trong 40 thí 11 sinh dự thi có 25 thí sinh làm được câu số học, 30 thí sinh làm được
câu đại số và 15 thí sinh làm được câu hình học. Ngoài ra số thí sinh
làm được cả hai câu số học và đại số là 20, số thí sinh làm được cả hai
câu số học và hình học là 5, số thí sinh làm được cả hai câu đại số và
hình học là 10. Biết rằng không có thí sinh không làm được câu nào.
Hỏi có bao nhiêu thí sinh làm được cả ba câu?
Lời giải. Gọi A, B, C là tập hợp các thí sinh làm được câu số học,
đại số và hình học. Theo đề ta có: |A| = 25, |B| = 30, |C| = 15, |A∩B| = 20, |B ∩C| = 10, |C ∩A| = 5. Vì không có thí sinh không làm được câu nào nên |A ∪ B ∪ C| = 40.
Áp dụng nguyên lý thêm bớt ta có: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|. Suy ra 40 = 25 + 30 + 15 − 20 − 10 − 5 + |A ∩ B ∩ C| ⇒ |A ∩ B ∩ C| = 5. Vậy có 5 thí sinh làm được cả 3 câu. i=1 Ak.
k=1 |Ak| − (cid:80) k Ví dụ 1.3.5 (IMO 1989). Cho n số nguyên dương. Một hoán vị
x1; x2; . . . ; x2n của tập {1; 2; . . . ; 2n} được gọi là có tính chất T nếu
tồn tại i ∈ {1; 2; . . . ; 2n − 1} sao cho |xi − xi+1| = n. Chứng minh rằng
với mọi n nguyên dương, số các hoán vị có tính chất T lớn hơn số các
hoán vị không có tính chất T .
Lời giải. Ta có: |xi − xi+1| = n nên nếu xi = k thì xi+1 = k + n. Với
mỗi số k ∈ {1; 2; . . . ; n}, ký hiệu Ak là tập các hoán vị mà trong đó có
hai phần tử k và k + n đứng liên tiếp. Gọi A là tập các hoán vị có tính
chất T . Ta có: A = (cid:83)n
Do đó: |A| ≥ (cid:80)n (cid:84) Ah|. Dễ dàng chứng minh được: |Ak| = 2(2n − 1)!, |Ak ∩ Ah| = 4(2n − 2)!. Từ đó: (cid:20) = 2n2(2n − 2)! > (cid:21)
4 . |A| ≥ (2n − 2)! n.2(2n − 1) − n(n − 1)
2 (2n)!
2 12 số học sinh đạt điểm giỏi ở môn Toán cũng đồng thời đạt điểm - Hơn 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
3 giỏi ở môn Vật lý; - Hơn số học sinh đạt điểm giỏi ở môn Vật lý cũng đồng thời đạt 2
3 điểm giỏi ở môn Văn; - Hơn số học sinh đạt điểm giỏi ở môn Văn cũng đồng thời đạt điểm 2
3 giỏi ở môn Lịch sử; - Hơn số học sinh đạt điểm giỏi ở môn Lịch sử cũng đồng thời đạt 2
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ó: |T |; |L|; |V |. |T1| > |L1| > |V1| > 2
3 2
3 2
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ó (1.1) |T1 ∩ L1| = |T1| + |L1| − |T1 ∪ L1|. Vì T1 ∪ L1 ⊂ L nên |T1 ∪ L1| ≤ |L|. Do đó từ (1.1) ta được: |T | + |L| − |L| = |T | − |L| ≥ |T | (do |T | ≥ |L|). |T1 ∩ L1| > 2
3 2
3 2
3 1
3 1
3 (1.2) Lại có (1.3) |T1 ∩ L1 ∩ V1| = |T1 ∩ L1| + |V1| − |(T1 ∩ L1) ∪ V1|. Vì L1 ⊂ V nên T1 ∩ L1 ⊂ V.
Do |(T1 ∩ L1) ∪ V1| ≤ |V |. 13 Vì vậy từ (1.2) và (1.3) ta được: |T | + |V | − |V | = (|T | − |V |) ≥ 0. (1.4) |T1 ∩ L1 ∩ V1| ≥ 1
3 1
3 2
3 1
3 Hiển nhiên: (1.5) T ∩ L ∩ S ∩ V = T1 ∩ L1 ∩ V1. 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 + a1x + a2x2 + · · · + anxn + · · · . ∞
(cid:88) Định nghĩa 1.4.2 Cho dãy số thực {an}. Hàm số cho bởi công thức n=0 G(x) = an xn
n! đượ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 (x−x0)+ (x−x0)2+· · · .+ f (x) = f (x0)+ (x−x0)(n+1)+Rn(x) f (cid:48)(x0)
1! f (cid:48)(cid:48)(x0)
2! f (n+1)(x0)
(n + 1)! . 14 Với Rn(x) là phần dư bậc n. Đặc biệt khi x0 = 0 ta có: k+n−1. f (x) = f (0) + x + x2 + · · · . + (x)(n+1) f (cid:48)(0)
1! f (cid:48)(cid:48)(0)
2! f (n+1)(0)
(n + 1)! nx2m − · · · + (−1)mxmn. nxm + C 1 Mệnh đề 1.4.4 Cho hàm sinh G(x) = (1 + x + x2 + · · · )n.
(i) Đặt ak là hệ số của xk trong khai triển của G(x) thì ak = C k
(ii) (1 − xm)n = 1 − C 1 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 + a1x + a2x2 + · · · , B(x) = b0 + b1x + b2x2 + · · · . Đặt G(x) = A(x)B(x) + a0b0 + (a0b1 + a1b0)x + (a0b2 + a1b1 + a2b0)x2 + · · · Khi đó hệ số của xk trong khai triển của G(x) là a0bk + a1bk−1 + a2bk−2 + · · · + ak−2b2 + ak−1b1 + akb0. 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 + i sin . 2π
n . Bậc n. Khi đó 2π
dương n, định nghĩa ε = cos
n
Xét đa thức F (x) = a0 + a1x + a2x2 + · · · (cid:2)F (1) + F (ε) + F (ε2) + · · · + F (εn−1)(cid:3) . a0 + an + a2n + · · · = 1
n + i sin . Định lý 1.4.8 Cho p là số nguyên tố, đặt ε = cos 2π
p 2π
p Khi đó nếu a0 + a1ε + a2ε2 + · · · ap−1εp−1 = 0 15 thì a0 = a1 = a2 = . . . = ap−1. 16 2.1 Vận dụng phương pháp truy hồi 2.1.1 Ý 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: (2.1) xn+2 = xn+1 + xn. (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 √ √ (cid:33) (cid:32) (cid:33)n+2 (cid:32) 5 5 − 1 +
2 1 −
2 √ . xn = Fn+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: a1a2 . . . 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
(cid:88) (cid:40) (cid:41) j=1 A(n; i) = . (a1; a2; ...an)|aj ∈ {2; 0; 1; 5}; aj ≡ i(mod3) 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: (2.2) an+1 = an + 2bn + cn. Hoàn toàn tương tự với dãy bn = |A(n; 1)|; cn = |A(n; 2)|. Ta suy ra: (2.3) bn+1 = an + bn + 2cn và (2.4) cn+1 = 2an + bn + cn. 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ó: . + Nếu k không chia hết cho 3 thì: ak = 4k − 1
3 . + Nếu k chia hết cho 3 thì: ak = 4k + 2
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:
|An+1| = |An| + 5|Bn| |Bn+1| = 3|An| + 3|Bn| 20 (2.5) → |An+1| + |Bn+1| = 4|An| + 8|Bn| = 4(|An| + |Bn|) + 4|Bn|
→ |An+1| + |Bn+1| = 4(|An| + |Bn|) + 12(|An−1| + |Bn−1|)
→ |Xn+1| = 4|Xn| + 12|Xn−1|. (2.5) 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 đó.
Dễ thấy |X1| = 8. Ta tính X2. Xét n ∈ |X2| → n = a, b : a; b ∈ {2; 3; 4; 5; 6; 7; 8; 9}. + Nếu a ∈ {2; 3; 4; 5; 6} thì b có 4 cách chọn. + Nếu a ∈ {7; 8; 9} thì b có 8 cách chọn.
Vì thế |X2| = 5.4 + 3.8 = 44. Do đó ta dễ dàng tìm được: (cid:2)15.6n−1 + (−2)n−1(cid:3) . |Xn| = 1
2 Nhận xét 2.1.5 Cả hai ví dụ trên đều dùng dãy phụ để tìm ra công
thức truy hồi, thế nhưng Ví dụ 2.1.3 ta không tìm ra công thức liên hệ
giữa đại lượng thứ n với đại lượng trước đó, còn Ví dụ 2.1.4 thì ta tìm
mối liên hệ giữa đại lượng thứ n + 2 với đại lượng thứ n + 1 và thứ n.
Có thể thấy rằng tư tưởng của bài toán đếm bằng hai cách rất rõ ràng
và ứng dụng của nó khá rộng rãi. Ví dụ 2.1.6 (Bulgaria 1995). Cho số nguyên n ≥ 2. Tìm số các
hoán vị (a1, a2, . . . , an) của n số nguyên dương đầu tiên sao cho tồn tại
duy nhất một chỉ số 1 ≤ i ≤ n − 1 mà ai > ai+1.
Lời giải: Gọi Sn là hoán vị thỏa mãn đề bài. Xét hai trường hợp: - Nếu an = n thì (a1, a2, . . . , an−1) là hoán vị của (1, 2, ..., n − 1) và thỏa
mãn điều kiện tồn tại chỉ số 1 ≤ i ≤ n − 2 mà ai > ai+1. Số hoán vị
này chính là Sn−1. n−1 cách chọn. - Nếu an (cid:54)= n thì phải tồn tại một chỉ số 1 ≤ i ≤ n − 1 mà ai = n.
Khi đó ta cần chọn các chỉ số cho i − 1 vị trí trước ai và n − i vị trí
sau ai. Để ý rằng với mỗi cách chọn như thế thì các số của hai dãy
này sẽ được xếp theo thứ tự giảm dần vì đã có một chỉ số i thỏa mãn
ai = n > ai+1 ∈ {1, 2, 3, . . . , n − 1}. Ứng với mỗi cách chọn có đúng
một dãy thỏa mãn yêu cầu bài toán nên có tất cả C i−1 21 n−1 − 1 = n−1 = n−1
(cid:80)
i=1 n−1
(cid:80)
i=0 Số các hoán vị trong trường hợp này là C i−1 C i 2n−1 − 1. Ta cũng tính được S2 = 1 và hai trường hợp trên rời nhau
nên có công thức truy hồi:
S2 = 1
Sn = Sn−1 + 2n−1 − 1, ∀n ≥ 3 n
(cid:88) n−1
(cid:88) suy ra i=3 i=2 Si = 2i − (n − 2) ⇔ Sn = S2 + 2n − 3 − (n − 2) = 2n − n − 1. Vậy số hoán vị cần tìm là 2n − n − 1. Ví dụ 2.1.7 (Austrian MO 2012). Xét một băng giấy được đánh
dấu từ trái sang phải theo thứ tự tăng dần từ 1 đến n. Tìm số cách tô
màu các ô của băng giấy thỏa mãn các điều kiện sau: - Mỗi ô như vậy được tô bởi một trong ba màu 1, 2 hoặc 3. - Ô mang số thứ tự chẵn thì có thể được tô bằng bất kỳ màu nào. - Ô mang số thứ tự lẻ thì chỉ được tô bởi màu lẻ, nghĩa là màu 1 hoặc màu 3. - Hai ô nằm ở cạnh nhau phải được tô màu khác nhau. Lời giải: Gọi Sn, n ≥ 1 lần lượt là số cách tô màu dãy ô gồm n ô và
an, bn, cn là số cách tô màu dãy ô gồm n ô mà ô thứ n lần lượt mang
mầu số 1, 2 và 3. Xem xét các trường hợp sau:
(i) Trường hợp 1: n = 2k + 1 với k ∈ Z, k ≥ 0. Vì ô lẻ chỉ được tô
màu lẻ nên ta có S2k+1 = a2k+1 + c2k+1. Xét ô thứ 2k + 3 , xảy ra các khả năng sau: - Nếu ô thứ 2k + 3 được tô màu 1 thì ô thứ 2k + 2 có thể được tô màu 1 hoặc mầu 3. - Nếu ô thứ 2k + 3 được tô màu 3 thì ô thứ 2k + 2 có thể được tô màu 2 hoặc mầu 1. 22 Tiếp tục xét ô thứ 2k + 2: - Nếu ô thứ 2k + 2 được tô màu 2 thì ô thứ 2k + 1 có thể được tô màu 1 hoặc mầu 3. - Nếu ô thứ 2k + 2 được tô bằng 1 trong hai màu 1 hoặc 3 thì ô thứ 2k + 1 chỉ có thể được tô bằng màu còn lại. Kết hợp những nhận xét trên ta suy ra: S2k+3 = a2k+3 + c2k+3 = c2k+2 + b2k+2 + a2k+2 + b2k+2
= a2k+1 + 2(a2k+1 + b2k+1) + c2k+1
= 3S2k+1. Mặt khác, dễ dàng tính được S1 = 2 nên suy ra với n = 2k + 1 thì số
cách tô màu thỏa mãn đề bài là 2.3k.
(ii) Trường hợp 2: n = 2k với k ∈ Z+.
Lập luận tương tự như trường hợp trên ta thu được số cách tô màu
thỏa mãn đề bài cho trường hợp này là 4.3k−1. Ví dụ 2.1.8 (Baltic 1995). Cho tập X = {1, 2, 3, . . . , 1995}. Hỏi có
bao nhiêu cách chia tập X thành 3 tập con khác rỗng sao cho trong
mỗi tập không có hai phần tử nào liên tiếp.
Lời giải: Gọi S(n) là số cách chia tập {1, 2, 3, . . . , n} thành 3 tập thỏa
mãn yêu cầu bài toán. Từ S(n) tạo ra tập S(n + 1) bằng cách thêm
phần tử n + 1 vào S(n) thỏa mãn yêu cầu bài toán.
Ta có S(n + 1) = 2S(n) + 1, ∀n ≥ 3. Từ đó ta có: S(n) = 2n−3S(3) + (1 + 2 + 22 + · · · + 2n−4) = 2n−2 − 1. Vậy số cách chia cần tìm là S(1995) = 21993 − 1. Ví dụ 2.1.9 (IMO 1996). Cho bảng ô vuông n × n với n > 1. Hỏi
có bao nhiêu cách đánh dấu các ô vuông trong bảng sao cho trong mỗi
hình vuông 2 × 2 có đúng 2 ô vuông được đánh dấu. (Hai cách đánh
dấu được coi là khác nhau nếu có một ô vuông nào đó mà trong cách 23 này thì được đánh dấu còn trong cách kia thì không).
Lời giải: Gọi Sn là số cách đánh dấu trong bảng n × n. Xét tập T gồm
các ô vuông nằm trong cột cuối cùng (tính từ phải sang) và hàng cuối
cùng (tính từ trên xuống), ta gọi An là các cách đánh dấu mà có hai
ô vuông kề nhau trong T cùng được đánh dấu hoặc cùng không được
đánh dấu và Bn là các cách đánh dấu mà các ô vuông trong T được
đánh dấu xen kẽ. Rõ ràng mỗi cách đánh dấu thuộc Bn sẽ ứng với một cách đánh dấu
thuộc Bn−1, còn mỗi cách đánh dấu thuộc An sẽ ứng với mỗi cách đánh
dấu thuộc An−1 và một cách thuộc Bn−1. (Điều này được suy ra khi xét bảng ô vuông (n − 1) × (n − 1) từ bảng n × n sau khi bỏ T ).
Từ đó ta có: |Bn| = |Bn−1|, |An| = |An−1| + |Bn−1|, n > 2. Mà |Sn| = |An| + |Bn|, ∀n > 1 nên Sn = 2Sn−1 − Sn−2, ∀n > 3. Dễ
thấy S2 = 6, S3 = 14.
Chứng minh bằng quy nạp ta được: Sn = 8n − 10, ∀n ≥ 2. 2.2 Vận dụng phương pháp song ánh 2.2.1 Ý tưởng 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 f : A → 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
bằng cách xây dựng song ánh từ A vào một tập hợp B mà tập hợp B
thỏa mãn 1 trong 2 điều kiện 1) Nếu số phần tử của B đã biết; 2) Hoặc việc đếm số phần tử của B là đơn giản hơn. 24 Khi đó thay cho việc đếm trực tiếp số phần tử của A ta đi đếm số
phần tử của B rồi suy ra A. Tính chất: Cho A, B là hai tập hợp hữu hạn và ánh xạ f : A → B. Khi đó: 1) Nếu f là đơn ánh thì |A| ≤ |B|; 2) Nếu f là toàn ánh thì |A| ≥ |B|; 3) Nếu f là song ánh thì |A| = |B|. 2.2.2 Một số ví dụ ...999 và các chữ số của N thuộc {1, 2, , 3, 4, 5, 6, 7, 8}. ...99 nên f : M → M là song ánh. Ví dụ 2.2.1 Hỏi trung bình cộng các số N gồm 2002 chữ số thỏa mãn
N
Lời giải: Gọi M là tập hợp các số N thỏa mãn điều kiện đề bài. Xây
dựng ánh xạ f như sau:
Nếu N = a1a2 . . . a2002 thì f (N ) = b1b2 . . . b2002 với bi = 9 − ai.
Do N + f (N ) = 99 . . . 9
(cid:124) (cid:123)(cid:122) (cid:125)
2002 Từ đó (cid:88) (cid:88) 2 N = . N ∈M N ∈M (N + f (N )) = |M |.99 . . . 9
(cid:124) (cid:123)(cid:122) (cid:125)
2002 . Suy ra trung bình cộng các số N là 102002 − 1
2 Ví dụ 2.2.2 Cho X = {a1, a2, . . . , an}. với n là số tự nhiên dương, k
là số tự nhiên thỏa mãn k ≤ n. Đặt S = {(ai1, ai2, . . . , aik) | ai1, ai2, . . . , aik ∈ X; 1 ≤ i1 ≤ i2 ≤ · · · ≤ ik ≤ n} . Tính số phần tử của tập S.
Lời giải: Ta có (ai1, ai2, . . . , aik) → (i1, i2, . . . , ik) là một song ánh từ
tập S vào tập S1 gồm các bộ (i1, i2, . . . , ik) với 1 ≤ i1 ≤ i2 ≤ · · · ≤
ik ≤ n nên |S| = |S1|.
Khó khăn gặp phải khi đếm các bộ của tập S1 là các số i1, i2, . . . , ik
có thể bằng nhau. Do đó ta tìm cách phá bỏ các dấu “=” ở trong bất
đẳng thức 1 ≤ i1 ≤ i2 ≤ · · · ≤ ik ≤ n. Tức là, ta đưa về đếm các bộ
(j1, j2, . . . , jk) với 1 ≤ j1 < j2 < · · · < jk ≤ n.
Để thực hiện được điều đó ta tịnh tiến các chỉ số i1, i2, . . . , ik mỗi chỉ 25 số tăng thêm một đơn vị so với chỉ số trước nó. Dẫn tới ta đi xét tương
ứng sau: Xét tương ứng (i1, i2, . . . , ik) ∈ S1 → (i1, i2 + 1, . . . , ik + k − 1). Rõ ràng, đây là một song ánh từ tập S1 vào tập S2 là tập gồm các bộ
(j1, j2, . . . , jk) sao cho j1, j2, . . . , jk ∈ {1, 2, . . . , n + k − 1} và j1 < j2 < . . . < jk.
Suy ra n+k−1. |S1| = |S2| = C k n+k−1. Hệ quả 2.2.3 Số nghiệm nguyên không âm của phương trình: x1 +
x2 + · · · + xk = n là C k Hệ quả 2.2.4 Số nghiệm nguyên dương của phương trình: x1 + x2 +
· · · + xk = n là C k−1
n−1. Ví dụ 2.2.5 Trong một giải bóng đá có 10 trận đấu và được diễn ra
trong vòng 30 ngày. Hỏi ban tổ chức có bao nhiêu cách sắp xếp các
trận bóng đá sao cho hai trận đấu kế nhau phải cách nhau ít nhất một
ngày.
Lời giải:
Cách 1: Giả sử trận đấu thứ i được xếp vào ngày thứ xi. Khi đó mỗi
cách xếp các trận đấu tương ứng với một bộ 10 số (x1, x2, . . . , x10) thỏa
mãn các điều kiện sau 1 ≤ x1 < x2 < x3 < · · · < x10 ≤ 30. xi+1 − xi ≥ 2 với mọi i = 1, 29.
Nếu các bộ (x1, x2, . . . , x10) chỉ thỏa mãn điều kiện thứ nhất thì việc
đếm trở lên đơn giản. Khó khăn ở đây là điều kiện thứ 2. Điều kiện
này bắt buộc các số x1, x2, . . . , x10 không có hai số nào là hai số tự
nhiên liên tiếp, do đó ta tìm cách chuyển về hai số kề nhau có thể là
hai số tự nhiên liên tiếp để đếm.
Ta có x2 − x1 ≥ 2 ⇔ x2 − x1 > 1 ⇔ x2 − 1 > x1 nên hai số x2 − 1 và 26 x1 có thể là hai số tự nhiên liên tiếp. Dẫn đến, ta sẽ chuyển bộ (x1, x2, . . . , x10) về bộ (x1, x2 − 1, x3 − 2, . . . , x10 − 9). Gọi A là tập các bộ (x1, x2, . . . , x10) thỏa mãn các điều kiện trên B = {(y1, y2, . . . , y10) | 1 ≤ y1 < y2 < · · · < y10 ≤ 21}. Xét ánh xạ f : A → B được xác định như sau f (x1, x2, . . . , x10) = (x1, x2 − 1, x3 − 2, . . . , x10 − 9). Ta chứng minh được f là một song ánh. Do đó 21 = 352716. |A| = |B| = C 10 Cách 2: Giả sử giữa ngày thứ nhất đến ngày trận đấu thứ nhất có x1
ngày, giữa trận đấu thứ nhất và trận đấu thứ hai có x2 ngày,. . ., giữa
trận đấu thứ 10 đến ngày thứ 30 có x11 ngày.
Khi đó mỗi cách xếp 10 trận đấu tương ứng với một bộ (x1, x2, . . . , x11)
thỏa mãn các điều kiện sau x1, x11 ≥ 0; x2, x3, . . . , x10 ≥ 1
x1 + x2 + . . . + x11 = 30 − 10 = 20. Đặt y1 = x1, y11 = x11, yi = xi − 1, ∀i = 2, 10.
Khi đó mỗi bộ (x1, x2, . . . , x11) tương ứng với một bộ (y1, y2, . . . , y11)
thỏa mãn y1, y2, . . . , y11 ≥ 0 và 21 = 352716 cách xếp 10 trận đấu thỏa mãn các yêu cầu bài (2.6) y1 + y2 + · · · + y11 = 11. Số các bộ (y1, y2, . . . , y11) chính là số nghiệm không âm của phương
trình (2.6) và bằng C 11
11+11−1 = C 11
21 .
Vậy có C 11
toán. 27 Nhận xét 2.2.6 Ở một số bài toán ta có thể chỉ ra các song ánh f :
A → B khác nhau, tuy nhiên kết quả của việc đếm số phần tử của tập
B là hoàn toàn trùng khớp. Ví dụ 2.2.7 Cho đa giác đều 2013 đỉnh. Người ta tô 100 đỉnh của đa
giác bởi màu đỏ. Hỏi có bao nhiêu cách tô sao cho giữa hai đỉnh được
tô màu kề nhau có ít nhất 3 đỉnh không được tô màu.
Lời giải: Gọi các đỉnh của đa giác là A1, A2, . . . , A2013. Giả sử tô màu
các đỉnh Ai1, Ai2, . . . , Ai100. Khi đó mỗi cách tô mầu thỏa mãn yêu cầu
bài toán ứng với bộ (i1, i2, . . . , i100) thỏa mãn các điều kiện sau 1 ≤ i1 < i2 < i3 < . . . < i100 ≤ 2013 ik+1 − ik ≥ 4 với ∀k = 1, 2012 và 2013 + i1 − i2013 ≥ 4. Ta thấy ik+1 − ik ≥ 4 ⇔ ik+1 − ik > 3 ⇔ ik+1 − 3 > ik, do đó ta sẽ thay thế các ik bởi ik − 3(k − 1).
Gọi S là tập các bộ (i1, i2, . . . , i100) thỏa mãn các điều kiện nói trên,
S1 là tập các bộ (a1, a2, . . . , a100) thỏa mãn 1 ≤ a1 < a2 < . . . < a100 ≤ 1716
a100 − a1 ≤ 1712. Khi đó ánh xạ f : S → S1 được xác định f (i1, i2, . . . , i100) = (a1, a2, . . . , a100) với ak = ik − 3(k − 1), k = 1, 100. Dễ dàng kiểm chứng được f là một song ánh. Ta xét các trường hợp
sau +) a1 ∈ {1, 2, 3}, đặt bi = ai − a1. Khi đó ánh xạ g đi từ tập S1 vào tập
S2 là tập các bộ (b1, b2, . . . , b100) thỏa mãn 1 ≤ b1 < b2 < . . . < b100 ≤
1712 là một song ánh.
Ta có |S3| = C 100
1713. Vậy 1712 + C 100
1713. |S| = |S2| + |S3| = 3.C 99 28 Ví dụ 2.2.8 Có bao nhiêu chỉnh hợp chập k (a1, a2, . . . , ak) của n số
tự nhiên đầu tiên thỏa mãn ít nhất một trong hai điều kiện sau i) Tồn tại i, j ∈ {1, 2, . . . , k} thỏa mãn ai > aj và i < j. ii) Tồn tại i ∈ {1, 2, . . . , k} sao cho ai − 1 là số lẻ. Lời giải: Gọi S là tập các chỉnh hợp chập k của n số tự nhiên đầu
tiên. Ta có n = |S| = Ak . n!
(n − k)! Gọi A là tập hợp các chỉnh hợp thỏa mãn yêu cầu bài toán B = {a =
(a1, a2, . . . , ak) ∈ S} và các ai thỏa mãn đồng thời hai điều kiện sau (a) ai+1 > ai với mọi i = 1, k − 1. (b) ai − i luôn là số chẵn với mọi i = 1, k. Ta có |A| = |S| − |B|. Ta đi tính |B| =?. n − C k 2 ]
[ n+k 2 ]
[ n+k Với mỗi bộ (a1, a2, . . . , ak) ⊂ {1, 2, 3, . . . , n} thì tồn tại duy nhất một
chỉnh hợp chập k(a1, a2, . . . , ak) thỏa mãn điều kiện (a). Do đó ta chỉ
cần đi phân tích điều kiện (b). vì ai −i là số chẵn khi và chỉ khi ai +i là
số chẵn. Hơn nữa giá trị của ai − i ta khó kiểm soát còn các giá trị của
ai + i chỉ phụ thuộc vào tập {1, 2, 3, . . . , k + n} nên ta xét ánh xạ f từ
tập B vào tập C được xác định bởi f (a1, a2, . . . , ak) = (b1, b2, . . . , bk)
với bi = ai + i và C là tập gồm các bộ (b1, b2, . . . , bk) thỏa mãn bi là
số chẵn ∀i = 1, k và bi ∈ {1, 2, 3, . . . , n + k}. Ta chứng minh được f là
song ánh.
Vì vậy |B| = |C| = C k . Vậy |A| = C k . Ví dụ 2.2.9 (VMO 2002). Cho tập S gồm tất cả các số nguyên trong
đoạn [1, 2002]. Gọi T là tập hợp tất cả các tập con không rỗng của S.
Với mỗi X thuộc T , ký hiệu m(X) là trung bình cộng các phần tử của
X. Tính m = . (cid:80) m(X)
|T | Lời giải: Xét ánh xạ f : T → T như sau: f (X) = {2003 − x | x ∈ X}, ∀X ∈ T. 29 Vì f là song ánh nên m(X) = m(f (X)). Do đó 2m = . ((cid:80) m(X) + m(f (X)))
|T | Mà m(X) + m(f (X)) = 2003 nên m = . 2003
2 Chú ý 2.2.10 Bài toán trên có thể mở rộng bằng thay số 2002 ở đầu
bài thành 2018. n
(cid:88) Ví dụ 2.2.11 (China 1994). Chứng minh rằng: 2n+1, ∀n ∈ Z+. 2 ]
[ n−k
n−k = C 2 k=0 2 n cách chọn và bước 2 có C 2nC [ n−k
2 ]
n−k Lời giải: Ta chọn ra n số từ 2n + 1 số như sau. Trước hết từ 2n + 1 số
ta chia ra n cặp và số x. Sau đó, bước 1: ta chọn ra k cặp rồi từ mỗi
(cid:3) cặp trong n − k cặp còn lại.
cặp chọn ra một số, bước 2: chọn (cid:2) n−k
Ngoài ra số x sẽ được chọn nếu n − k lẻ và sẽ không được chọn nếu
n − k chẵn. Rõ ràng bước 1 có 2kC k
cách
chọn. Lúc này ta chọn được tổng cộng n số, trong đó k chạy từ 0 đến n. Chú ý 2.2.12 Nếu ánh xạ f : A → B là đơn ánh thì |A| ≤ |B|. Để
minh họa cho tính chất đó ta đi xét ví dụ sau đây. Ví dụ 2.2.13 Cho A là tập hữu hạn các số thực dương. Ta định nghĩa
B và C là các tập sau (cid:27) B = x, y ∈ A , C = {xy | x, y ∈ A}. (cid:26)x
y (cid:12)
(cid:12)
(cid:12)
(cid:12) Chứng minh rằng |A|.|B| ≤ |C|2. (cid:27) Lời giải: Giả sử B = , . . . , với các phân số phân biệt. , (cid:26)x1
y1 x2
y2 xk
yk xi
yi Xét ánh xạ f : A × B → C 2 được xác định bởi (cid:19) (cid:18) f z; = (zxi; zyi). xi
yi 30 (cid:18) (cid:19) (cid:18) (cid:19) Xét a = z; , b = z; mà f (a) = f (b), ta có: xi
yi xj
yj
xi = xj ⇒ = ⇒ ⇒ z = z(cid:48) ⇒ a = b. xi
yi xj
yj xiz = xiz(cid:48)
yiz = yiz(cid:48) yi = yj Vậy C là đơn ánh, suy ra |A × B| ≤ |C × C| ⇒ |A|.|B| ≤ |C|2. Ví dụ 2.2.14 (Bakan 1997) Cho m, n là các số nguyên dương
m, n > 1. Xét tập X gồm n phần tử và A1, A2, . . . , Am là m tập con
của X thỏa mãn: với mọi x, y ∈ X, x (cid:54)= y tồn tại tập Ak, 1 ≤ k ≤ m
sao cho x ∈ Ak, y /∈ Ak hoặc x /∈ Ak, y ∈ Ak. Chứng minh n ≤ 2m.
Lời giải: Ta có 2m là số phần tử của tích Đề-các Y = {0, 1}m. Xây
dựng ánh xạ f : X → Y được xác định như sau: với mỗi x ∈ X ta
cho tương ứng y = (x1, x2, . . . , xm) sao cho nếu x ∈ Ak thì xk = 1 và
x /∈ Ak thì xk = 0.
Dễ dàng thấy được f là đơn ánh nên |X| ≤ |Y | hay n ≤ 2m. 2.3 Vận dụng phương pháp đa thức và số phức 2.3.1 Ý tưởng Ý tưởng của phương pháp này là đưa việc đếm số tập X có tính
chất T nào đó về tính tổng S của các hệ số ak ứng với các lũy thừa
bậc k có cùng tính chất T (cid:48) nào đó của đa thức P (x). Sau đó sử dụng
công cụ để tính S.
Mặt khác nếu (cid:15) là căn nguyên thủy bậc n của đơn vị thì ta có i) 1 + (cid:15) + (cid:15)2 + · · · + (cid:15)n−1 = 0. ii) 1 + (cid:15)k + · · · + (cid:15)k(n−1) = 0 với (k, n) = 1. Đây chính là tính chất quan trọng của căn nguyên thủy có thể sử dụng
trong giải bài toán đếm. 2.3.2 Ví dụ Ví dụ 2.3.1 (Chọn đội tuyển PTNK 2009) Tìm số tất cả các số có
n chữ số lập từ các chữ số 3, 4, 5, 6 và chia hết cho 3.
Lời giải: Gọi cn là số các số có n chữ số lập từ các chữ số 3, 4, 5, 6 và 31 chia hết cho 3. Gọi α là một nghiệm của phương trình α2 + α + 1 = 0.
Khi đó α3 = 1 và α2k + αk + 1 nhận giá trị bằng 0 nếu k không chia
hết cho 3 và bằng 3 nếu k chia hết cho 3.
Xét đa thức P (x) = (x3 + x4 + x5 + x6)n. k=0 a3k. 6n
(cid:88) 2n
(cid:88) Dễ thấy cn chính là bằng tổng các hệ số của các số mũ chia hết cho
3 trong khai triển của P (x) nói cách khác nếu P (x) = (cid:80)6n
k=0 akxk thì
cn = (cid:80)2n k=0 k=0 P (1) + P (α) + P (α2) = ak(1 + α + α2) = 3 a3k. Cuối cùng do P (1) = 4n, P (α) = P (α2) = 1 2n
(cid:88) nên ta có k=0 . cn = a3k = 4n + 2
3 Ví dụ 2.3.2 Có bao nhiêu số nguyên dương có 5 chữ số mà tổng các
chữ số của nó là một số chẵn.
Lời giải: Gọi S là số các số có 5 chữ số thỏa mãn yêu cầu bài toán.
Xét đa thức: P (x) = (x + x2 + · · · + x9)(1 + x + x2 + · · · + x9)4. 45
(cid:88) Khai triển P (x) ta được: k=1 P (x) = akxk. 22
(cid:88) Khi đó k=1 S = [P (1) + P (−1)] = 45000. a2k = 1
2 Ví dụ 2.3.3 Tìm số tập con A của tập X = {1, 2, . . . , 2010} sao cho
tổng các phần tử của A chia hết cho 5. 32 Lời giải: Xét đa thức P (x) = (1 + x)(1 + x2) . . . (1 + x2010). Khai triển đa thức này ta được: C⊂X (cid:88) P (x) = xS(C) trong đó S(C) là tổng các phần tử của c. Do đó số tập con A của X có tổng các phần tử chia hết cho 5 là tổng
các hệ số của các lũy thừa dạng x5k với k ∈ Z.
Đặt + i sin (ε là một căn bậc 5 của đơn vị). ε = cos 2π
5 2π
5 Ta thấy với mọi k (cid:54) ...5 thì 1 + εk + (ε2)k + (ε3)k + (ε4)k = 1 − (ε5)k
1 − εk = 0. Và nếu k ...5 thì 1 + εk + (ε2)k + (ε3)k + (ε4)k = 5. Gọi S số tập con của A thì (cid:2)P (1) + P (ε) + P (ε2) + P (ε3) + P (ε4)(cid:3) . S = 1
5 Vì đa thức Q(x) = x5 − 1 có các nghiệm là 1, ε, ε2, ε3, ε4 nên Q(x) = (x − 1)(x − ε)(x − ε2)(x − ε3)(x − ε4). Suy ra: (1 + ε)(1 + ε2)(1 + ε3)(1 + ε4)(1 + ε5) = −P (−1) = 2. Vậy S = = . 22010 + 4.2402
5 22010 + 2404
5 Ví dụ 2.3.4 (Việt nam MO 2015). Cho số nguyên dương k. Tìm 33 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 {0, 2, 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). Bổ sung các chữ số 0 vào trước nếu thấy
cần thiết, các số cần tìm có dạng: a1a2 . . . ak (ai ∈ {0, 2, 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, ta đưa bài toán về việc đếm số các bộ (a1, a2, . . . , ak) ∈ Ak sao cho
a1 + a2 + · · · ak chia hết cho 3.
Tiếp theo ta xét đa thức (a1,a2,...,ak)∈Ak (cid:88) P (x) = (x2 + x + 1 + x5)k = x(a1+a2+...+ak). Tổng các hệ số của P (x) bằng số các bộ (a1, a2, . . . , ak) ∈ Ak và bằng
4k. Hơn nữa số các bộ (a1, a2, . . . , ak) ∈ Ak sao cho a1 + a2 + · · · ak bằng tổng các hệ số của các số mũ chia hết cho
3 trong P (x).
Đặt P (x) = a0 + a1x + a2x2 + a3x3 + a4x4 + · · · . Ta cần tính S = a0 + a3 + a6 + · · · Gọi ε là một nghiệm của phương trình x2 + x + 1 = 0 thì ta có ε3 = 1.
Từ đó dễ dàng suy ra 1 + εk + ε2k nhận giá trị bằng 0 với mọi k không
chia hết cho 3 và bằng 3 nếu k chia hết cho 3 (∗)
Ta có P (1) = a0 + a1 + a2 + a3 + a4 + · · · ,
P (ε) = a0 + a1ε + a2ε2 + a3ε3 + a4ε4 + · · · ,
P (ε2) = a0 + a1ε2 + a2ε4 + a3ε6 + a4ε8 + · · · 34 Áp dụng lập luận (*) ta suy ra P (1) + P (ε) + P (ε2) = 3a0 + 3a3 + 3a6 + · · · Suy ra S = = . P (1) + P (ε) + P (ε2)
3 4k + ε2k + ε4k
3 nếu k không 4k − 1
3 chia hết cho 3 và S = nếu k chia hết cho 3. Cuối cùng lại áp dụng lập luận (*), ta suy ra S =
4k + 2
3 Nhận xét 2.3.5 Bài toán trên chính là Ví dụ 2.1.3 đã được giải thông
qua việc vận dụng phương pháp truy hồi ở trên, nhưng lại được trình
bày lại thông qua việc vận dụng kỹ thuật đếm với đa thức và số phức. Ví dụ 2.3.6 Cho X = {0, 1, 2, . . . , 25}. Tìm số các tập con 7 phần tử
có tổng các phần tử chia hết cho 19.
Lời giải: Với mỗi tập con A ⊂ X gọi S(A) là tổng các phần tử của A.
Ta quy ước S(∅) = 0. Với mỗi i = 0, 1, . . . , 18, đặt P (i) = {A ⊂ X| |A| = 7 và S(A) ≡ i(mod19)}. Ta cần tính P (0). Gọi α là căn nguyên thủy bậc 19 của 1. Khi đó 1 + a + a2 + · · · + a18 = 0 và x19 − 1 = (x − 1)(x − a) · · · (x − a18). Xét đa thức Q(x) = (x − 1)(x − a)(x − a2) · · · (x − a25). Ta tính hệ số của x19 trong Q(x) bằng hai cách. Một mặt nếu khai
triển Q(x) ra thì để được x19, ta cần lấy x từ 19 dấu ngoặc, còn 7 dấu
ngoặc khác sẽ lấy các số có dạng ak với k ∈ {0, 1, . . . , 25}. Như thế ta
sẽ có tổng các số có dạng aS(A) chỉ phụ thuộc vào số dư khi chia S(A)
cho 19 (đó là lý do tại sao ta lấy căn bậc 19 của đơn vị) nên từ đây dễ 35 dàng suy ra tổng nói trên bằng: − (cid:2)|P (0)| + P (1).a + · · · + P (18).a18(cid:3) . Mặt khác P (x) = (x19 − 1)(x − 1)(x − a) . . . (x − a6). Suy ra hệ số của x19 bằng −1.a.a2 . . . a6 = −a2.
Từ đây suy ra |P (0)| + |P (1)|.a + [|P (2)| − 1] .a2 · · · + |P (18)|.a18 = 0. Điều này đúng với mọi a là nghiệm của phương trình: 1 + x + x2 + · · · + x18 = 0. Suy ra đa thức |P (0)| + |P (1)|x + [|P (2)| − 1] x2 · · · + |P (18)|x18 tỷ lệ với đa thức 1 + x + x2 + · · · + x18 và vì thế: |P (0)| = |P (1)|x = |P (2)| − 1 = · · · = |P (18)|. 19 − 1
19 C 7 . Riêng Như vậy tất cả các |P (i)|, i (cid:54)= 2, bằng nhau và bằng 19 − 1
19 C 7 |P (2)| lớn hơn đúng 1 đơn vị! Vậy đáp số là . Ví dụ 2.3.7 (IMO 1995). Cho p là một số nguyên tố lẻ. Tìm số các
tập con A của tập hợp {1, 2, . . . , 2p} biết rằng: i) A chứa đúng p phần tử; ii) Tổng các phần tử của A chia hết cho p. Lời giải: Xét đa thức P (x) = xp−1 + xp−2 + · · · + x + 1. Đa thức này
có p − 1 nghiệm phức phân biệt. Gọi α là một nghiệm bất kỳ của
P (x). Chú ý rằng α, α2, . . . , αp−1 là p − 1 nghiệm phân biệt của P (x) 36 và αp = 1. Do đó theo định lý vieta: xp−1 = (x − 1)(x − α)(x − α2) · · · (x − αp−1). Xét đa thức Q(x) = (x − α)(x − α2) · · · (x − α2p) và gọi: H = {A ⊂ {1, 2, . . . , 2p}| |A| = p}. i=0 aixi. Khi đó: Giả sử Q(x) = (cid:80)2p A∈H x∈A i=0 niαi = 2 (*) (cid:88) (cid:88) αS(A), S(A) = x. ap = − p−1
(cid:88) Vì nếu S(A) ≡ i(modp) thì αS(A) = αi nên ap = − (cid:80)p−1
i=0 niαi, trong
đó ni là số các A ∈ H sao cho S(A) ≡ i( mod p). Mặt khác, Q(x) =
(xp − 1)2, suy ra ap = −2. Thành thử (cid:80)p−1
Xét đa thức i=1 R(x) = nixi + n0 − 2. Từ đẳng thức (*) suy ra α là một nghiệm của R(x). Vì degP = degR
và α là một nghiệm bất kỳ của P (x) nên P (x) và R(x) chỉ sai khác
nhau hằng số nhân.
Từ đó np−1 = np−2 = . . . n1 = n0 − 2. Suy ra 2p − 2
p C p = . n0 − 2 = np−1 + np−2 + . . . n1 + n0 − 2
p Vậy đáp số của bài toán là 2p − 2
p C p . n0 = 2 + 2.4 Vận dụng phương pháp sử dụng hàm sinh 2.4.1 Ý tưởng Hàm sinh có thể được áp dụng trong việc giải các bài toán đếm.
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ố 37 anxn. của xn chính là số cách chọn n phần tử, tức là với an là hệ số của xn
với mọi n lớn hơn hoặc bằng 2 thì hàm sinh của số cách chọn sẽ là
F (x) = (cid:80)
n≥0 2.4.2 Ví dụ Ta sẽ bắt đầu bằng một ví dụ đơn giản, để mô tả ý tưởng của phương pháp. Ví dụ 2.4.1 Có bao nhiêu cách chọn n phần tử phân biệt từ tập hợp
có k phần tử. Nhận xét 2.4.2 Bài toán này dễ dàng giải bằng công thức tổ hợp.
Nhưng lần này chúng ta sẽ sử dụng hàm sinh. Để xác định hàm sinh
thì một trong những cách đơn giản là: Xuất phát từ một vài trường hợp
cụ thể trực quan, khái quát hóa, và quy nạp dẫn đến hàm sinh.
Cụ thể như sau: Đầu tiên ta hãy xét tập hợp có một phần tử {a1}. Ta
có:
1 cách chọn
0 phần tử
1 cách chọn
1 phần tử
2 phần tử trở lên
0 cách chọn
⇒ Hàm sinh cho số cách chọn n phần tử từ tập {a1} là 1 + x. Tương tự
như vậy, hàm sinh cho số cách chọn n phần tử từ tập {ai} (1 ≤ i ≤ k)
cũng là 1 + x (không phụ thuộc vào sự khác biệt giữa các ai).
Bây giờ ta sẽ chứng minh: hàm sinh cho số cách chọn các phần tử từ
hợp của hai tập hợp bằng tích các hàm sinh cho số cách chọn các phần
tử của mỗi tập trên. Tiếp tục xét tập 2 phần tử {a1, a2} ta có:
0 phần tử
1 cách chọn
1 phần tử
2 cách chọn
2 phần tử
1 cách chọn
3 phần tử trở lên
0 cách chọn
⇒ Hàm sinh cho số cách chọn n phần tử từ tập {a1, a2} là 1 + 2x + x2 = (1 + x)2 = (1 + x)(1 + x). Tiếp tục áp dụng quy tắc này ta sẽ được hàm sinh cho số cách chọn
các phần tử từ tập k phần tử: (1 + x)(1 + x) . . . (1 + x) = (1 + x)k. 38 Ta có k, C 1 k, C 2 k, . . . , C k k , 0, 0 . . .(cid:105) ⇔ C 0 k + k, C 1 k + C 2 k + · · · + C k k = (1 + x)k. k và bằng số cách chọn n (cid:104)C 0 Như vậy hệ số của xn trong (1 + x)k là C n
phần tử phân biệt từ tập hợp có k phần tử. Ví dụ 2.4.3 Có bao nhiêu cách sắp một giỏ n trái cây thỏa mãn điều
kiện sau: i) Số táo phải chẵn; ii) Số chuối phải chia hết cho 5; iii) Chỉ có thể có nhiều nhất 4 quả cam; iv) Chỉ có thể có nhiều nhất 1 quả đào. 0 quả táo
1 quả táo
2 quả táo
3 quả táo Bài toán có những điều kiện ràng buộc rất phức tạp, và ta có cảm giác
việc giải bài toán rất khó. Nhưng hàm sinh lại cho ta một cách giải
quyết nhanh gọn.
Lời giải: Trước tiên ta đi tìm hàm sinh cho cách chọn từng loại quả:
Chọn táo:
1 cách chọn
1 cách chọn
1 cách chọn
0 cách chọn
Như thế ta có hàm sinh A(x) = 1 + x2 + x4 + · · · = 1
1 − x2 (tổng các số hạng của cấp số nhân lùi vô hạn).
Tương tự ta tìm được hàm sinh cho cách chọn quả chuối là: A(x) = 1 + x5 + x10 + · · · = 1
1 − x5 . Hàm sinh cho cách chọn cam và đào hơi khác một chút. Ta có
1 cách chọn
1 cách chọn
1 cách chọn
1 cách chọn 0 quả cam
1 quả cam
2 quả cam
3 quả cam 39 4 quả cam
5 quả cam 1 cách chọn
0 cách chọn
⇒ Hàm sinh là A(x) = 1 + x + x2 + x3 + x4 = . 1 − x5
1 − x Tương tự ta tìm được hàm sinh cho cách chọn đào là D(x) = 1 + x = . 1 − x2
1 − x ⇒ Áp dụng Quy tắc xoắn. Hàm sinh cho cách chọn từ 4 loại quả là: A(x)B(x)C(x)D(x) = 1
1 − x5 1 − x5
1 − x 1 − x2
1 − x = 1
1 − x2
1
(1 − x)2 = 1 + 2x + 3x2 + 4x3. Như vậy cách sắp giỏ trái cây gồm n trái đơn giản là n + 1 cách. Ví dụ 2.4.4 Tính số nghiệm nguyên không âm của phương trình: x1 + x2 + · + xd = n. giá trị 0
giá trị 1
giá trị 2
giá trị 3 Lời giải: Vì x1, x2 . . . , xd nguyên không âm nên suy ra xi (1 ≤ i ≤ d)
nhận các giá trị 0, 1, 2, 3 . . . Ta tìm hàm sinh cho cách số chọn mỗi
xi (1 ≤ i ≤ d). Có
1 cách chọn
1 cách chọn
1 cách chọn
1 cách chọn
⇒ Hàm sinh cho cách chọn mỗi xi là 1 + x + x2 + x3 = . 1
1 − x Áp dụng quy tắc xoắn ⇒ Hàm sinh cho cách chọn bộ số (x1, x2 . . . , xd) là 1
(1 − x)d . Gọi un là số nghiệm nguyên không âm của phương trình: x1 + x2 + 40 k+d−1xk. k≥0 k≥0 .... + xd = n.
Khi đó hàm sinh của dãy với các số hạng dạng un chính là hàm sinh
cho số cách chọn bộ số (x1, x2 . . . , xd).
Tức là (cid:88) (cid:88) C k unxk = 1
(1 − x)d = n+d−1. Vậy un = C n Ví dụ 2.4.5 Bạn Nam có các đồng xu C1, C2, . . . , Cn. Với mỗi k, Ck
được đúc sao cho khi tung lên, xác suất để nó sấp là
. Tung tất 1
2k + 1 n
(cid:89) k=1 cả n đồng xu, tính xác suất để số đồng sấp là lẻ (biểu diễn ở dạng thu
gọn).
Lời giải: Xác suất để số đồng sấp là lẻ là tổng hệ số bậc lẻ của đa
thức: (cid:19) (cid:18) 2k + . P (x) = 2k + 1 x
2k + 1 Tổng hệ số này bằng = . P (1) − P (−1)
2 n
2n + 1 Ví dụ 2.4.6 Với mỗi tập hợp A, định nghĩa s(A) là tổng các phần
tử của A (nếu A = ∅ thì s(A) = 0). Đặt S = {1, 2, . . . , 1999}. Với
0 ≤ r ≤ 6, định nghĩa Tr = {T |T ⊆ S, s(T ) ≡ r(mod7)}. 1999
(cid:89) Với mỗi r, tính số phần tử của Tr.
Lời giải: Xét hàm sinh i=1 G(x) = (xi + 1). + i sin , ta có Đặt ε = cos 2π
7 2π
7 G(ε) = 2285(1 + ε)(1 + ε2)(1 + ε3)(1 + ε4) = 2285(1 + ε3). 41 6
(cid:88) Mặt khác, ta viết r=0 G(ε) = |Tr|εr. Như vậy, T0 − 2285 = T1 = T2 = T3 − 2285 = T4 = T5 = T6. Mà T0 + T1 + T2 + T3 + T4 + T5 + T6 = 21999. Suy ra: . T1 = T2 = T3 = T4 = T5 = T6 = ; T0 = T3 = 21999 − 2286
7 21999 + 5.2285
7 p−1
(cid:89) Ví dụ 2.4.7 Cho p là một số nguyên tố lẻ và n là một số nguyên
dương không chia hết cho p. Tìm tất cả các bộ (x1, x2 . . . , xp−1) ∈
{0, 1, . . . , n − 1}p−1 sao cho (cid:80)p−1
i=1 ixi.
Lời giải: Xét hàm sinh i=1 F (x) = (1 + xi + x2i + · · · x(n−1)i). Ta có F (1) = np−1. Đặt ε = cos + i sin . 2π
n 2π
n p−1
(cid:88) Khi đó với mọi 1 ≤ j ≤ p − 1 : F (ej) = (cid:81)p−1
i=1 1 − εnij
1 − εij . Theo định lý RUF ta có bộ số cần tính là: j=0 . F (ej) = 1
p np−1 + p − 1
p 42 Với mục đích tìm hiểu, sưu tầm một hệ thống các bài toán minh
họa cho việc vận dụng các phép đếm, luận văn “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” đã hoàn thành các
nhiệm vụ sau: (1).Hệ thống một vài 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 vài phép đếm 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. (3).Đư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. Trong
một vài ví dụ, luận văn cũng đã cố gắng đưa thêm các lời giải theo
hướng khác với cách giải trong tài liệu tham khảo. Đồng thời luận văn
cũng mạnh dạn mở rộng một vài bài toán. Hướng nghiên cứu tiếp theo của luận văn là sưu tầm, hệ thống hóa,
và đưa ra lời giải tường minh cho việc vận dụng các phương pháp, phép
đếm khác như: Nguyên lý DIRICHLET; nguyên lý cực hạn; phương
pháp đệ quy; phương pháp quỹ đạo. . . Do vấn đề được đề cập trong luận văn là tương đối rộng và phức
tạp, hơn nữa do thời gian và khả năng còn hạn chế nên mặc dù đã có
nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót. Tác giả
luận văn mong nhận được những ý kiến đóng góp quý báu của Thầy,
Cô giáo và những người quan tâm để luận văn được hoàn thiện hơn. 43 [1] Nguyễn Đình Thành Công, Nguyễn Văn Hưởng, Nguyễn Duy
Hưng, Trần Trí Kiên, Nguyễn Văn Sơn, Lê Nhất, Trần Bảo Chung
(2016), Chuyên đề bồi dưỡng HSG qua các kỳ thi Olympic, NXB
ĐHQG Hà Nội. [2] Nguyễn Ngọc Giang (2016), Phương pháp giải các bài thi vô địch toán, NXB ĐHQG. [3] Hà Duy Hưng, Nguyễn Sơn Hà, Nguyễn Ngọc Giang, Lê Minh
Cường (2016), Tuyển chọn đề thi HSG THPT môn Toán, NXB
ĐHQG. [4] Nguyễn Văn Mậu (2016), Hanoi open mathematics competition problems and solutions (2006-2015), NXB ĐHQG. [5] Nguyễn Văn Nho (2013), Tuyển tập Olympic toán học các nước Đông Âu, NXB ĐHQG. [6] Nguyễn Văn Nho, Lê Hoàng Phò (2013), Tuyển tập Olympic toán học các nước Châu Á – Thái Bình Dương, NXB ĐHQG. [7] Văn Phú Quốc (2014), Bồi dưỡng HSG môn Toán, NXB ĐHQG. [8] Ngô Đắc Tân (2004), Lý thuyết tổ hợp và đồ thị, NXB ĐHQG. [9] Trịnh Khắc Tuân (2015), Tuyển chọn đề thi HSG THPT môn Toán, NXB ĐHQG Hà Nội. [10] Tuyển tập đề thi Olympic 30/4 lần thứ XXI – 2015, NXB ĐHQG Hà Nội. [11] Các bài toán chọn lọc 45 năm tạp chí Toán học và Tuổi trẻ (2009), NXB Giáo dục.Chương 2
Vận dụng phương pháp đếm vào
giải toán
Kết luận
Tài liệu tham khảo
