Chương 1 Một số kiến thức chuẩn bị 1.1 Nguyên lý Dirichlet cơ bản Định lý 1. Nếu nhốt n + 1 chú thỏ được nhốt vào n chuồng thì bao giờ cũng có 2 con thỏ bị nhốt vào cùng một chuồng.2 Nguyên lý Dirichlet mở rộng n Định lý 2. Nếu nhốt n chú thỏ vào m lồng mà phép chia m > k thì tồn tại một lồng chứa ít nhất k + 1 chú thỏ. Ta dễ dàng chứng minh được bằng phản chứng.
Thật vậy giả sử trái lại mọi lồng thỏ đều chứa số thỏ nhỏ hơn k + 1 con thì số thỏ trong mỗi lồng ≤ k. Khi đó suy ra tổng số thỏ là ≤ m. Điều này vô lý vì có n con thỏ. Vậy giả thiết phản chứng là sai, nguyên lý Dirichlet mở rộng được chứng minh.
Nhận xét : Nguyên lý Dirichlet thực chất là một định lý về tập hợp. Chúng ta có các phát biểu khác của nguyên lý Dirichlet dưới dạng tập hợp hữu hạn phần tử và mở rộng hơn cho tập vô hạn.3 Nguyên lý Dirichlet mở rộng cho tập hữu hạn Cho A là tập hữu hạn phần tử. Kí hiệu |A| là số lượng các phần tử thuộc A. Khi đó ta có các định lý sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Cho A,B là hai tập hợp 6= ∅ có số phần tử hữu hạn mà |A| > |B| và nếu mỗi phần tử của A tương ứng với một phần tử nào đó của B thì tồn tại ít nhất 2 phần tử của A mà tương ứng với cùng một phần tử của B. Nếu A,B là các tập hợp hữu hạn và |A| > k|B| ở đây k là một số tự nhiên nào đó và nếu mỗi phần tử của A tương ứng với một phần tử nào đó của B thì tồn tại ít nhất k + 1 phần tử của A mà chúng tương ứng với cùng một phần tử của B. k = 1 hiển nhiên đúng. Để chứng minh mệnh đề trên chúng ta giả sử mỗi phần tử của B chỉ tương ứng với nhiều nhất k phần tử của A.
Khi đó |A| ≤ k|B| trái với giả thiết |A| > k|B|. (Nguyên lý Dirichlet cho tập hữu hạn) Cho tập hữu hạn S 6= ∅ và S1 , S2 , S3 , ., Sn là các tập con của S sao cho |S1 | + |S2 | +. 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 với i = 1, 2,. Định lý tương đương Nguyên lý Dirichlet (mở rộng) và nguyên lý Dirichlet cho tập hữu hạn tương đương nhau.
Thật vậy chứng minh thuận, giả sử S có m phần tử x1 , x2 ,. 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 i = 1, 2,. Khi đó theo nguyên lý Dirichlet tồn tại ít nhất một 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 với i = 1, 2,.
Ngược lại chứng minh đảo, kí hiệu n phần tử là j = 1, 2,. Ta phân bố các phần tử j = 1, 2, ., n vào m hộp Hi , i = 1, 2, ., m}, Sj = {Hi |j ∈ Hi } với mọi j = 1, 2,. Hiển nhiên |Sj | = 1 với mọi j và |S| = m. Theo nguyên lý Dirichlet cho tập hữu hạn tồn tại phần tử Hi chung của k + 1 tập Sj , tức là tồn tại hộp Hi chứa ít nhất k + 1 phần tử.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 Nguyên lý Dirichlet đối với tập vô hạn phần tử Nguyên lý Dirichlet đối với tập vô hạn phần tử hay còn gọi dễ nhớ hơn là nguyên lý Dirichlet với độ đo. Đối với độ dài, diện tích, thể tích có một nguyên lý tương tự nguyên lý Dirichlet đối với tập hợp theo một nghĩa nào đó. Ta tạm gọi nguyên lý đó là nguyên lý Dirichlet đối với độ dài, diện tích, thể tích. Ta có các khái niệm sau: Khái niệm 1.
Một tập hợp trong mặt phẳng gọi là bị chặn khi tồn tại một hình tròn chứa toàn bộ các điểm của tập hợp đó. Nếu không tồn tại một hình tròn như thế thì tập hợp đó gọi là tập hợp không bị chặn. Một điểm P gọi là điểm biên của tập hợp A trong mặt phẳng, nếu mọi hình tròn tâm tại P có chứa những điểm thuộc A và cả những điểm không thuộc A. Tập hợp tất cả các điểm biên của A gọi là biên của A.
Một điểm P gọi là điểm trong của tập hợp A trong mặt phẳng khi tồn tại hình tròn tâm P mà nó nằm trọn trong A.1 Tập phần tử là một khoảng trên đường thẳng Ta kí hiệu d(I) là độ dài của của khoảng I ⊂ R. (Nguyên lý Dirichlet cho đoạn thẳng) Cho A là một khoảng giới nội, A1 , A2 , ., An là các khoảng sao cho Ai ⊂ A(i = 1, 2, .Khi đó có ít nhất 2 khoảng trong số các khoảng trên có một điểm trong chung. Thật vậy, giả sử không Sn có cặp nào trong những khoảng đã cho có điểm trong chung. Mặt khác, từ Ai ⊂ A(i = 1, 2,.
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. Một cách phát biểu khác dễ nhớ hơn: Trên đường thẳng cho đoạn AB có độ dài a và một số đoạn Ai Bi (i = 1, n) có tổng độ dài là b, khi đó: - Nếu b < a thì bên trong đoạn AB có một điểm M nằm bên ngoài tất cả các đoạn Ai Bi. - Nếu b > a và đoạn AB chứa tất cả các đoạn Ai Bi thì tồn tại ít nhất hai đoạn con Ai Bi có điểm trong chung.
Tổng quát : - Nếu b < ka thì bên trong đoạn AB tồn tại điểm M không thuộc quá k − 1 đoạn con. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 - Nếu b > ka và đoạn AB chứa tất cả các đoạn Ai Bi thì có ít nhất k + 1 đoạn con Ai Bi có điểm trong chung. Phát biểu trừu tượng của phát biểu tổng quát như sau: Định lý 8. (Nguyên lý Dirichlet cho đoạn thẳng mở rộng) 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.
Khi đó tồn tại ít nhất k + 1 khoảng Ai (i = 1, 2, ., n) có điểm chung trong. 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ý trên. Giả sử định lí đúng với k, ta phải chứng minh nó cũng đúng với k + 1. , An các khoảng con của A thỏa mãn (k + 1).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,.
Vì Ai ⊂ A, nên d(Ai ) ≤ d(A) với (i = 1, 2,. , n), từ đó suy ra d(A1 ) + d(A2 ) +. Ta chứng minh tồn tại điểm chung cho ít nhất k + 2 tập A1 , A2 ,. , An thỏa mãn (1) bằng quy nạp theo n.
Ta bắt đầu từ n = k + 2, tức là (k + 1).2) Đặt A0i = Ai \ Ak+2 (i = 1, 2, .6) Suy ra : A0i ⊂ A0 và A”i ⊂ A”(i = 1, 2,. Vì có tất cả k + 1 tập hợp A0i , từ bao hàm thức trên ta được (k + 1).8) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.9) và theo giả thiết quy nạp (mệnh đề đúng với k) suy ra A1 ∩ Ak+2 , A2 ∩ Ak+2 ,. , Ak+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ừ (1.3) suy ra ít nhất k + 2 tập hợp thỏa (1.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 (1.1) có điểm trong chung. Ta sẽ phải chứng minh rằng từ (k + 1).10) Suy ra có ít nhất k + 2 tập hợp trong dãyA1 , A2 ,. , An+1 có điểm trong chung.
Thật vậy, chúng ta đặt A0i = Ai \ An+1 (i = 1, 2, .16) Chúng ta sẽ chứng minh một trong các bất đẳng thức sau là đúng: (k + 1).18) Thật vậy trong trường hợp ngược lại ta có (k + 1). Cộng hai vế lại và do(1.19) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Cộng hai vế (1.19)với d(A”) và từ (1. Điều này trái với (1.10) nên một trong hai bất đẳng thức (1.18) phải có ít nhất một bất đẳng thức đúng. Theo giả thiết quy nạp đối với n từ (1.17) suy ra ít nhất k + 2 tập hợp trong dãy A01 , A02 ,.
, A0n có điểm trong chung.11) suy ra rằng kết luận cũng đúng cho dãy A1 , A2 ,. 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 (1.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 của A1 , A2 ,. Như vậy từ (1.10) suy ra k + 2 tập hợp trong dãy A1 , A2 ,.
, An 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. Nhận xét: Hoàn toàn tương tự ta có thể phát biểu nguyên lý Dirichlet đối với diện tích một hình (A) và các hình (A1 ), (A2 ), ., V (An ) trong không gian.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 Khái niệm 4.
Một tập hợp bị chặn các điểm trong mặt phẳng gọi là bề mặt khi biên của nó không chứa điểm trong (của biên). Nếu A và B là hai bề mặt, những tập hợp A ∪ B , A ∩ B , A \ B cũng là những bề mặt trong mặt phẳng. Nếu A, B và C là các bề mặt và A không có chung điểm trong với B và C thì A không có điểm trong chung với B ∪ C. Mọi bề mặt A những điểm trong mặt phẳng có thể cho tương ứng một số thực không âm S(A) sao cho: a) S(∆) = 1 với ∆ là một hình vuông có cạnh là 1.
b) Nếu A và B là hai bề mặt không có điểm chung thì S(A∪B) = S(A)+S(B).