Bài 2

Cho

S=\{1,2,\ldots,2014\}

. Với mỗi tập con khác rỗng

T\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

S

sao cho nếu

D\subseteq S

là hợp rời nhau của các tập con khác rỗng

A,B,C\subseteq S

, thì đại diện của

D

cũng là đại diện của ít nhất một trong

A,B,C

Bước 2 trên 3: Chọn chuỗi bắt buộc

Bước trước Bước tiếp

x_1,x_2,\ldots,x_{2010}:\quad 2014\cdot2013\cdots5

Phân tích chi tiết

Có 2014 cách chọn $x_1$ . Bỏ phần tử đó rồi lặp lại lập luận trên tập còn lại để chọn $x_2$ , tiếp tục đến $x_{2010}$ . Số cách là tích đã nêu; mọi tập chứa phần tử đầu tiên còn lại $x_i$ đều có đại diện ấy.