Chủ đề này có 1 trả lời

[thangde.]

cho tập S={1;2...n}.Biết có thể tô các tập con của S bằng k màu thỏa mãn nếu A và B được tô cùng màu thì hoặc Chứng minh

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 30-07-2006 - 18:28

[lehoan]

Lấy http://dientuvietnam.net/cgi-bin/mimetex.cgi?{n\choose[\dfrac{n}{2}]} tập có http://dientuvietnam.net/cgi-bin/mimetex.cgi?[\dfrac{n}{2}] phần tử thì hiển nhiên không có hai tập nào chứa nhau. Do đó http://dientuvietnam...n/mimetex.cgi?A và http://dientuvietnam...n/mimetex.cgi?B là hai tập con có http://dientuvietnam...n/mimetex.cgi?A và http://dientuvietnam...n/mimetex.cgi?B kề nhau. Tương tự nếu http://dientuvietnam...n/mimetex.cgi?A cũng kề http://dientuvietnam...n/mimetex.cgi?B

NX:
Nếu kí hiệu http://dientuvietnam...mimetex.cgi?X_k là họ gồm các tập con con có http://dientuvietnam...n/mimetex.cgi?k phần tử thì ta có

có cặp ghép từ http://dientuvietnam.net/cgi-bin/mimetex.cgi?X_{k-1} vào http://dientuvietnam.net/cgi-bin/mimetex.cgi?X_{k} nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?X_{k} vào http://dientuvietnam.net/cgi-bin/mimetex.cgi?X_{k+1} nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?[\dfrac{n}{2}] phần tử đi về hai phía và quét hết tất cả các tập con khác. Khi đó ta tô màu các tập trên con đường đó cùng màu thì chỉ cần dùng số màu là http://dientuvietnam.net/cgi-bin/mimetex.cgi?{n\choose[\dfrac{n}{2}]}