Bài 2
Cho là số nguyên dương và là các tập con của . Mỗi có đúng phần tử, hai tập khác nhau có đúng một phần tử chung, và mỗi phần tử của thuộc ít nhất hai tập . Với những nào có thể gán nhãn 0 hoặc 1 cho mỗi phần tử sao cho mỗi có đúng phần tử mang nhãn 0?
Bước 1 trên 5: Bước 1
Phân tích chi tiết
Mỗi phần tử của A_i thuộc thêm một tập khác. Một tập khác cố định chứa nhiều nhất một phần tử của A_i, và có 2n tập khác; vì A_i có 2n phần tử nên mỗi tập khác chứa đúng một phần tử. Do đó mỗi phần tử thuộc đúng hai tập.