tailieunhanh - 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. . | 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 Đà Nang 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à 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 A 0 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 eS 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ử x 1 x2 . xm. Xét tập X xi Sj xi e Sj i 1 2 . m j 1 2 . n . Hiển nhiên X S1 S2 . Sn k. S 64 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 6 29 .2008 Ta phân

• Báo cáo khoa học
• trình bày báo cáo
• tài liệu báo cáo khoa học
• báo cáo hóa học
• báo cáo khoa học sinh học
• báo cáo khoa học nông nghiệp
• CÁCH TRÌNH BÀY BÁO CÁO
• PHƯƠNG PHÁP TRÌNH BÀY BÁO CÁO
• KĨ NĂNG TRÌNH BÀY BÁO CÁO
• MẸO TRÌNH BÁY BÁO CÁO
• TRÌNH BÀY BÁO CÁO KHOA HỌC
• TRÌNH BÀY LUẬN VĂN BÁO CÁO
• Hình thức báo cáo thực tập
• Báo cáo thực tập tốt nghiệp
• Báo cáo thực tập
• Trình bày báo cáo thực tập
• Hướng dẫn trình bày báo cáo
• Hướng dẫn viết báo cáo
• Mẫu báo cáo
• Cách trình bày luận văn
• Cách trình bày khóa luận
• Thể thức của báo cáo
• trình bày luận văn
• báo cáo nông nghiệp
• báo cáo y dược
• báo cáo sinh học
• chăn nuôi lợn
• Kỹ năng trình bày báo cáo
• Kỹ năng thuyết trình
• Thiết kế slide
• Định dạng văn bản
• Nội dung trình bày báo cáo
• Thời gian thuyết trình
• Thực tập chuyên ngành
• Hướng dẫn viết tiểu luận
• Cấu trúc báo cáo
• Cách thể hiện báo cáo
• Nội dung báo cáo
• cách trình bày báo cáo khoa học
• báo cáo khoa học toán học
• tài liệu báo cáo nghiện cứu khoa học
• báo cáo ngành văn học
• báo cáo tiếng anh
• báo cáo khoa học
• thơ lục bát
• chăn nuôi
• báo cáo ngành kỹ thuật
• báo cáo ngành nông nghiệp
• báo cáo ngành ngoại ngữ
• báo cáo kinh tế
• báo cáo ngành tin học
• tài liệu báo cáo nghiên cứu khoa học
• báo cáo ngành y học
• trình bày thông tin tài sản thiếu trong báo cáo tài chính
• trình bày thông tin tài sản
• trình bày thông tin tài sản trong báo cáo tài chính doanh nghiệp
• phân tích tài chính
• tài chính doanh nghiệp
• phân tích tài chính doanh nghiệp
• báo cáo tài chính
• Tài liệu về trình bày đồ án
• Trình bày đồ án tốt nghiệp
• Quy định trình bày báo cáo cáo chuyên đề
• Quy định trình bày bài tập lớn
• Viện Đại học Mở Hà Nội
• mẫu báo cáo thực tập tốt nghiệp
• trình bày luận án
• cách viết báo cáo tốt nghiệp
• báo cáo tốt nghiệp
• Báo cáo phân tích ngành hàng hải
• báo cáo khoa học kinh tế
• báo cáo kỹ thuật