Bài 4

Cho

n

và

b

là các số nguyên dương. Gọi

n

là

b

-phân biệt nếu tồn tại một tập gồm

n

số nguyên dương khác nhau nhỏ hơn

b

, không có hai tập con khác nhau

U

và

V

có tổng các phần tử trong

U

bằng tổng các phần tử trong

V

. (a) Chứng minh

8

là

100

-phân biệt. (b) Chứng minh

9

không là

100

-phân biệt.

Bước 4 trên 4: Mâu thuẫn với chặn dưới một trăm

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

(s_4+\cdots+s_9)-(s_1+s_2+s_3)\ge419,\quad (s_1+s_2+s_3+s_6+s_7+s_8+s_9)-(s_4+s_5)\ge399

Phân tích chi tiết

Đếm các tập con có hai, ba hoặc bốn phần tử lớn hơn s_3 được 400 tập, nên hiệu biên thứ hai ít nhất là 399. Cộng hai bất đẳng thức cho s_6+s_7+s_8+s_9 ít nhất 409. Nhưng mỗi số trong bốn số này không vượt quá 99, tổng nhiều nhất 394, mâu thuẫn. Suy ra (b).