Bài 2

Cho

n \ge 2

là một số nguyên. Gọi

A_1, A_2, \dots, A_{2^n}

là

2^n

tập con của một tập có

n

phần tử, xếp theo thứ tự nào đó. Chứng minh rằng

|A_1\setminus A_2| + |A_2\setminus A_3| + \cdots + |A_{2^n-1}\setminus A_{2^n}| + |A_{2^n}\setminus A_1| \ge 2^{n-2}.

Bước 1 trên 5: Thiết lập các số đếm chuyển tiếp

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

a_x:=\#\{i:x\in A_i\setminus A_{i+1}\},\quad b_x:=\#\{i:x\in A_{i+1}\setminus A_i\},\quad i=1,\dots,2^n\ (\text{indices mod }2^n)

Phân tích chi tiết

Đánh số các tập theo chu trình môđun $2^n$ . Với mỗi phần tử $x$ , gọi $a_x$ là số chuyển tiếp mà x thuộc $A_i$ nhưng không thuộc $A_{i+1}$ , và $b_x$ là số chuyển tiếp theo hướng ngược lại. Khi đó tổng cần chứng minh là $\sum_i|A_i\setminus A_{i+1}|=\sum_x a_x$ .