Báo cáo khoa học: NGUYÊN LÝ DIRICHLET ĐỐI NGẪU VÔ HẠN PHẦN 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. ...
Nội dung trích xuất từ tài liệu:
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 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. 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 mtạ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 concủa S sao cho | S 1 | + | S 2 | + … + | S n | > k. | S |. Khi đó, tồn tại một phần tử x ∈ S saocho 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 đốingẫ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.m64 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 đó, theonguyê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 ilà 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 mhộ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 choA i ⊂ A (i = 1, 2, …, n) và d(A) < d(A 1 ) + d(A 2 ) + … + d(A n ). Khi đó ít nh có hai ấtkhoả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ácbấ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ảngtrê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á ...