NẾU ÍT NHẤT MỘT TRONG HAI TẬP A, B KHÔNG LÀ TẬP CON CỦA S. KHI ĐÓ|...

4. Nếu ít nhất một trong hai tập A, B không là tập con của S. Khi đó

| (A + B)∆ S | = | A +B | + | S |− 2 | (A+ B) ∩ S | ≥ | A +B | + | S |− 2 | S | = | A + B |−| S | ≥ | A | + | B |− 1 −| S | .

Do đó

| A ∆ S | + | B ∆ S | + | (A + B)∆ S | ≥ | A

| + | S | − | X | + | B

| + | S | − | Y | + | A | + | B | − 1 − | S |

= | A

| + | S | − | X | + | B

| + | S | − | Y | + | A

| + | X | + | B

| + | Y | − 1 − | S |

= 2 | A

| + 2 | B

| + | S | − 1

≥ 2 + | S | − 1 = n + 1.

Bất đẳng thức cuối cùng có được do ít nhất một bất đẳng thức | A

| ≥ 1 hoặc | B

| ≥ 1 phải xảy ra.

Vậy trong cả hai trường hợp, thì GTNN của bài toán là n + 1.

Ta chứng minh | A + B | ≥ | A | + | B | − 1. Thật vậy, giả sử các phần tử của tập A là a

< a

< . . . < a

và các phần tử của B là b

< b

< . . . < b

. Khi đó trong tổng A + B luôn có k + l − 1 số tăng dần trong

dãy sau

a

+ b

, a

+ b

, . . . , a

+ b

, a

+ b

, a

+ b

, a

+ b

, . . . , a

+ b

.

Điều này chứng tỏ kết quả cần chứng minh.

Bài tập 3.17. Cho n là số nguyên dương và S là tập gồm n phần tử, A

, . . . , A

là m tập con, mỗi tập

chứa ít nhất hai phần tử, của S thỏa mãn: với bộ ba chỉ số (i, j, k) mà A

∩ A

6 = /0, A

∩ A

6 = /0, A

∩ A

6 = /0

thì sẽ có A

∩ A

∩ A

6 = /0. Chứng minh rằng m ≤ 2

− 1.

Chứng minh. Ta chứng minh bằng quy nạp theo n. Hiển nhiên phát biểu đề bài đúng với n = 2. Giả sử

kết luận đúng với mọi số nguyên dương bé hơn n. Xét hai trường hợp