PHẦN I
NGUYÊN LÍ DIRICHLET VÀ ỨNG DỤNG

Chúng ta đã biết có nhiều bài toán ở dạng đặc biệt mà muốn giải được nó ngoài những kiến thức cơ bản cần phải có những phương pháp riêng biệt. Phương pháp sử dụng nguyên lý Dirichlet là một trong những phương pháp như vậy.
Trong chương này ta sẽ trình bày nguyên lý Dirichlet đối với hình học và ứng dụng của nó để giải một số bài toán hình học tổ hợp.
�1. Nguyên lý Dirichlet đối với tập hợp hữu hạn các phần tử.
1.1 Dạng đơn giản nhất của nguyên lý này có thể phát biểu như sau :
Người ta nhốt một số thỏ vào một số lồng, khi đó :
Nếu số thỏ nhiều hơn số lồng thì có một lồng có số thỏ không ít hơn 2.
Nếu số thỏ ít hơn số lồng thì có ít nhất một lồng không có thỏ.
Bằng ngôn ngữ tập hợp, nguyên lý Dirichlet được phát biểu như sau :
Mệnh đề 1 (MĐ1)
Cho m tập hợp có tổng số phần tử là n, khi đó
Nếu n > m thì có một tập hợp có số phần tử không ít hơn 2
Nếu n < m và các tập hợp đặt rời nhau ( không chứa phần tử chung) thì có ít nhất một tập hợp rỗng.
Trong một số bài toán phức tạp (MĐ1) không đủ để giải mà cần mở rộng nó như sau :
Mệnh đề 2 (MĐ2) : Nguyên lý Dirichlet tổng quát
Cho m tập hợp có tổng số phần tử là n khi đó
Nếu n > k.m thì có một tập hợp có số phần tử không ít hơn k+1
Nếu n < k.m và các tập hợp rời nhau ( không có phần tử chung) thì có một tập hợp có số phần tử không nhiều hơn k-1.
Trong khi mệnh đề trên ta hiểu các phần tử chính là các thỏ và các tập hợp chính là các lồng.
Nguyên lý Dirichlet hiển nhiên là đơn giản, tuy vậy nhiều bài toán rất khó, nguyên lý cho ta một cách giải hiệu quả. Cái khó là phải biết chọn đối tượng làm "thỏ" và xây dựng các "lồng" như thế nào.
Sau đây sẽ trình bày một số ví dụ minh hoạ ứng dụng của nguyên lý trên vào việc giải một số bài toán.
1.2 Ứng dụng.
Bài toán 1. Trong một tam giác đều có cạnh bằng 2 lấy 5 điểm bất kỳ. Chứng minh rằng tồn tại 2 điểm cách nhau một khoảng không vượt quá 1.
Giải
Ta coi 5 điểm là 5 phần tử ( 5 thỏ ).

Bây giờ ta chia tam giác đều đã cho thành 1
4 tam giác đều nhỏ, có cạnh bằng 1.
(xem hình vẽ 1) và coi 4 tam giác là Hình 1
4 tập hợp (4 lồng)

Rõ ràng 4 tam giác chứa 5 điểm đã cho. Theo (MĐ1) sẽ có 1 tam giác nhỏ chứa 2 điểm. Vì cạnh của tam giác đều nhỏ bằng 1 nên khoảng cách giữa 2 điểm đó không vượt quá 1. ( bằng 1 khi 2 điểm đó là các đỉnh của tam giác nhỏ). Ta được đpcm.
Bài toán 2. Trong một hình chữ nhật kích thước 3x4, ta đánh dấu 12 điểm. Chứng minh rằng tồn tại 3 điểm mà khoảng cách giữa chúng đôi một không vuợt quá
.

1
3

2








4

5


Giải
Ta chia hình chữ nhật thành 5 hình đa
giác lồi (xem hình 2), 2 trong chúng
là hình thang vuông, số còn lại là ngũ giác.
Dễ thấy khoảng cách lớn nhất giữa hai
điểm thuộc 1 trong 5 đa giác bằng
.
( Dùng định lý Pitago).
Khi đó, ta có 5 đa giác chứa 12 điểm. Hình 2
Mà 12 > 2.5 . Theo (MĐ2) có 1 đa
giác chứa ít nhất 3 điểm.
Vì khoảng cách lớn nhất giữa hai điểm thuộc đa giác chứa 3 điểm đó bằng
nên khoảng cách giữa 3 điểm này đôi một không vượt quá
.
Bài toán 3. Trong một hình vuông có diện tích S là một số chính phương, ta đánh dấu n điểm, với n có dạng 25k+1. Chứng minh rằng có thể tìm được k+1 điểm được đánh dấu nằm trong 1 hình tròn có diện tích
































Giải
Ta chia hình vuông đã cho thành 25
hình vuông nhỏ có diện tích

và cạnh là
(hình 3).
Khi đó 25 hình vuông nhỏ chứa n điểm
được đánh dấu, mà
n = 25 k + 1 > k . 25

Theo (MĐ2) có 1 hình vuông nhỏ chứa ít nhất k+1 điểm được đánh dấu. Vẽ hình tròn ngoại tiếp hình vuông nhỏ ấy. Dễ thấy rằng diện tích hình tròn ngoại tiếp hình vuông nhỏ bằng
(đpcm).

Nhận xét :
Dựa vào bài toán trên ta có thể chọn S, n là những số cụ thể thoả mãn các điều kiện đặt ra, ta sẽ được hưởng những bài toán cụ thể, hoặc có thể thay đổi kết luận sẽ được bài toán khó khăn hoặc dễ hơn.

Bài toán 4. Trong một hình tròn đơn vị lấy n +1 điểm bất kỳ nhưng không có điểm nào trùng với tâm hình tròn. Chứng minh rằng có thể tìm được không ít hơn hai điểm nằm trong một hình quạt tròn có diện tích bằng

Giải
Ta chia hình tròn đơn vị thành n hình quạt bằng nhau ( có đỉnh ở tâm hình tròn đã cho và góc ở tâm bằng
)
như hình 4 .

Khi đó n hình quạt chứa n +1 điểm. Hình 4

Vậy theo (MĐ1) có 1 hình quạt chứa ít nhất 2 điểm mà diện tích của hình quạt đó bằng

Bài toán 5. Trong mặt phẳng lấy 2n +3 điểm sao cho với bất cứ 3 điểm nào trong chúng cũng có hai điểm cách nhau một khoảng nhỏ hơn 1. Chứng minh rằng tại một hình tròn bán kính 1 chứa ít nhất n + 2 điểm đó.
Giải
Lấy điểm A bất kỳ trong 2n+3 điểm đã cho. Xét hình tròn tâm A bán kính 1. Có 2 khả năng xảy ra.
1. Nếu 2n+2 điểm còn lại nằm trong hình tròn tâm A thì bài toán hiển nhiên đúng.
2. Ngược lại, tức là không phải tất cả 2n+2 điểm nằm trong hình tròn tâm A. Khi đó trong 2n+2 điểm còn lại sẽ có 1 điểm B nào đó mà AB ( 1. Ta xét 2 hình tròn tâm A, tâm B bán kính bằng 1. Với C là 1 điểm bất kỳ trong 2n+1 điểm còn lại, ta xét bộ 3 điểm (A, B, C).
Vì AB ( 1 nên trong 2 đoạn AC, BC phải có một đoạn nhỏ hơn 1.
Nếu AC < 1 thì C nằm trong hình tròn tâm A.
Nếu BC < 1 thì C nằm trong hình tròn tâm B.
Dễ thấy 2n+1 điểm còn lại hoặc nằm trong hình tròn tâm A hoặc nằm trong hình tròn tâm B. Nghĩa là hai hình tròn tâm A, B chứa 2n+1 điểm mà 2n+1 > 2.n. Theo (MĐ2) có một hình tròn hoặc A hoặc B chứa ít nhất n+1 điểm còn lại.
Vậy hình tròn tâm A hoặc B chứa n+1 điểm còn lại sẽ là hình tròn chứa n+2 điểm đã cho. (đpcm)
Bài toán 6. Trong mặt phẳng cho n đường thẳng với n có dạng 4k+1 mà mỗi đường thẳng cắt một hình vuông cho trước thành 2 hình thang có tỉ số diện tích bằng
. Chứng minh rằng có ít nhất k+1 đường đồng quy trong các đường thẳng đã cho.
Giải
Ta thấy mỗi đuờng thẳng đã cho không
thể cắt hai cạnh liên tiếp của hình vuông
vì nếu thế mỗi đường thẳng như vậy sẽ
tạo với các cạnh của hình vuông một tam
giác và một ngũ giác. Bởi vậy muốn tạo
ra hai hình thang thì nhất thiết mỗi đường
thẳng đã cho phải cắt một trong 2 cặp
cạnh của hình vuông.

Kí hiệu {di} , i = 1, n là tập hợp các đường thẳng đã cho, ABCD là hình vuông đang xét M, N lần lượt là trung điểm của AD và BC.
Theo giả thiết di cắt ABCD thành 2 hình thang có tỉ số diện tích 2 : 3.
Khi đó di cắt MN tại Oi cũng chia đoạn này có tỉ số 2:3. Tức là :

Như vậy trong hình vuông ABCD tồn tại tập hợp gồm 4 điểm Oi.
Ta gọi : {di} , i = 1, n là các thỏ, vậy có n = 4k+1 con thỏ.
{Oi} , i = 1, n là số lồng, vậy số lồng bằng 4.
Mà : 4k+1 > 4k
Vậy theo (MĐ2) có ít nhất k+1 đường thẳng cùng đi qua một điểm Oi hay ít nhất k+1 đường đồng quy. (đpcm).
Chú ý : ? bài toán này các điểm được coi là các lồng và các đường thẳng được coi là các thỏ.
Bài toán 7. Một đa giác lồi cạnh được đặt trong hệ t?a độ vuông góc sao cho 5 đỉnh của đa giác có toạ độ là những số nguyên. Chứng minh rằng bên trong hay trên các cạnh của đa giác còn chứa ít nhất một điểm có toạ độ là những số nguyên.
Giải :
Ta ký hiệu Ai (Xi , Yi) là đỉnh của đa giác. Khi đó những điểm có tọa độ nguyên chỉ thuộc vào 1 trong 4 loại sau :
(x chẵn , y chẵn) An An -1
(x chẵn , y lẻ) (xn , yn)
(x lẻ , y lẻ) A1
(x lẻ , y chẵn) (x1 , y1)
Coi tập hợp điểm mà tọa
độ có tính chẵn, lẻ là các lồng. A2 Hình 7
Coi đỉnh đa giác có toạ độ nguyên thỏ, có 5 thỏ.
Mà 5 > 4
Theo (MĐ1) có ít nhất 2 đỉnh có toạ độ nguyên là Ai (xi , yi) và Ak (xk , yk) có toạ độ cùng tính chẵn, lẻ.
Xét điểm
điểm này thuộc đa giác ( do tính lồi ) và có toạ độ nguyên. (đpcm).
Bài toán 8 :
Chứng minh rằng nếu một đường thẳng không đi qua đỉnh nào của một tam giác ABC và cắt 2 cạnh của tam giác thì đường thẳng đó phải cắt phần kéo dài của cạnh còn lại.
Giải :
Giả sử đường thẳng d cắt các cạnh
AB và AC lần lượt tại M và N và cắt M
đường thẳng BC tại P. Ta thấy d
chia mặt phẳng chứa tam giác ABC
thành 2 phần (1 , (2.
B C
Hình 8

Co