Bài 1

Cho

A

là tập con gồm 101 phần tử của

S=\{1,2,\ldots,10^6\}

. Chứng minh tồn tại các số

t_1,t_2,\ldots,t_{100}

trong

S

sao cho

A_j=\{x+t_j\mid x\in A\}

, với

j=1,2,\ldots,100

, đôi một rời nhau.

Bước 2 trên 3: Đếm các ứng viên bị chặn

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

Hiểu nôm na

Một họ cực đại chặn mọi ứng viên bằng các hiệu của phần tử.

10^6\le |T|(101\cdot100+1)

Phân tích chi tiết

Gọi là họ cực đại các dịch chuyển đôi một rời nhau. Mỗi phần tử của hoặc đã thuộc , hoặc có dạng , với và khác nhau. Do đó . $S$ $T$ $T$ $a,b\in A$ $t_i+b-a$ $t_i\in T$