Đề tài Sáng kiến kinh nghiệm hướng dẫn học sinh giỏi phần toán tổ hợp

hợp sau đây:
+ Trường hợp 1: Lấy một số thuộc rồi thêm số 3 hoặc 6 vào phía sau.
+ Trường hợp 2: Lấy một số thuộc rồi thêm đúng một trong hai số 4 hoặc 5 vào sau số đó.
Như vậy ta có: hay (1).
Tương tự với các số thuộc tập ta cũng có (2).
Từ (1) ta có và thay vào (2) được
 hay với mọi .
Tính trực tiếp được và , cùng với hệ thức truy hồi trên ta có kết quả cần tính là với mọi .
Bài 9. Cho A và B là hai đỉnh đối tâm của một hình tám cạnh đều. Có một con ếch bắt đầu nhảy từ A. Tại bất kì đỉnh nào trừ E, ếch có thể tới một trong hai đỉnh kề. Nếu ếch nhảy tới E thì nó dừng lại tại đó. Gọi an là số đường đi phân biệt của đúng n bước nhảy để ếch nhảy từ A đến được E. Chứng minh rằng:
 a) a2n-1 = 0.
 b).
HD. 
a) Để nhảy từ A đến E thì số đỉnh phải nhảy qua của con ếch phải là số chẵn. Do đó a2n-1 = 0.
b) Gọi bn là số đường đi từ C tới E qua n bước nhảy = số đường đi từ G tới E qua n bước nhảy.
Qua hai bước đầu tiên thì ếch có thể nhảy như sau: A ® B ® A hoặc A ® H ® A hoặc A ® B ® C hoặc A ® H ® G. Do đó ta có hệ thức: a2n = 2a2n-2 + 2b2n-2 (*).
Từ C, sau hai bước nhảy con ếch có thể nhảy như sau: C ® D ® E (kết thúc quá trình khi n = 1) hoặc C ® D ® C hoặc C ® B ® C (nếu n ³ 2) hoặc C ® B ® A (nếu n > 2). Do đó với n > 2 ta có: b2n = 2b2n-2 + a2n-2 (**).
Từ (*) và (**) ta suy ra: a2n = 2a2n-2 + 2(2b2n-4 + a2n-4) Þ a2n = 2a2n-2 + 2(a2n-2 - 2a2n-4) + 2a2n-4 Þ a2n = 4a2n-2 - 2a2n-4 với n > 2 (1). Từ a2 = 0, a4 = 2 dễ dàng suy ra công thức cần chứng minh.
Bài 10. Có n thí sinh ngồi trên một bàn tròn (n > 1). Hỏi có bao nhiêu cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn có các đề khác nhau, biết rằng trong ngân hàng đề có đúng m đề (m > 1).
HD. Ta cắt thành hàng thẳng. Kí hiệu Pn là số cách phát đề hợp lệ cho n học sinh a1, a2,, an. Ta viết ai = aj (i khác j) nếu aj và ai cùng loại đề.
Xét một cách phát đề hợp lệ cho n + 1 thí sinh a1, a2,, an, an+1.
+) Nếu a1 khác an thì bỏ an+1 ta được một cách phát đề hợp lệ cho n thí sinh a1, a2,, an và có m - 2 cách phát đề cho an+1.
+) Nếu a1 = an thì sau khi bỏ đi an+1 thì có một cách phát đề hợp lệ cho n - 1 thí sinh a1, a2,, an-1 và có m - 1 cách phát đề cho a1, an+1 hợp lệ và a1 = an.
Theo quy tắc cộng và quy tắc nhân ta có hệ thức: Pn+1 = (m - 2)Pn + (m-1)Pn-1.
Dễ có P2 = m(m - 1) và P3 = m(m - 1)(m - 2) và quy nạp suy ra công thức xác định Pn là: 
Pn = (m - 1)n + (m - 2)(-1)n.
Nhận xét. Có thể thấy bài toán tương đương với bài toán sau của dãy số: đếm số các dãy (ai)i=1,,n thỏa mãn: aiÎM = {1, 2,, m}; " i = 1, 2,, n và a1 ¹ a2, a2 ¹ a3,, an ¹ a1.
Bài 11. Cho số tự nhiên nÎN*. Xét tổng S = x1y1 + x2y2 +  + xnyn trong đó xi, yiÎ{0; 1} với mọi giá trị i = 1, 2,, n. Gọi A, B tương ứng là số các tổng trên mà S là lẻ và chẵn. Chứng minh rằng 
.
HD. Đặt Sn = x1y1 + x2y2 +  + xnyn trong đó xi, yiÎ{0; 1} với mọi i = 1, 2, n. Gọi An, Bn là số các tổng mà Sn tương ứng là lẻ và chẵn, ta có ngay A1 = 1, B1 = 3. 
Với n > 1, thì do Sn = Sn–1 + xnyn và có ba bộ (xn, yn) làm cho xnyn chẵn (bằng 0) và chỉ một bộ (xn, yn) làm cho xnyn lẻ nên ta có: An = 3.An–1 + Bn–1 và Bn = An + 3.Bn–1.
Chúng ta có thể tính An, Bn trong trường hợp này bằng cách đưa về dãy truy hồi tuyến tính cấp hai và dùng phương trình đặc trưng, nhưng ta có thể viết
 	An + Bn = 4(An–1 + Bn–1) =  = 4n–1(A1 + B1) = 4n 
 và An – Bn = 2(An–1 – Bn–1) =  = 2n–1(A1 – B1) = – 2n. 
Lần lượt cộng và trừ từng vế cho nhau ta được
An = 2n–1(2n – 1) và Bn = 2n–1(2n + 1) với mọi n ³ 1.
Từ đó . Bài toán được chứng minh.
Bài 12. Cho các điểm A1, A2, , An với n ³ 2 theo thứ tự đó nằm trên một đường thẳng. Người ta tô màu tất cả các điểm này bởi 5 màu: xanh, đỏ, vàng, cam và tím thoả mãn hai điều kiện: 
 +) mỗi điểm tô một màu,
 +) Hai điểm Ai, Ai+1 (i = 1, 2, , n - 1) thì hoặc luôn được tô cùng màu hoặc là một trong hai điểm được tô màu xanh. 
Hỏi có bao nhiêu cách tô như vậy?
HD. Gọi an là số cách tô thoả mãn điều kiện có điểm cuối được tô xanh, bn là số cách tô thoả mãn điều kiện có điểm cuối không được tô xanh. Ta tính trực tiếp được a2 = 5, b2 = 8. 
Xét khi n > 2: Rõ ràng khi An được tô xanh thì An-1 có thể được tô xanh hoặc không xanh nên
an = an-1 + bn-1 	(1).
Nếu An không được tô xanh thì nó được tô bởi một trong 4 màu còn lại và An-1 phải được tô xanh hoặc cùng màu với An (khác màu xanh). Từ đó suy ra 
bn = 4an-1 + bb-1 	(2).
Kết hợp (1), (2) cùng với a2 = 5, b2 = 8 ta có:
 2an + bn = 3(2an-1 + bn-1) =  = 3n-2(2a2 + b2) = 3n-2.18 = 2.3n 
 và bn- 2an = (-1)(bn-1-2an-1) =  = (-1)n-2(b2 - 2a2) = -2.(-1)n. 
Giải hệ này ta được an = , bn = với mọi n ³ 2. Vậy số cách tô màu cần tìm là:
S = an + bn = với mọi n ³ 2.
Bài 13. Cho một tứ diện đều ABCD có cạnh là 1 mét. Một con bọ xuất phát từ đỉnh A, di chuyển theo quy tắc: tại mỗi đỉnh nó đến nó sẽ chọn một trong 3 cạnh tại đỉnh đó để di chuyển theo cạnh đó đến đỉnh khác. Tìm số cách đi để con bọ trở lại đỉnh A khi nó đã đi được đúng n mét với n Î N*.
HD. Gọi , , , là số cách đi để đúng sau khi đi được n mét con bọ sẽ tương ứng đến A, B, C, D. Với mỗi n > 1:
B
A
C
D
i) Do tính đối xứng của các đỉnh B, C và D nên
	 = = ,	 (1)
ii) Muốn đi đến A phải từ B, C hoặc D đi thêm 1 mét nữa nên:
	 = + + ,	 (2)
	iii) Tương tự: = + + (3).
 Từ (1) và (2) ta có: = 3 Þ = 3. Kết hợp với 
 (3) ta được: 
 = 3 = 3( + + ) = 3( + 2) = 3 + 2.
Hay là = 2+ 3 với mọi n > 1.
Kết hợp với = 0, = 3 ta tính được kết quả = với mọi nÎN*.
Bài 14. Cho số tự nhiên n Î N* và có n cặp vợ chồng tham gia lễ hội hoá trang. Có bao nhiêu cách ghép họ thành n cặp nhảy sao cho không có cặp nào là vợ chồng?
HD. Ký hiệu các cặp vợ chồng là C1, V1, , Cn, Vn và sn là số cách sắp xếp n cặp nhảy sao cho không có cặp nào là vợ chồng. Với n ³ 3, vì có n - 1 cách sắp xếp Cn với Vi (i ¹ n) nên ta xét hai trường hợp:
Trường hợp 1: Ghép Cn với Vi (i ¹ n) và ghép Ci với Vn. Khi đó có n - 1 cách ghép Cn với Vi , loại đi 2 cặp Cn, Vn; Ci , Vi có sn-2 cách ghép n - 2 cặp còn lại. Trường hợp này sẽ có (n-1)sn-2 cách.
Trường hợp 2: Ghép Cn với Vi (i ¹ n) và không ghép Ci với Vn. Khi đó cũng có n - 1 cách ghép Cn với Vi, loại đi hai người đó, ghép tuỳ ý những người còn lại sẽ có n - 1 cách. Trường hợp này sẽ có (n-1)sn-1 cách.
Do vậy, kết hợp cả hai trường hợp trên ta có hệ thức truy hồi:
sn = (n-1)(sn-1 + sn-2) với mọi n ³ 3.
Biến đổi
 =  = . 
Tính trực tiếp được s1 = 0, s2 = 1, thay vào ta có
= Û .
Từ đây suy ra 
 = .
Vậy cuối cùng ta có: 
 với mọi nÎN*.
1.2. Các bài toán sử dụng tổng hợp đệ quy và song ánh
Bài 15. Với mỗi n Î N*, kí hiệu Hn là tập tất cả các hoán vị của n số nguyên dương đầu tiên. Xét các tập hợp:
.
Tìm tất cả các số nguyên dương n sao cho: .
HD. Đặt ;. Dễ có: 
.
Xét ánh xạ f:, . Vì f là song ánh nên: 
.
Xét ánh xạ g:, . Vì g là song ánh nên: 
Vậy: . Mà .
Xét ánh xạ h: Tn ® Tn-1ÈTn-2; .
Vì h là song ánh nên . Mà 
.
Vậy: ÛÛ n £ 6.
Bài 16 (IMO 1987). Gọi Pn(k) là số các hoán vị của tập (n ÎN*) có đúng k điểm cố định (0 £ k £ n). Chứng minh rằng: .
HD. Đặt: M ={(f, i)êf là hoán vị của A giữ nguyên k phần tử, iÎA sao cho f(i) = i}. Ta có: 
.
Với mỗi 1£ i £ n: đặt Ni là tập tất cả các hoán vị giữ nguyên k -1 phần tử của tập hợp B = A\ {i} thì . Xét ánh xạ 
g: , .
Vì g là song ánh nên 
.
Bài 17 (VMO 1996). Cho n, k, mÎN* thoả mãn điều kiện 1 1. Hỏi có bao nhiêu chỉnh hợp chập k: của n số nguyên dương đầu tiên mà mỗi chỉnh hợp đó đều thoả mãn ít nhất một trong hai điều kiện sau:
 i) $ i, j Î{1, 2,...,k} sao cho i aj ;
 ii) $ i Î{1, 2,...,k} sao cho ai – i không chia hết cho m.
HD. Đặt A = {tập các chỉnh hợp chập k của (1,2,...,n)}; A* = {tập các chỉnh hợp thoả mãn giả thiết}; B = {ÎA êa1 < a2 <...< ak và ai – i m "i = 1,2,...,k}. Dễ thấy A* = A\B.
Xét ánh xạ f: B ® B’, . Khi đó f là song ánh từ B đến B’, với B’ = . Do đó . Vậy .
BÀI TẬP
Bài 1. Trong mặt phẳng cho n đường tròn (nÎN*) trong đó bất kỳ hai đường tròn nào cũng cắt nhau tại hai điểm phân biệt và không có ba đường nào có điểm chung. Tính số phần mặt phẳng mà các đường tròn đó chia ra.
Đáp số: n2 – n + 2 phần với mọi nÎN*.
Bài 2. Có bao nhiêu xâu gồm n ký tự (n ³ 1) với các kí tự 0, 1, 2 sao cho không có hai ký tự 0 đứng cạnh nhau.
Hướng dẫn: Gọi sn là số các xâu như thế. Tính được s1 = 3, s2 = 8 và hệ thức truy hồi sn = 2sn-1 + 2sn-2 với mọi n ³ 3. Suy ra được kết quả 
sn = với mọi n Î N*.
Bài 3. Cho số nguyên dương n, ký hiệu T là tập hợp gồm 2n số nguyên dương đầu tiên. Hỏi có bao nhiêu tập con S của T có tính chất: trong S không tồn tại các số a, b mà . (Lưu ý rằng tập rỗng là tập con có tính chất nên trên).
Đáp số: với mọi n ³ 1.
Bài 4. Giả sử Fk là tập tất cả các bộ (A1, A2,, Ak) trong đó Ai là một tập con của {1, 2,, n}, "i = 1, 2,, k (các Ai có thể trùng nhau). Tính: Sn =.
Bài 5. n đường tròn chia mặt phẳng ra làm bao nhiêu miền nếu bất kì cặp đường tròn nào cũng cắt nhau tại hai điểm phân biệt và không có ba đường tròn nào có giao điểm chung.
Bài 6. Cho số nguyên dương n và S = {1, 2,, n}. Gọi cn là số các tập con của S mà chứa đúng hai số nguyên dương liên tiếp. Chứng minh rằng: trong đó Fn là số hạng thứ n trong dãy Fibônaxi.
Bài 7. Có bao nhiêu cách lát đường đi kích thước 3´2n bằng các viên gạch kích thước 1´2? 
Đáp số: cn = 4cn-1 - cn-2.
CHUYÊN ĐỀ 2. CÁC NGUYÊN LÍ CƠ BẢN CỦA TỔ HỢP
----------
Phần I. NGUYÊN LÍ DIRICHLET
1. Cơ sở lí thuyết
1.1. Nguyên lí Drichhet dạng tổ hợp
Nếu nhốt n.m + r (m, n, r là các số nguyên dương) con thỏ vào n cái chuồng thì phải có ít nhất một chuồng chứa không ít hơn m + 1 con thỏ.
1.2. Nguyên lí Drichhet dạng độ đo
+ Giả sử đoạn thẳng AB được chia thành n đoạn thẳng A1B1, A2B2,..., AnBn. Nếu thì tồn tại một điểm là điểm chung của ít nhất đoạn. Nếu thì tồn tại một điểm là điểm chung của không quá đoạn.
+ Giả sử hình (H) được chia thành n hình con (H1), (H2),..., (Hn). Nếu thì tồn tại một điểm là điểm chung của ít nhất hình con. Nếu thì tồn tại một điểm là điểm chung của không quá hình con.
2. Một số kĩ thuật ứng dụng của nguyên lí Đirichlet
2.1. Phân chia tập hợp để tạo các n - tập (các “chuồng”)
Ví dụ mở đầu. Trong hình vuông có cạnh bằng 1 đặt 51 điểm bất kì phân biệt. Chứng minh rằng có ít nhất ba trong số 51 điểm đó nằm trong một hình tròn bán kính .
Lời giải. Chia thành 25 hình vuông con có độ dài cạnh bằng 0,2. Khi đó tồn tại một hình vuông con chứa ít nhất 3 điểm (giả sử là M, N, P) trong 51 điểm đó (vì 51 = 2.25 + 1). Giả sử ABCD là hình vuông con đó và I là tâm của nó. Xét hình tròn (C) tâm I, bán kính R = . Ta có 
.
Vậy M, N, P nằm trong hình tròn (C).
Nhận xét. Nội dung cơ bản của phương pháp là chia một đối tượng lớn thành nhiều đối tượng nhỏ (các đối tượng này như các “chuồng”); sau đó áp dụng nguyên lí Dirichlet.
Ví dụ 2. Trong hình tròn có diện tích bằng 8 đặt 17 điểm bất kì sao cho không có 3 điểm nào thẳng hàng. Chứng minh rằng có ít nhất ba điểm tạo thành một tam giác có diện tích nhỏ hơn 1.
HD. Chia đường tròn thành 8 hình quạt bằng nhau như hình vẽ:
Sẽ có 3 điểm nằm trong một hình quạt (giả sử đó là các điểm A, B, C) Khi đó S(ABC) < S(quạt) = 1 (đpcm).
Ví dụ 3. Trong hình tròn (C) tâm O, bán kính R = 2,5 cho 10 điểm bất kì; CMR có hai điểm có khoảng cách nhỏ hơn 2.
Lời giải. Chia hình tròn thành 9 phần như hình vẽ (gồm một hình tròn bán kính 1 ở trong và tám “hình thang cong” ở ngoài):
Theo nguyên lí Dirichlet thì có một phần chứa ít nhất hai điểm (giả sử là A và B) trong 10 điểm đã cho. Xét hai trường hợp:
+) Hai điểm A, B nằm trong hình tròn nhỏ: khi đó AB < 2.
+) Hai điểm A, B nằm trong hoặc trên các cạnh của một trong các “hình thang cong” còn lại: Giả sử “hình thang cong” đó là MNPQ. Khi đó xét hình thang MNPQ có: QP < 1; QM = 1,5; PN = 1,5; MN < 2; QN < 2; PM < 2. Do đó khoảng cách giữa hai điểm bất kì thuộc hình thang MNPQ và miền trong của nó đều nhỏ hơn 2.
· Nếu A, B thuộc hình thang MNPQ hoặc miền trong của nó thì ta có đpcm.
· Nếu A, B không nằm hoàn toàn trong hình thang thì lấy trên đoạn OM điểm A’ sao cho OA’ = OA, lấy trên đoạn ON điểm B’ sao cho OB’ = OB. Từ suy ra AB £ A’B’ < 2.
Vậy trong mọi trường hợp thì AB < 2 (đpcm).
Ví dụ 4. Cho hình bình hành ABCD và 25 đường thẳng. Mỗi đường thẳng chia ABCD thành 2 hình thang với tỉ số diện tích là . CMR trong 25 đường thẳng đó có 7 đường thẳng đồng quy.
Lời giải. Gọi K, H, I, J lần lượt là trung điểm của các đoạn thẳng như hình vẽ:
Xét 25 đường thẳng đã cho. Với mỗi đường thẳng đó có một trong hai khả năng sau xảy ra:
+) Đường thẳng đó cắt cạnh AB và CD. Khi đó nó phải đi qua K hoặc H.
+) Đường thẳng đó cắt cạnh AD và BC. Khi đó nó phải đi qua I hoặc J.
Như vậy sẽ có 7 đường thẳng cùng đi qua một trong 4 điểm I, J, K, H nêu trên (đpcm).
Nhận xét. Việc phát hiện ra các m – tập ở đây dựa trên tính chất đặc trưng của các đường thẳng.
2.2. Xây dựng các n - tập theo đối tượng xuất phát
Ví dụ mở đầu. Trong mặt phẳng cho 2009 điểm. Biết rằng trong 3 điểm bất kì lấy từ các điểm đã cho luôn có hai điểm có khoảng cách không lớn hơn 1. CMR có 1005 điểm nằm trong hình tròn bán kính 1.
Lời giải. Lấy điểm M trong 2009 điểm đó và xét hình tròn (C) có tâm M, bán kính bằng 1.
+) Nếu tất cả các điểm đều thuộc (C) thì (C) là hình tròn cần tìm.
+) Nếu có điểm N sao cho MN > 1 thì xét hình tròn (C’) có tâm N, bán kính 1. Khi đó với mọi điểm P trong 2007 điểm còn lại luôn xảy ra một trong hai khả năng sau: (vì AB > 1). Từ 2007 điểm này sẽ có ít nhất 1004 điểm cùng thuộc (C) (hoặc (C’)). Khi đó hình tròn (C) (hoặc (C’)) là hình tròn cần tìm.
Nhận xét. Trong ví dụ trên, việc chọn ra các n - tập được bắt đầu từ việc chọn ra một “đối tượng xuất phát” là điểm M. Từ “đối tượng xuất phát” này ta lập luận để suy ra các đối tượng (trường hợp) còn lại ... Đây là một kĩ thuật hay dùng trong các bài toán sử dụng nguyên lí Đirichlet.
Ví dụ 2. Trong mặt phẳng cho 9 đường thẳng song song nằm ngang và 3 đường thẳng song song nằm dọc. Người ta đánh dấu các giao điểm của các đường thẳng này bởi hai màu xanh (X) và đỏ (Đ). CMR tồn tại 2 đường thẳng nằm ngang và 2 đường thẳng nằm dọc sao cho 4 giao điểm của chúng được tô cùng màu.
Lời giải. Xét 3 giao điểm đầu của các đường thẳng nằm ngang. Trên mỗi đường thẳng này có 23 cách tô màu 3 giao điểm đầu. Có 9 đường thẳng nằm ngang với 23 = 8 cách tô màu nên có hai đường thẳng có cùng cách tô màu 3 điểm đầu tiên. Trên hai đường đó thì trong 3 cách tô màu phải có hai màu trùng nhau Þ đpcm.
Ví dụ 3. Trên đường tròn cho 16 điểm tô bởi một trong ba màu: X, Đ, V. Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi hai màu: T, L. Chứng minh rằng ta luôn có 3 trong 16 điểm trên tô cùng màu và 3 cạnh của nó cũng được tô cùng màu.
HD. Có ít nhất 6 điểm tô cùng màu, giả sử là A, B, C, D, E, F. Xét 5 dây cung AB, AC, AD, AE, AF sẽ có ít nhất 3 dây cùng màu, giả sử đó là màu T.
Không mất tính tổng quát giả sử AB, AC, AD cùng màu T. Khi đó:
Nếu BC màu T thì kết thúc bài toán; nếu BC màu L thì xét CD: 
Nếu CD màu T thì kết thúc; nếu CD màu L thì xét BD: 
Nếu BD là T thì kết thúc; nếu BD màu L thì tam giác BCD có ba cạnh cùng màu L và 3 đỉnh B, C, D cùng màu bài toán kết thúc.
Ví dụ 4. Cho đa giác đều A1A2A1981 nội tiếp (O). CMR trong số 64 đỉnh bất kì của đa giác luôn có 4 đỉnh là các đỉnh của một hình thang.
Lời giải. 
Nhận xét: Nếu có hai dây cung (được tạo thành từ 1981 đỉnh của đa giác) có độ dài bằng nhau và không có đỉnh chung thì ta sẽ có một hình thang.
Xét độ dài các dây cung A1A2, A1A3,, A1A1981. Ta thấy A1A2 = A1A1981, A1A3 = A1A1980,, A1A991 = A1A992 và các độ dài này đôi một khác nhau. Vậy có 990 độ dài các dây cung có một đỉnh là A1 và đó cũng là tất cả các độ dài của các dây cung được tạo thành từ 1981 điểm đã cho.
Trong 64 đỉnh sẽ có dây cung. Vì có 990 độ dài suy ra có ít nhất 3 dây cung có cùng độ dài. Nếu các dây cung này đều đôi một có đỉnh chung thì sẽ tạo thành một tam giác đều (vì chỉ có đúng 2 dây cung chung đỉnh có cùng độ dài) như hình vẽ:
Khi đó đường tròn sẽ được chia ra thành 3 cung bằng nhau suy ra số đỉnh của đa giác phải là số nguyên lần của 3, điều này là vô lí vì 1981 không chia hết cho 3. Vậy trong 3 dây cung có cùng độ dài này có ít nhất hai dây cung không có chung đỉnh, hai dây cung đó tạo thành một hình thang cân có 4 đỉnh là 4 đỉnh của đa giác ban đầu.
Ví dụ 5. Trong mặt phẳng cho n - giác lồi có tọa độ các đỉnh là các số nguyên (n > 4).
a) CMR ở trên cạnh hoặc bên trong đa giác đó còn có ít nhất một điểm nguyên khác nữa.
b) CMR bên trong đa giác đó (không kể các cạnh) còn có ít nhất một điểm nguyên khác nữa.
HD.
a) Chia tập các điểm nguyên thành 4 loại: Loại I = (ch; ch), loại I = (ch; lẻ), loại III = (lẻ; ch), loại IV = (lẻ; lẻ). Vì n > 4 nên có ít nhất 5 đỉnh suy ra có ít nhất hai điểm có cùng loại và khi đó trung điểm của hai điểm này có tọa độ nguyên.
b) Xét 5 đỉnh liên tiếp của đa giác là A, B, C, D, E. Khi đó ta có một ngũ giác lồi ABCDE và các điểm nằm trong ABCDE cũng nằm trong đa giác trên.
Trong năm đỉnh A, B, C, D, E phải có hai đỉnh chung một cạnh có tổng các góc ở đỉnh đó > 1800 (vì ngược lại thì vô lí!. Giả sử A và B là hai đỉnh như vậy. Khi đó: 
.
Không mất tính tổng quát giả sử . Ta kẻ Ax//BC, Ct//AB (hướng của các tia Ax, Ct lần lượt là hướng các vectơ ), chúng cắt nhau tại I.
+ Nếu : Vì nên tia Ax thuộc miền góc trong của góc (không kể hai cạnh). Mặt khác, Ct trùng với tia CE, do dó I nằm trong đoạn CE (không kể hai đầu mút) nên I nằm trong ngũ giác ABCDE (không kể các cạnh).
+ Nếu thì tia Ct nằm trong miền góc (không kể các cạnh). Do đó I nằm trong ngũ giác ABCDE (không kể các cạnh).
Vì A, B, C có các tọa độ nguyên nên I có tọa độ nguyên Þ (ĐPCM).
2.3. Xây dựng các dãy số
Ví dụ mở đầu. CMR có thể tìm được một số có dạng 197919791979000 chia hết cho 2000.
Lời giải. Xét dãy số: 1979, 19791979,, . Khi chia các số hạng của dãy này cho 2000 sẽ có hai số hạng có cùng số dư và hiệu của chúng có dạng 19791979197900 chia hết cho 2000.
Nhận xét. Nội dung chủ yếu để giải các dạng toán này là tạo ra các dãy số từ bài toán. Sau đó ta áp dụng nguyên lí Đirichlet cho các số hạng của dãy số được chọn (Các số hạng thay cho các “thỏ”).
Ví dụ 2. Xét 100 số nguyên dương a1,, a100; ai £ 100, " i = 1, 2,, 100 và a1 +  + a100 = 200. CMR trong 100 số đó luôn tồn tại một vài số có tổng bằng 100.
Lời giải.
+) Nếu ai = aj với mọi i ¹ j thì hiển nhiên.
+) Nếu a1 ¹ a2 thì lập dãy sau: a1, a2, a1 + a2,, a1 + a2 ++ a99 (các số hạng này thuộc [1, 199]).
· Nếu tồn tại một số hạng nào trong dãy chia hết cho 100 thì số hạng đó bằng 100 (đpcm).
· Nếu không có số hạng nào chia hết cho 100 thì trong 100 số này khi chia cho 100 sẽ có hai số hạng có cùng số dư. Hiệu của chúng cho ta tổng cần tìm.
Ví dụ 3. CMR trong 39 số tự nhiên liên tiếp bất kì luôn có ít nhất một số có tổng các chữ số chia hết cho 11.
Lời giải. Giả sử các số đó là a1 < a2 << a39. Xét 20 số hạng đầu tiên của dãy này sẽ có hai số tận cùng là 0 và có một số (trong hai số này) có chữ số ngay trước chữ số tận cùng khác 9. Gọi số này là N.
Xét các số N + 1, N + 2,, N + 19 thuộc 39 số đã cho. Khi đó:
S(N + i) = S(N) + i với i = 0, 2,, 9 và S(N + 19) = S(N) + 10 (kí hiệu S(a) là tổng các chữ số của a).
Trong 11 số liên tiếp S(N), S(N) + 1,, S(N) + 9, S(N) + 10 thì có một số chia hết cho 11 (đpcm).
Ví dụ 4. Cho 69 số nguyên dương phân biệt không vượt quá 100. CMR có thể chọn được 4 số a, b, c, d sao cho a < b < c và a + b + c = d.
HD. Giả sử các số là 1 £ a1 < a2 << a69 £ 100. Khi đó a1 £ 32. Xét hai dãy sau:
.
Từ (1) và (2) có 134 số hạng trong đoạn [1; 132] suy ra có 2 số bằng nhau thuộc về hai dãy Þ đpcm.
2.4. Xây dựng bảng
Ví dụ mở đầu. Cho a1, a2, , an là các số thực bất kì cho trước. Chứng minh rằng luôn tồn tại số thực x sao cho a1 + x, a2 + x,, an + x đều là các số vô tỉ.
Lời giải. Giả sử t là số vô tỉ bất kì. Ta sẽ chứng minh trong các số t, 2t,, (n + 1)t sẽ có một số thỏa mãn.
Giả thiết phản chứng là không có số nào trong các số trên thỏa mãn. Lập bảng (n + 1)´n như sau:
 t + a1 t + a2  t + an
 2t + a1 2t + a2  2t + an
(n + 1)t + a1 (n + 1)t + a2 ... (n + 1)t + an 
Có n + 1 hàng và n cột. Theo giả thiết phản chứng thì trong mỗi hàng có ít nhất một số hữu tỉ nên có ít nhất n + 1 số hữu tỉ. Vì có n cột nên có một cột chứa hai số hữu tỉ, giả sử là kt + ak và mt + ak (m > k) . Khi đó hiệu của chúng (k - m)t là số hữu tỉ, vô lí! Þ đpcm.
Nhận xét. Nội dung cơ bản của phương pháp này là lập các bảng. Sau đó áp dụng nguyên lí Dirichlet cho các hàng (hoặc cột) để suy ra các tính chất mới cần sử dụng.
Ví dụ 2. Cho tập A Ì có tính chất: trong N số tự nhiên liên tiếp bất kì (N > 1) luôn tồn tại một số thuộc A. CMR tồn tại hai số trong A sao cho số này chia hết cho số kia.
Lời giải. Xét bảng (N + 1)´N (N + 1 dòng, N cột) được xây dựng như sau:
Hàng 1: 1 2 3 4  N
Hàng 2: 1 + 1.2N 2 + 1.2N 3 + 1.2N 4 + 1.2N  N + 1.2N
..      
Hàng i: k + 1 k + 2 k + 3 k + 4  k + N
Hàng i+1: k+1+M k+2+M k+3+M k+4+M  k+N+M
Với M = (k + 1)(k + 2)(k + N).
Theo giả thiết thì trong mỗi hàng luôn tồn tại một phần tử của A. Do có N + 1 hàng và N cột nên có một cột chứa hai phần tử của A và trong hai phần tử này thì phần tử thuộc hàng sau sẽ chia hết cho phần tử thuộc hàng trước nó.
Ví dụ 3. Trên bàn cờ 10´10 người ta viết các số từ 1 đến 100. Mỗi hàng chọn ra số lớn thứ ba. CMR tồn tại một hàng có tổng các số trong hàng đó nhỏ hơn tổng các chữ số lớn thứ ba được chọn.
HD. Kí hiệu các số lớn thứ ba là a9 < a8 << a1 < a0. Khi đó số phần tử lớn hơn a0 nhiều nhất là 20 (nhiều nhất là 2 phần tử ở mỗi hàng). Suy ra a0 ≥ 80 (1). Tương tự a1 ≥ 78 (2).
Mặt khác a8 ≥ a9 + 1, a7 ≥ a9 + 2,, a2 ≥ a9 + 7. Kết hợp với (1) và (2) suy ra:
a0 + a1 ++ a9 ≥ 80 + 78 + (a9 + 1) + (a9 + 2) ++ (a9 + 7) + a9 = 8a9 + 180.
Xét hàng chứa a9. Tổng các số của dòng chứa a9 là S(a9). Ta có:
S(a9) £ 100 + 99 + a9 + a9 – 1 +  + a9 – 7
S(a9) = 8a9 + 171 < 8a9 + 180 £ a0 + a1 + + a9.
3. Ứng dụng nguyên lí Đirichlet trong một số vấn đề của toán học
3.1. Ứng dụng trong các bài toán suy luận
Ví dụ 1. Có 10 đội bóng thi đấu với nhau mỗi đội phải đấu một trận với các đội k