zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Báo cáo khoa học

Báo cáo khoa học: " NGUYÊN LÝ DIRICHLET ĐỐI NGẪU VÔ HẠN PHẦN TỬ"

Chia sẻ: Nguyễn Phương Hà Linh Nguyễn Phương Hà Linh | Ngày: | Loại File: PDF | Số trang:7

Báo xấu

316
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mặc dù đơ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 nó tương đương với nguyên lý Dirichlet (cổ điển ). Sau đó, nguyên lý Dirichletđối ngẫu được mở rộng cho tập vô hạn. Cuối cù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. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: " NGUYÊN LÝ DIRICHLET ĐỐI NGẪU VÔ HẠN PHẦN TỬ"

TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008 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 khóa 2005 – 2008 TÓM T ẮT Mặc dù đơ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 nó tương đương với nguyên lý Dirichlet (cổ điển ). Sau đó, nguyên lý Dirichletđối ngẫu được mở rộng cho tập vô hạn. Cuối cù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. n • Nguyên lí Dirichlet. Nếu xếp nhiều hơn n đối tượng vào m cái hộp và > k thì tồn m 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à S 1 , S 2, …, S n là các tập con của S sao cho | S 1 | + | S 2 | + … + | S n | > 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 S i ( 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ử x 1 , x 2 , …, x m . Xét tập X = { (x i ,S j ) | x i ∈ S j , i = 1, 2, …, m & j = 1, 2, …, n }. Hiển nhiên | X | = | S 1 | + | S 2 | + … + | S n | > k. | S | = k.m 64
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008 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 x i ∈ S j thì (x i ,S j ) đượ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ử x i là phần tử chung của k + 1 tập S i ( 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 H i , i = 1, …, m. Kí hiệu S = { H i | i = 1, 2, …, m}, S j = { H i | j ∈ H i } ∀ j = 1, 2, …, n. Hiển nhiên | S j | = 1 ∀j = 1, 2, …, n và | S | = m. Suy ra | S 1 | + | S 2 | + … + | S n | = n > k.m > k. |S|. Theo Nguyên lý Dirichlet đối ngẫu tồn tại phần tử H i chung của k + 1 tập S j ( i = 1, 2, … n), tức là tồn tại hộp H i chứa ít nhất k + 1 phần tử. 2. Nguyên lý Dirichlet đối ngẫu vô hạn 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 khoảng giới nội, A 1 , A 2 , … , A n là các kho ột ảng sao cho A i ⊂ A (i = 1, 2, …, n) và d(A) < d(A 1 ) + d(A 2 ) + … + d(A n ). Khi đó ít nh có hai ất 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(A 1  A 2  …  A n ) = d(A 1 ) + d(A 2 ) + … + d(A n ) > d(A). Mặt khác, từ A i ⊂ A (i = 1, 2, …, n) suy ra d(A 1  A 2  …  A n ) ≤ 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, A 1 , A 2 , … , A n là những khoảng con của A, k là số tự nhiên thỏa mãn k. d(A) < d(A 1 ) + d(A 2 ) + … + d(A n ) Khi đó tồn tại ít nhất k + 1 khoảng A i (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 A 1 , A 2 , … , A n các khoảng con của A thỏa mãn (k + 1).d(A) < d(A 1 ) + d(A 2 ) + … + d(A n ) (2.1) Ta sẽ chỉ ra rằng tồn tại điểm trong chung của k + 2 khoảng A i (i = 1, 2, …, n). Vì A i ⊂ A, nên d(A i ) ≤ d(A) (i = 1, 2, … , n), từ đó suy ra d(A 1 ) + d(A 2 ) + … + d(A n ) ≤ n.d(A). Theo (2.1) ta có (k + 1).d(A) < d(A 1 ) + d(A 2 ) + … + d(A n ) < 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 A 1 , A 2 , …, A n thỏa (2.1) 65
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008 bằng quy nạp theo n. Ta bắt đầu từ n = k + 2, tức là : (k + 1).d(A) < d(A 1 ) + d(A 2 ) + … + d(A k + 2 ) (2.2) Đặt A' i = A i \ A k + 2 (i = 1, 2, … , k + 1) (2.3) A" i = A i  A k + 2 (i = 1, 2, … , k + 1) (2.4) và A' = A \ A k + 2 (2.5) A" = A k + 2 (2.6) A' i ⊂ A' và A" i ⊂ A"( i = 1, 2, … , k + 1). Suy ra : 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(A k + 2 ) + d(A" 1 ) + d(A" 2 ) +… + d(A" k+1 ) (2.8) Từ (2.8) suy ra : k.d(A k + 2 ) < d(A 1  A k + 2 ) + d(A 2  A k + 2 ) +… + d(A k + 1  A k + 2 ) (2.9) Từ (2.9) và theo giả thiết quy nạp (mệnh đề đúng với k) suy ra A 1  A k + 2 , A 2  A k + 2 , …, A k+1  A k + 2 có điểm trong chung, điều này có nghĩa là tập hợp A 1 , A 2 , … , A k + 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(A 1 ) + d(A 2 ) + … + d(A n )+ d(A n + 1 ) (2.10) suy ra có ít nhất k + 2 tập hợp t rong dãy A 1 , A 2 , … , A n + 1 có điểm trong chung. Thật vậy, chúng ta đặt : A' i = A i \ A n+1 (i = 1, 2, … , n) (2.11) A" i = A i  A n+1 (i = 1, 2, … , n) (2.12) và A' = A \ A n + 1 (2.13) A" = A n + 1 (2.14) Vì A' i  A" i = A i , A' i  A" i = ∅ (i = 1, 2, …, n) và A'  A" = A, A'  A" = ∅ nên d(A' i ) + d(A" i ) = d(A i ) (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 ) 66
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008 k.d(A'') ≥ d(A" 1 ) + d(A" 2 ) + … + d(A" n ) và Cộng hai vế lại và do (2.15), (2.16) ta có : d(A') + k.d(A) ≥ d(A 1 ) + d(A 2 ) + … + (A n ) (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(A 1 ) + d(A 2 ) + … + d(A n ) + d(A n + 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 A 1 , A 2 , … , A n . 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 A 1 , A 2 , … , A n và cả của A n +1 . Như vậy từ (2.10) suy ra k + 2 tập hợp trong dãy A 1 , A 2 , … , A 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. 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 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 A 1 , A 2 , … , A n là các miền sao cho A i ⊂ A (i = 1, 2, …, n) và S(A) < S(A 1 ) + S(A 2 ) + … + S(A n ), 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 miền giới hạn bởi một đường cong phẳng khép kín, còn A 1 , ột A 2 , … , A n là những miền thoả mãn A i ⊂ A (i = 1, 2, …, n) và k là số tự nhiên thỏa mãn k. S(A) < S(A 1 ) + S(A 2 ) + … + S(A n ) 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. 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 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 A 1 , A 2 , … , A n là các khối sao cho A i ⊂ A (i = 1, 2, …, n) và V(A) < V(A 1 ) + V(A 2 ) + … + V(A n ), 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 khối giới hạn bởi các mặt cong phẳng, A 1 , A 2 , … , A n là ột những khối và thoả mãn A i ⊂ A (i = 1, 2, …, n), còn k là số tự nhiên mà thỏa k.V(A) < V(A 1 ) + V(A 2 ) + … + V(A n ) 67
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008 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 n hất 4 đường tròn R 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à B Hình 1 A một đoạn thẳng có độ dài 2R. Vì vậy trên cạnh hình vuông 10 10 đã chọn có những đoạn thẳng chiếu xuống với tổng độ dài là . Mà > 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 ít nhất 4 đoạn thẳng đã c hiếu xuống. Khi đó, đường thẳng đi qua M ủa vuông góc với AB cắt ít nhất 4 trong những đường tròn đó. • Ví dụ 2 A B 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 B1 A1 đ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. O 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 C1 D1  1 1 2 2 3 9  phần 0,  ,  ,  ,  ,  , … ,  ,1 . Kí C D Hình 2  10  10 10  10 10  10   i i +1 hiệu M i là phần của M nằm trong đoạn  , ( i = 0, 1, 2, … , 9) và D i là tổng độ 10 10   dài các đoạn thẳng tạo ra M i . Bằng cách tịnh tiến thích hợp chúng ta chuyển mọi đoạn 1 2 2 3 9   1 thẳng  ,  ,  ,  , … ,  ,1 tới 0,  . Kí hiệu M i ’ là ảnh của M i với i = 1, 10 10  10 10  10   10  2, 3, … , 9. Vì D = D 0 + D 1 + … + D 9 > 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 M o , M 1 ’, M 2 ’, … , M 9 ’ có điểm chung.  1 Điều này có nghĩa là một số nào đó trong 0,  là kết quả của 6 điểm khác nhau x 1 ,  10  k kk x 2 , … ,x 6 của M trừ đi tương ứng những số dạng 1 , 2 ,…, 6 , với k i là một số nào 10 10 10 68
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008 đó trong 0, 1, 2, … , 9 và i = 1, 2, … , 6. Theo nguyên lý Dirichlet ít nhất có 2 trong các k số k 1 , k 2 , … , k 6 là liên tiếp. Ví dụ k 2 = k 1 + 1 hay k 2 – k 1 = 1. Và vì x 1 – 1 = x 2 – 10 k −k k2 1 , mâu thuẫn với giả thiết. , nên x 2 – x 1 = 2 1 = 10 10 10 Vậy tổng độ dài của những đoạn tạo nên M không vượt quá 0,5. • Ví dụ 3 Tìm hình vuông có kích thước bé nhất, để trong hình vuông đó có thể sắp xếp 5 hình tròn có bán kính bằng 1 sao cho không có 2 hình tròn có điểm trong chung ? Lời giải. Giả sử hình vuông ABCD có tâm O và cạnh là a, chứa 5 hình tròn không cắt nhau và đều có bán kính bằng 1, khi đó các tâm của chúng nằm trong hình vuông A 1 B 1 C 1 D 1 có tâm O, AB//A 1 B 1 và cạnh bằng a – 2 (xem hình 2). Cácđường thẳng nối từ các trung điểm của các cạnh đối diện của hình vuông A 1 B 1 C 1 D 1 chia hình vuông đó thành b hình vuông nhỏ. Theo nguyên lý Dirichlet, ở một trong chúng ít ốn nhất cũng có hai trong số các tâm. Khi đó khoảng cách giữa hai tâm này một mặt không lớn hơn đường chéo hình vuông bé, mặt khác không bé hơn 2. Do vậy có: a −2 A1B1 2 ≤ OA 1 = 2= 2. 2 2 Suy ra : a ≥ 2 2 + 2 Vậy nếu a ≥ 2 2 + 2 và tâm của các hình tròn là các điểm O, A 1 , B 1 , C 1 , D 1 thì tất cả các điều kiện của bài toán được thoả mãn, như vậy cạnh của hình vuông cần tìm là 2 2 + 2 . TÀI LIỆU THAM KHẢO [1] Vũ Hữu Bình, Các bài toán hình học tổ hợp (Dùng cho bậc trung học cơ sở) , NXB Giáo dục, Hà Nội, 2005. [2] Trần Quốc Chiến, Giáo trình Lý thuyết tổ hợp, Đại học Đà Nẵng, 2005. [3] Nguyễn Hữu Điển, Phương pháp Dirichlet và ứng dụng , NXB khoa ọc và kỹ h thuật, 1999. [4] Nguyễn Đức Nghĩa và Nguyễn Tô Thành, Toán rời rạc , NXB Đại học Quốc Gia Hà Nội, 2003. [5] Bộ Giáo dục và Đào tạo - Hội Toán học Việt Nam, Tuyển tập 30 năm Tạp chí Toán học và Tuổi trẻ, NXB Giáo dục, 2004. [6] V.K. Balakrishnan, Theory and Problems of Combinatorics, Schaum’s Outline series McGraw-Hill, Inc. 69
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008 [7] Stefan Danchev Brics and Soren Riis, “Tree Resolution proofs of the Weak Pigeon- hole Principle”. [8] Andreas Blass, “An Induction Principle and Pigeonhole Principles for K- Finite Sets”, 2003. [9] Edwin Kwek Swee Hee - Huang Meiizhuo - Koh Chan - Heng Wee Kua, “Applications of the Pigeonhole Principle”, Singapore Maths Project Festival, 2003. [10] http://en.wikipedia.org/wiki/Johan_Peter_Gustav_Lejeune_Dirichlet, “Johan_Peter_Gustav_Lejeune_Dirichlet”, ngày truy cập 11/9/2007. [11] http://www.cs.cornell.edu/Courses/cs280/2002sp/pigeonhole% 20problem. htm, “Quiz (sort of) with answers Pigeonhole Principle CS 280 – Spring 2002”. 70

CÓ THỂ BẠN MUỐN DOWNLOAD

TL.01: Bộ Tiểu Luận Triết Học

207 tài liệu

1468 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.