tailieunhanh - Cực trị tập hợp

Nội dung chính của bài viết trình bày một số định lý quan trọng, một số phương pháp giải toán cực trị tập hợp, xây dựng - quy nạp - truy hồi. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung bài viết này. | CỰC TRỊ TẬP HỢP TRẦN MINH HIỀN Trường THPT Chuyên Quang Trung Bình Phước 1. Một số định lý quan trọng Định nghĩa . Cho F là một họ các tập hợp con của một tập tử X. Khi đó F được gọi là họ giao nếu với mọi A B F n phần T ta có A B 6 . Định lý . Cho F là một họ giao của một tập n phần tử X. Khi đó F 2n 1 . Chứng minh. Lấy một tập con A X. Khi đó với mỗi cặp tập con A X A của X thì nhiều nhất là một trong hai tập A hoặc X A thuộc vào F vì nếu cả hai tập A X A đều thuộc vào F thì do A X A mâu thuẫn với F là một họ giao các tập con của X . Vì X có 2n tập con và mỗi cặp tập con A X A có nhiều nhất một tập thuộc F. Do đó 1 F 2n 2n 1 . 2 Định lý Định lý Erdos-Ko-Rado . Một họ F các k_tập một tập hợp có k phần tử gọi là k_tập của một tập n phần tử X n k . Khi đó 2 n 1 F . k 1 Chứng minh. 1. Với n k là các số nguyên dương với n 2k. Một k_cung là một tập i i 1 . . . i k với các số nguyên lấy theo modulo n. Một cách hình dung cho một k_cung như là k đoạn cung tròn liên tiếp nối hai điểm i và i k modn trên đường tròn. Ta nói hai cung A và A0 giao nhau nếu chúng có chung nhau một đoạn cung tròn k_cung và hai cung giao nhau được minh họa bởi hình dưới đây . 123 Tạp chí Epsilon Số 03 06 2015. 2. Một họ A1 A2 . . . At các k_cung giao nhau đôi một của n thì t k. Thật vậy mỗi điểm i điểm gắn cho một cung tròn là điểm kết thúc của hai cung một cung nhận i là điểm đầu tiên và một cung nhận i là điểm cuối cùng. Do hai cung này không giao nhau dẫn đến nhiều nhất một trong hai cung này thuộc vào họ F. Xét một cung A1 cho trước. Vì các cung còn lại đều phải giao với A1 một đoạn cung chung. Do đó các cung còn lại phải nhận một 124 Tạp chí Epsilon Số 03 06 2015. trong các điểm trong của cung A1 là các điểm i1 i2 . . . ik 1 là điểm kết thúc. Vì mỗi điểm kết thúc có không quá một k_cung thuộc F nên có k 1 điểm kết thúc sẽ có không quá k_cung thuộc F cộng với cung A1 thì có không quá k_cung thuộc tập F. 3. Bây giờ xét một hoán vị của n có dạng a1 a2 . . . an . Ta đánh dấu các đoạn .