TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008
64
NGUYÊN LÝ DIRICHLET ĐỐI NGẪU VÔ HẠN PHẦN TỬ
THE INFINITE DUAL DIRICHLET PRINCIPLE
TRẦN QUỐC CHIẾN
Trường Đại học Sư phạm, Đại học Đà Nẵng
TRƯƠNG CÔNG NÊN
Học viên Cao học kha 2005 – 2008
TÓM TẮT
Mc d đơn giản nhưng nguyên lý Dirichlet được áp dụn g đ giải nhiều bài toán tổ hợp
phức tạp. Tuy nhiên, nguyên lý Dirichlet chỉ được áp dụng cho các tập hữu hạn. Bài
báo này trình bày nguyên lý Dirichlet đối ngẫu cho tập hữu hạn và chứng minh rng n
tương đương vi nguyên lý Dirichlet (cổ đin ). Sau đ, nguyên lý Dirichlet đối ngẫu
được mở rộng cho tập vô hạn. Cuối cng, các kết quả được áp dụng đ giải một số bài
toán tổ hợp phức tạp.
ABSTRACT
Although it is simple, the Dirichlet principle is applied to solve many difficult
combinatorical problems. However Dirichlet principle deals exceptionally with finite
sets. This paper presents the dual Dirichlet principle and shows that it is equivalent to
the Dirichlet principle. Then, the dual Dirichlet principle is extended for infinite sets.
Finally, the results are applied to solve some difficult combinatorical problems.
1. Nguyên lý Dirichlet đối ngẫu hữu hạn phần tử
Trước hết ta nhắc lại Nguyên lý Dirichlet.
• Nguyên lí Dirichlet. Nếu xếp nhiều hơn n đối tượng vào m cái hộp và
n
m
> k thì tồn
tại một hộp chứa ít nhất k + 1 đối tượng.
Nguyên lý Dirichlet đối ngẫu được phát biểu như sau
• Nguyên lí Dirichlet đối ngẫu. Cho tập hữu hạn S ≠ ∅ và S1, S2, …, Sn là các tập con
của S sao cho | S1 | + | S2 | + … + | Sn
∈
| > k. | S |. Khi đó, tồn tại một phần tử x S sao
cho x là phần tử chung của k+ 1 tập Si ( i = 1, 2, … n).
Ta sẽ chứng minh hai nguyên lý này tương đương nhau.
• Định lí 1 (Định lí tương đương). Nguyên lý Dirichlet và Nguyên lý Dirichlet đối
ngẫu tương đương nhau.
Chứng minh
◊ Nguyên lý Dirichlet suy ra Nguyên lý Dirichlet đối ngẫu:
Giả sử S có m phần tử x1, x2, …, xm. Xét tập X = { (xi,Sj) | xi
∈
Sj , i = 1, 2, …,
m & j = 1, 2, …, n }. Hiển nhiên | X | = | S1 | + | S2 | + … + | Sn | > k. | S | = k.m
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008
65
Ta phân bố các phần tử của tập X vào m hộp 1, 2, …, m như sau: nếu xi
∈
Sj thì
(xi,Sj) được phân vào hộp i với mọi i = 1, 2, …, m và j = 1, 2, …, n. Khi đó, theo
nguyên lí Dirichlet, tồn tại hộp i có ít nhất k + 1 phần tử. Từ đó suy ra tồn tại phần tử xi
là phần tử chung của k + 1 tập Si ( i = 1, 2, … n).
◊ Nguyên lý Dirichlet đối ngẫu suy ra Nguyên lý Dirichlet:
Kí hiệu n phần tử là j = 1, 2, …, n. Ta phân bố các phần tử j = 1, 2, …, n vào m
hộp Hi , i = 1, …, m. Kí hiệu S = { Hi | i = 1, 2, …, m}, Sj = { Hi | j ∈ Hi } ∀ j = 1, 2,
…, n. Hiển nhiên | Sj | = 1 ∀j = 1, 2, …, n và | S | = m. Suy ra | S1 | + | S2 | + … + | Sn |
= n > k.m > k. |S|.
Theo Nguyên lý Dirichlet đối ngẫu tồn tại phần tử Hi chung của k + 1 tập Sj ( i =
1, 2, … n), tức là tồn tại hộp Hi
2. Nguyên lý Dirichlet đối ngẫu vô hạn phần tử
chứa ít nhất k + 1 phần tử.
2.1. Tập phần tử là một khoảng trên đường thẳng
Trong mục này ta kí hiệu d(I) là độ dài của khoảng I ⊂ R.
• Định lý 2. Cho A là một khoảng giới nội, A 1, A2, … , An là các khoảng sao cho
A
⊂
iA (i = 1, 2, …, n) và d(A) < d(A1) + d(A2) + … + d(An). Khi đó ít nhất có hai
khoảng trong số các khoảng trên có một điểm trong chung.
Chứng minh. Thật vậy, giả sử không có cặp nào trong những khoảng đã cho có
điểm trong chung. Khi đó, d(A1
A
2
… An) = d(A1) + d(A2) + … + d(An) >
d(A). Mặt khác, từ A
⊂
i A (i = 1, 2, …, n) suy ra d(A1
A
2
… An
≤
) d(A). Các
bất đẳng thức trên mâu thuẫn với nhau. Vậy ít nhất có hai khoảng trong số các khoảng
trên có điểm trong chung.
• Định lý 3. Cho A là một khoảng giới nội, A1, A2, … , An là những khoảng con của A,
k là số tự nhiên thỏa mãn
k. d(A) < d(A1) + d(A2) + … + d(An)
Khi đó tồn tại ít nhất k + 1 khoảng Ai (i = 1, 2, …, n) có điểm trong chung.
Chứng minh. Ta chứng minh bài toán này bằng phương pháp quy nạp.
◊ Trường hợp k = 1 được chứng minh ở định lý 2.
◊ Giả sử định lí đúng với k, ta phải chứng minh nó cũng đúng với k + 1. Cho A1, A2, …
, An các khoảng con của A thỏa mãn
(k + 1).d(A) < d(A1) + d(A2) + … + d(An) (2.1)
Ta sẽ chỉ ra rằng tồn tại điểm trong chung của k + 2 khoảng Ai (i = 1, 2, …, n).
Vì A
⊂
iA, nên d(Ai
≤
) d(A) (i = 1, 2, … , n), từ đó suy ra d(A1) + d(A2) + … + d(An
≤
)
n.d(A). Theo (2.1) ta có (k + 1).d(A) < d(A1) + d(A2) + … + d(An
≥
) < n.d(A). Suy ra
k + 1 < n. Vì vậy n k + 2.
Ta chứng minh tồn tại điểm chung cho ít nhất k + 2 tập A1, A2, …, An thỏa (2.1)
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008
66
bằng quy nạp theo n. Ta bắt đầu từ n = k + 2, tức là :
(k + 1).d(A) < d(A1) + d(A2) + … + d(Ak + 2) (2.2)
Đặt A'i = Ai \ Ak + 2 (i = 1, 2, … , k + 1) (2.3)
A"i = A
i Ak + 2 (i = 1, 2, … , k + 1) (2.4)
và
A' = A \ Ak + 2 (2.5)
A" = Ak + 2 (2.6)
Suy ra : A'
⊂
iA' và A"
⊂
iA"( i = 1, 2, … , k + 1).
Vì có tất cả k + 1 tập hợp A'i
≥
, từ bao hàm thức trên ta được :
(k + 1).d(A') d(A'1) + d(A'2) + … + d(A'k+1) (2.7)
Nếu lấy (2.2) trừ đi (2.7) ta có :
(k + 1).d(A") < d(Ak + 2) + d(A"1) + d(A"2) +… + d(A"k+1) (2.8)
Từ (2.8) suy ra :
k.d(Ak + 2) < d(A
1Ak + 2) + d(A
2Ak + 2) +… + d(A
k + 1 Ak + 2) (2.9)
Từ (2.9) và theo giả thiết quy nạp (mệnh đề đúng với k) suy ra A
1Ak + 2, A
2Ak + 2,
…, A
k+1 Ak + 2 có điểm trong chung, điều này có nghĩa là tập hợp A1, A2, … , Ak + 2
≥
có điểm trong chung. Như vậy với n = k + 2 từ (2.3) suy ra ít nhất k + 2 tập hợp thỏa (
2.1) có điểm trong chung.
Bây giờ chúng ta giả thiết với n k + 2 có ít nhất k + 2 tập hợp thỏa (2.1) có
điểm trong chung. Ta sẽ phải chứng minh rằng từ (k + 1).d(A) < d(A1) + d(A2) + … +
d(An)+ d(An + 1) (2.10)
suy ra có ít nhất k + 2 tập hợp trong dãy A1, A2, … , An + 1 có điểm trong chung.
Thật vậy, chúng ta đặt :
A'i = Ai \ An+1 (i = 1, 2, … , n) (2.11)
A"i = A
i An+1 (i = 1, 2, … , n) (2.12)
và A' = A \ An + 1 (2.13)
A" = An + 1 (2.14)
Vì A'
iA"i = Ai, A'i
A"i
∅
= (i = 1, 2, …, n) và A'
A" = A, A'
A" =
∅
nên
d(A'i) + d(A"i) = d(Ai) (i = 1, 2, … , n) (2.15)
và d(A') + d(A") = d(A) (2.16)
Chúng ta sẽ chứng minh một trong các bất đẳng thức sau là đúng:
(k + 1).d(A') < d(A'1) + d(A'2) + … + d(A'n) (2.17)
hoặc là k.d(A'') < d(A"1) + d(A"2) + … + d(A"n) (2.18)
Thật vậy trong trường hợp ngược lại ta có
(k + 1).d(A') ≥ d(A'1) + d(A'2) + … + d(A'n)
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008
67
và k.d(A'') ≥ d(A"1) + d(A"2) + … + d(A"n
≥
)
Cộng hai vế lại và do (2.15), (2.16) ta có :
d(A') + k.d(A) d(A1) + d(A2) + … + (An
≥
) (2.19)
Cộng hai vế (2.19) với d(A") và từ (2.15), (2.16) ta có :
(k + 1).d(A) d(A1) + d(A2) + … + d(An) + d(An + 1)
Điều này trái với (2.10). Nên một trong hai bất đẳng thức (2.17) và (2.18) phải có ít nhất
một bất đẳng thức đúng.
Giả sử (2.17) đúng. Theo giả thiết quy nạp đối với n từ (2.17) suy ra ít nhất k + 2
tập hợp trong dãy A'1, A'2, … , A'n có điểm trong chung. Từ (2.11) suy ra rằng kết luận
cũng đúng cho dãy A1, A2, … , An.
Giả sử (2.18) đúng. Từ giả thiết quy nạp đối với k suy ra k + 1 tập hợp trong
A"1, A"2, … , A"n có điểm trong chung và cùng với (2.12) chỉ ra rằng tồn tại một điểm
mà nó là điểm trong k+1 tập hợp A1, A2, … , An và cả của An +1.
Như vậy từ (2.10) suy ra k + 2 tập hợp trong dãy A1, A2, … , An
2.2. Tập phần tử là miền phẳng giới hạn bởi một đường cong phẳng khép kín
có điểm trong
chung. Suy ra kết luận đúng với n + 1. Từ phương pháp quy nạp, suy ra điều phải chứng
minh.
Trong mục này ta kí hiệu S(A) là diện tích miền A trong một mặt phẳng.
Định lý 4. Nếu A là một miền giới hạn bởi một đường cong phẳng khép kín, còn A1,
A2, … , An là các miền sao cho A
⊂
iA (i = 1, 2, …, n) và S(A) < S(A1) + S(A2) + … +
S(An), thì ít nhất có hai miền trong số các miền nói trên có điểm trong chung.
Chứng minh. Tương tự như chứng minh Định lí 2.
Định lý 5. Cho A là một miền giới hạn bởi một đường cong phẳng khép kín, còn A1,
A2, … , An là những miền thoả mãn A
⊂
iA (i = 1, 2, …, n) và k là số tự nhiên thỏa mãn
k. S(A) < S(A1) + S(A2) + … + S(An
2.3. Tập phần tử là khối ba chiều giới hạn bởi các mặt cong phẳng
)
Khi đó ít nhất k + 1 trong số những miền nói trên có điểm trong chung.
Chứng minh. Tương tự như chứng minh Định lý 3.
Trong mục này ta kí hiệu V(A) là diện tích khối A.
Định lý 6. Nếu A là một khối giới hạn bởi các mặt cong phẳng, còn A1, A2, … , An là
các khối sao cho A
⊂
iA (i = 1, 2, …, n) và V(A) < V(A1) + V(A2) + … + V(An), thì ít
nhất có hai khối trong số các khối trên có điểm trong chung.
Chứng minh. Tương tự như chứng minh Định lí 2.
Định lý 7. Cho A là một khối giới hạn bởi các mặt cong phẳng, A 1, A2, … , An là
những khối và thoả mãn A
⊂
iA (i = 1, 2, …, n), còn k là số tự nhiên mà thỏa
k.V(A) < V(A1) + V(A2) + … + V(An)
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008
68
Khi đó ít nhất k + 1 trong số những khối trên có điểm trong chung.
Chứng minh. Tương tự như chứng minh Định lí 3.
3. ỨNG DỤNG
• Ví dụ 1
Trong một hình vuông có cạnh là 1 chứa một số
đường tròn. Tổng tất cả chu vi của chúng là 10. Chứng
minh rằng tồn tại một đường thẳng cắt ít nhất 4 đường tròn
trong những đường tròn đó?
Giải. Ta chọn một cạnh hình vuông rồi chiếu vuông
góc các đường tròn xuống cạnh đó (xem hình 1). Ta có,
hình chiếu của một đường tròn bán kính R xuống AB là
một đoạn thẳng có độ dài 2R. Vì vậy trên cạnh hình vuông
đã chọn có những đoạn thẳng chiếu xuống với tổng độ dài là
10
π
. Mà
10
π
> 3. Nên theo
nguyên lý Dirichlet đối ngẫu (Định lí 3) suy ra có một điểm M nào đó thuộc AB là điểm
trong chung của ít nhất 4 đoạn thẳng đã c hiếu xuống. Khi đó, đường thẳng đi qua M
vuông góc với AB cắt ít nhất 4 trong những đường tròn đó.
• Ví dụ 2
Một tập hợp M là hợp của một số đoạn thẳng
nằm trong khoảng [0, 1]. Biết rằng khoảng cách giữa 2
điểm bất kỳ của M khác 0,1. Chứng minh rằng tổng độ
dài của những đoạn tạo nên M không vượt quá 0,5.
Lời giải. Giả sử tổng độ dài của tất cả các đoạn
thẳng trong M lớn hơn 0,5. Chia đoạn [0,1] thành 10
phần
,
12
,
10 10



,
23
,
10 10



, … , 9,1
10



. Kí
hiệu Mii i1
,
10 10
+



là phần của M nằm trong đoạn ( i = 0, 1, 2, … , 9) và Di là tổng độ
dài các đoạn thẳng tạo ra M i
12
,
10 10



. Bằng cách tịnh tiến thích hợp chúng ta chuyển mọi đoạn
thẳng ,
23
,
10 10



, … ,
9,1
10



tới
1
0,10
. Kí hiệu Mi’ là ảnh của Mi
Vì D = D
với i = 1,
2, 3, … , 9.
0 + D1 + … + D9 > 0,5 = 5*0,1. Theo nguyên lý Dirichlet đối ngẫu
(Định lí 3) suy ra có ít nhất 6 tập hợp trong Mo, M1’, M2’, … , M9
1
0,10
’ có điểm chung.
Điều này có nghĩa là một số nào đó trong là kết quả của 6 điểm khác nhau x1,
x2, … ,x6
1
k
10
của M trừ đi tương ứng những số dạng ,
2
k
10
,…,
6
k
10
, với ki là một số nào
R
B
A
Hình 1
A B
C
D
A1 B1
C1
D1
O
Hình 2