MathLabs

Bài 2

Cho S={1,2,…,2014}S=\{1,2,\ldots,2014\}. Với mỗi tập con khác rỗng T⊆ST\subseteq S, chọn một phần tử làm đại diện. Hãy tìm số cách gán đại diện cho mọi tập con khác rỗng của SS sao cho nếu D⊆SD\subseteq S là hợp rời nhau của các tập con khác rỗng A,B,C⊆SA,B,C\subseteq S, thì đại diện của DD cũng là đại diện của ít nhất một trong A,B,CA,B,C.
Bước 1 trên 3: Đại diện lan truyền
Bước trướcBước tiếp
r(X)=x1whenever x1=r(S) and x1∈Xr(X)=x_1\quad\text{whenever }x_1=r(S)\text{ and }x_1\in X
Phân tích chi tiết

Gọi r(X)r(X) là đại diện của XX và đặt x1=r(S)x_1=r(S). Nếu XX chứa x1x_1 và có không quá 2012 phần tử, bổ sung XX bằng hai tập rời nhau khác rỗng để được SS; điều kiện buộc r(X)=x1r(X)=x_1. Nếu XX có 2013 phần tử, trước hết áp dụng điều kiện cho từng cặp chứa x1x_1 rồi áp dụng cho XX, cũng suy ra kết luận.